희소 행렬(sparse matrix)이란 행렬을 이루는 대다수의 요소가 0으로 채워져 있는 행렬을 의미합니다. 대표적인 예는 다음과 같습니다.
아래 행렬에는 0이 총 5개 포함되어 있습니다. 0의 개수가 행렬 전체 요소 개수(9개)의 절반보다 많기 때문에, 이 행렬은 희소 행렬에 해당합니다.
0 0 9 5 0 8 7 0 0
희소 행렬은 불필요한 0 값을 압축하여 저장 공간을 크게 절약할 수 있어, 이미지 처리, 과학·공학 계산, 그래프 알고리즘 등 다양한 분야에서 널리 활용됩니다. 이번 글에서는 주어진 행렬이 희소 행렬인지 판별하는 C++ 프로그램을 살펴보겠습니다.
알고리즘
- 정수형 2차원 배열 a[10][10]을 선언하고 초기값을 설정합니다.
- 정수형 변수 i, j, count를 선언하고 count는 0으로 초기화합니다.
- 정수형 변수 row, col을 선언하고 각각 3으로 초기화합니다.
- 중첩 반복문으로 행렬의 모든 요소를 검사하여 값이 0이면 count를 증가시킵니다.
- "행렬은 다음과 같습니다"라는 메시지와 함께 행렬의 모든 값을 출력합니다.
- 행렬에 포함된 0의 개수를 출력합니다.
- count가 (row × col) ÷ 2보다 크면 "희소 행렬입니다", 그렇지 않으면 "희소 행렬이 아닙니다"를 출력합니다.
예제 코드
#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
실행 결과를 보면 3×3 행렬 안에 0이 5개 존재합니다. 정수 나눗셈 기준으로 (3 × 3) ÷ 2 = 4이고, 0의 개수 5가 이 값보다 크므로 해당 행렬은 희소 행렬로 판별됩니다. 이처럼 0의 개수만 세어 간단한 조건 비교만으로 희소 행렬 여부를 손쉽게 확인할 수 있습니다.