희소 행렬(Sparse Matrix)이란?
이 글에서는 희소 행렬이 무엇인지, 그리고 이를 메모리에 어떻게 효율적으로 표현할 수 있는지 살펴보겠습니다. 희소 행렬이란 행렬을 구성하는 대부분의 원소가 0인 행렬을 의미합니다. 좀 더 구체적인 정의로는, 전체 m×n 크기 중 약 30% 수준인 최대 1/3 정도만 0이 아닌 원소(non-zero element)를 가지는 행렬을 희소 행렬이라고 부릅니다.
희소 행렬이 메모리 낭비를 일으키는 이유
컴퓨터에서는 다양한 연산을 효율적으로 수행하기 위해 행렬을 활용합니다. 그런데 행렬이 희소(sparse)한 성질을 가지고 있다면 어떻게 될까요? 연산 자체는 오히려 쉬워질 수 있지만, 값이 0인 원소들까지 모두 저장해야 하기 때문에 메모리 공간을 불필요하게 많이 차지하게 됩니다.
예를 들어 아래와 같은 6×6 희소 행렬 M이 있다고 가정해 보겠습니다.
이 행렬에는 0이 아닌 원소가 단 8개뿐이며, 나머지 28개는 모두 0입니다. 그럼에도 이 행렬은 6×6 = 36개의 메모리 공간을 그대로 차지합니다. 행렬의 크기가 커지면 커질수록 낭비되는 공간은 기하급수적으로 늘어나겠죠.
삼중항(Triplet) 테이블을 이용한 저장 방식
이러한 낭비를 줄이기 위해 희소 행렬은 별도의 표(table) 구조로 저장할 수 있습니다. 행 번호(Row), 열 번호(Column), 해당 위치의 값(Value) 세 가지 정보를 묶어 아래와 같은 테이블 X를 만드는 것입니다.
- 1열: 행(row) 번호
- 2열: 열(column) 번호
- 3열: M[row, col] 위치에 저장된 실제 데이터 값
각 행은 세 개의 정보를 담고 있기 때문에 삼중항(triplet)이라고 부릅니다. 특히 첫 번째 삼중항은 행렬의 크기 정보를 나타냅니다. Row = 6, Column = 6은 행렬 M이 6×6 행렬임을 의미하고, Value 필드의 8은 배열 안에 존재하는 0이 아닌 원소의 개수를 뜻합니다.
공간 복잡도 분석
그런데 의문이 생깁니다. 이 테이블 역시 9행 × 3열 = 36개의 공간을 사용하는데, 과연 어디가 이득일까요? 핵심은 확장성에 있습니다. 만약 행렬 크기가 8×8 = 64가 되더라도 0이 아닌 원소가 여전히 8개라면, 테이블 X는 변함없이 36개의 공간만 사용하면 됩니다.
즉, 이 테이블은 열이 고정된 3개이고, 행의 개수는 0이 아닌 원소의 개수에 따라서만 달라집니다. 따라서 0이 아닌 원소의 개수를 T라고 할 때, 공간 복잡도는 O(3×T), 즉 O(T)가 됩니다. 반면 원본 행렬을 통째로 저장하는 방식의 공간 복잡도는 O(m×n)이므로, 행렬이 클수록 삼중항 표현 방식이 훨씬 효율적이라는 결론을 내릴 수 있습니다.