C++로 구현하는 희소 행렬(Sparse Matrix) 판별 프로그램

희소 행렬(Sparse Matrix)이란?

희소 행렬은 행렬을 구성하는 대다수의 요소가 0으로 채워져 있는 행렬을 말합니다. 다음은 그 대표적인 예시입니다.

아래 행렬에는 0이 총 5개 들어 있습니다. 0의 개수가 행렬 전체 요소 수의 절반을 넘기 때문에 이 행렬은 희소 행렬에 해당합니다.

5 0 0
3 0 1
0 0 9

희소 행렬을 판별하는 C++ 프로그램은 다음과 같습니다.

예제 코드

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

실행 결과

The matrix is:
0 0 9
5 0 8
7 0 0
The number of zeros in the matrix are 5
This is a sparse matrix

코드 설명

1. 0의 개수 세기

위 프로그램에서는 중첩 for 루프를 사용해 행렬의 모든 요소를 하나씩 확인하면서 0의 개수를 셉니다. 해당 코드는 다음과 같습니다.

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

2. 행렬 출력하기

0의 개수를 구한 뒤에는 중첩 for 루프를 사용해 행렬 전체를 화면에 출력합니다.

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

3. 희소 행렬 여부 판별

마지막으로 0의 개수를 출력하고, 그 값이 행렬 전체 요소 수(row × col)의 절반보다 큰지 검사합니다. 조건을 만족하면 이 행렬이 희소 행렬이라는 메시지를, 만족하지 않으면 희소 행렬이 아니라는 메시지를 출력합니다.

cout<<"The number of zeros in the matrix are "<< count <<endl;
if (count > ((row * col)/ 2))
cout<<"This is a sparse matrix"<<endl;
else
cout<<"This is not a sparse matrix"<<endl;

희소 행렬이 중요한 이유

희소 행렬은 0인 요소까지 모두 저장하면 메모리가 크게 낭비됩니다. 그래서 실제 응용에서는 0이 아닌 요소만 따로 저장하는 압축 기법(예: CSR, COO 형식)을 활용합니다. 이러한 방식은 추천 시스템, 자연어 처리, 그래프 알고리즘처럼 대규모 데이터를 다루는 분야에서 메모리 사용량과 연산 속도를 크게 개선해 줍니다.