행렬의 대부분의 원소가 0으로 이루어져 있을 때, 이를 희소 행렬(Sparse Matrix)이라고 부릅니다. 희소 행렬은 메모리 절약과 연산 최적화가 중요한 다양한 분야에서 자주 등장하는 개념입니다.
희소 행렬의 예시
다음은 3x3 크기의 행렬 예시입니다.
1 1 0 0 0 2 0 0 0
위 행렬을 보면 총 9개의 원소 중 6개가 0이므로, 대부분의 원소가 0인 희소 행렬이라고 할 수 있습니다.
문제 정의
주어진 행렬이 희소 행렬인지 아닌지를 판별하는 프로그램을 작성해야 합니다.
판별 기준과 해결 방법
행렬 내 0의 개수가 전체 원소 개수의 절반보다 많다고 가정합니다. 즉, 0의 개수가 (행 × 열) / 2보다 큰 경우를 기준으로 삼습니다.
이 조건을 만족하면 해당 행렬은 희소 행렬이고, 그렇지 않으면 희소 행렬이 아닙니다.
C 프로그램 코드
다음은 주어진 행렬이 희소 행렬인지 판별하는 C 프로그램입니다.
#include<stdio.h>
#include<stdlib.h>
int main(){
int row,col,i,j,a[10][10],count = 0;
printf("Enter row\n");
scanf("%d",&row);
printf("Enter Column\n");
scanf("%d",&col);
printf("Enter Element of Matrix1\n");
for(i = 0; i < row; i++){
for(j = 0; j < col; j++){
scanf("%d",&a[i][j]);
}
}
printf("Elements are:\n");
for(i = 0; i < row; i++){
for(j = 0; j < col; j++){
printf("%d\t",a[i][j]);
}
printf("\n");
}
/*checking sparse of matrix*/
for(i = 0; i < row; i++){
for(j = 0; j < col; j++){
if(a[i][j] == 0)
count++;
}
}
if(count > ((row * col)/2))
printf("Matrix is a sparse matrix \n");
else
printf("Matrix is not sparse matrix\n");
}프로그램 동작 순서
- 사용자로부터 행(row)과 열(column)의 크기를 입력받습니다.
- 행렬의 각 원소를 입력받아 2차원 배열에 저장합니다.
- 입력된 행렬을 화면에 출력합니다.
- 이중 반복문을 사용하여 값이 0인 원소의 개수를 셉니다.
- 0의 개수가 (행 × 열) / 2보다 크면 희소 행렬로 판별하여 결과를 출력합니다.
실행 결과
위 프로그램을 실행하면 다음과 같은 결과를 얻을 수 있습니다.
Run 1: Enter row 3 Enter Column 2 Enter Element of Matrix1 1 0 2 0 2 0 Elements are: 1 0 2 0 2 0 Matrix is not sparse matrix Run 2: Enter row 3 Enter Column 2 Enter Element of Matrix1 1 0 0 0 0 0 Elements are: 1 0 0 0 0 0 Matrix is a sparse matrix
결과 해석
실행 1: 6개의 원소 중 0이 3개뿐이므로, 0의 개수(3)가 (3 × 2) / 2 = 3보다 크지 않아 희소 행렬이 아닌 것으로 판별됩니다.
실행 2: 6개의 원소 중 0이 5개이므로, 0의 개수(5)가 3보다 커서 희소 행렬로 판별됩니다.
마무리
희소 행렬 판별은 단순히 0의 개수를 세는 것만으로 쉽게 구현할 수 있습니다. 실제 응용에서는 희소 행렬을 압축 저장하거나 CSR(Compressed Sparse Row), CSC(Compressed Sparse Column) 같은 특수한 자료구조로 표현하여 메모리와 연산 시간을 크게 절약할 수 있습니다. 이러한 확장 개념도 함께 학습해 두면 그래프 알고리즘, 과학 계산, 머신러닝 등 다양한 분야에 도움이 됩니다.