[자료구조] 희소 행렬(Sparse Matrix)

희소 행렬(Sparse Matrix)은 행렬의 원소 중에 많은 항들이 '0'으로 구성되어 있는 행렬이다. 희소 행렬의 대부분의 항은 '0'으로 이루어져 있어, 실제 사용하지 않는 메모리 공간으로 인해 메모리 낭비가 발생하게 된다. 그러나 0 값을 제외하고 0이 아닌 값(비영 요소)만 따로 추출하여 새로운 배열로 구성하는 방법을 사용함으로써 메모리를 효율적으로 사용할 수 있다.

​

예를 들어 아래와 같은 희소 행렬에는 5개의 비영 요소가 존재하고 있고, 이를 2차원 배열로 표현할 수 있다.

 

<희소 행렬과 2차원 배열>

 

희소 행렬의 기억 공간 비효율성을 개선하기 위해 이를 새로운 배열로 표현한다. 이때 0이 아닌 값이 존재하는 요소를 추출하여 새로운 배열로 재구성한다.

​

① 희소 행렬을 2차원 배열로 변환한다. 그리고 배열에서 0이 아닌 값을 가진 원소를 <행번호, 열번호, 값>으로 추출한다. (5개의 < > 값 추출)

<0, 0, 3>

<2, 2, 4>

<3, 3, 2>

<4, 0, 9>

<5, 4, 1>

​

② 추출한 값을 새로운 2차원 배열에 저장한다.

// 2차원 배열로 저장
int arr={0, 0, 3,
         2, 2, 4,
         3, 3, 2,
         4, 0, 9,
         5, 4, 1}

 

③ 배열의 '0행'에는 <전체 행의 개수, 전체 열의 개수, 추출한 원소의 개수> 값을 삽입한다.

int arr={6, 5, 5,   // 배열 0행에 희소 행렬에 대한 정보 저장, 6열/5행/0이 아닌 값 5개
         0, 0, 3,
         2, 2, 4,
         3, 3, 2,
         4, 0, 9,
         5, 4, 1}

 

*조밀 행렬(Dense Matrix)은 의미 있는 값인 원소로 채워져 있는 행렬로, 희소 행렬과 대비된다.

 

참고: 메가존아이티평생교육원

       네이버 지식백과, '조밀 행렬'