C++로 희소 행렬(Sparse Matrix) 판별하기

희소 행렬이란 무엇일까요?

희소 행렬(Sparse Matrix)은 행렬을 구성하는 요소 중 대다수가 0으로 채워져 있는 행렬을 의미합니다. 다시 말해, 행렬의 전체 요소 개수 중 절반 이상이 0이라면 해당 행렬을 희소 행렬이라고 부릅니다.

예를 들어 아래 행렬에는 0이 총 5개 포함되어 있습니다. 행렬의 전체 요소는 9개이므로, 0의 개수(5개)가 절반(4.5개)보다 많기 때문에 이 행렬은 희소 행렬에 해당합니다.

1 0 2
5 0 0
0 0 9

희소 행렬 판별 C++ 프로그램

다음은 주어진 행렬이 희소 행렬인지 아닌지를 판별하는 C++ 프로그램입니다.

예제 코드

#include<iostream>
using namespace std;
int main () {
   int a[10][10] = { {2, 0, 0} , {0, 3, 8} , {0, 9, 0} };
   int i, j, count = 0;
   int r = 3, c = 3;
   for (i = 0; i < r; ++i) {
      for (j = 0; j < c; ++j) {
         if (a[i][j] == 0)
         count++;
      }
   }
   cout<<"The matrix is:"<<endl;
   for (i = 0; i < r; ++i) {
      for (j = 0; j < c; ++j) {
         cout<<a[i][j]<<" ";
      }
      cout<<endl;
   }
   cout<<"There are "<<count<<" zeros in the matrix"<<endl;
   if (count > ((r * c)/ 2))
   cout<<"This is a sparse matrix"<<endl;
   else
   cout<<"This is not a sparse matrix"<<endl;
   return 0;
}

실행 결과

The matrix is:
2 0 0
0 3 8
0 9 0
There are 5 zeros in the matrix
This is a sparse matrix

코드 상세 설명

위 프로그램의 핵심 로직은 크게 세 단계로 나눌 수 있습니다.

1단계: 0의 개수 세기

먼저 중첩 for 루프(nested loop)를 사용하여 행렬의 모든 요소를 하나씩 검사하고, 값이 0인 요소를 만날 때마다 카운트 변수를 증가시켜 0의 총 개수를 구합니다.

for (i = 0; i < r; ++i) {
   for (j = 0; j < c; ++j) {
      if (a[i][j] == 0)
      count++;
   }
}

2단계: 행렬 출력하기

0의 개수를 구한 후에는 마찬가지로 중첩 for 루프를 사용하여 행렬의 모든 요소를 화면에 출력합니다.

cout<<"The matrix is:"<<endl;
for (i = 0; i < r; ++i) {
   for (j = 0; j < c; ++j) {
      cout<<a[i][j]<<" ";
   }
   cout<<endl;
}

3단계: 희소 행렬 여부 판별하기

마지막으로 행렬에 포함된 0의 개수를 출력하고, 조건문을 통해 판별 결과를 보여줍니다. 만약 0의 개수가 행렬 전체 요소 수(r * c)의 절반보다 많다면 희소 행렬로 판정하고, 그렇지 않다면 희소 행렬이 아니라고 출력합니다.

cout<<"There are "<<count<<" zeros in the matrix"<<endl;
if (count > ((r * c)/ 2))
cout<<"This is a sparse matrix"<<endl;
else
cout<<"This is not a sparse matrix"<<endl;

마무리

이처럼 희소 행렬 판별은 단순히 0의 개수를 세어 전체 요소 수의 절반과 비교하는 것만으로 손쉽게 구현할 수 있습니다. 참고로 실무에서는 메모리 효율을 위해 0이 아닌 값만 저장하는 CSR(Compressed Sparse Row), CSC(Compressed Sparse Column) 같은 압축 저장 방식도 널리 활용되니 함께 알아두시면 좋습니다.