C++로 주어진 행렬이 희소 행렬(Sparse Matrix)인지 확인하는 방법

이번 글에서는 C++를 사용하여 주어진 행렬이 희소 행렬(Sparse Matrix)인지 판별하는 방법을 알아보겠습니다.

희소 행렬이란?

희소 행렬은 행렬 내 대부분의 요소가 0으로 채워져 있는 행렬을 의미합니다. 일반적으로 전체 요소의 3분의 2(2/3) 이상이 0일 경우 해당 행렬을 희소 행렬로 정의합니다. 희소 행렬은 메모리 절약과 연산 최적화를 위해 특수한 저장 기법으로 다뤄지는 경우가 많습니다.

다음은 희소 행렬의 예시입니다.

{0, 2, 0, 0, 0}
{8, 0, 0, 0, 0}
{0, 3, 0, 0, 0}
{0, 9, 0, 3, 0}
{0, 0, 0, 0, 4}

판별 알고리즘

희소 행렬 여부를 확인하는 과정은 매우 간단합니다.

1. 행렬을 순회하면서 값이 0인 요소의 개수를 셉니다.
2. 0의 개수가 전체 요소 개수(m × n)의 3분의 2보다 큰지 비교합니다.
3. 크다면 희소 행렬, 그렇지 않다면 희소 행렬이 아닙니다.

C++ 구현 예제

#include <iostream>
#include <cmath>
#define MAX 5
using namespace std;

bool isSparseMatrix(int arr[][MAX], int m, int n) {
    int counter = 0;
    for (int i = 0; i < m; i++)
        for (int j = 0; j < n; j++)
            if (arr[i][j] == 0)
                counter++;
    return (counter > (2*(m * n) / 3));
}

int main() {
    int matrix[MAX][MAX] = {
        {0, 2, 0, 0, 0},
        {8, 0, 0, 0, 0},
        {0, 3, 0, 0, 0},
        {0, 9, 0, 3, 0},
        {0, 0, 0, 0, 4}
    };

    if(isSparseMatrix(matrix, MAX, MAX)){
        cout << "This is sparse matrix";
    } else {
        cout << "This is not sparse matrix";
    }
}

실행 결과

This is sparse matrix

코드 설명

isSparseMatrix 함수는 이중 반복문을 사용해 행렬의 모든 요소를 확인하며, 값이 0인 경우 카운터를 증가시킵니다. 모든 요소를 검사한 후, 0의 개수가 전체 요소 수의 3분의 2보다 많으면 true를 반환하여 해당 행렬이 희소 행렬임을 알립니다.

위 예제의 5×5 행렬은 총 25개의 요소 중 19개가 0이므로, 25 × 2/3 ≈ 16.67보다 많아 희소 행렬로 판별됩니다. 시간 복잡도는 O(m×n)으로, 행렬의 크기에 비례합니다.