이 글에서는 주어진 행렬이 희소 행렬(Sparse Matrix)인지 판별하는 방법을 자세히 알아보겠습니다. 행렬의 대다수 요소가 0으로 이루어져 있고, 0이 아닌 요소가 매우 적은 경우 해당 행렬을 희소 행렬이라고 부릅니다.
희소 행렬은 대규모 데이터를 다룰 때 메모리를 효율적으로 활용할 수 있어서 그래프 이론, 기계 학습, 과학 계산 등 다양한 분야에서 널리 사용됩니다.
문제 이해하기
아래는 입력과 출력의 예시입니다.
입력 행렬:
4 0 6 0 0 9 6 0 0
기대 출력:
Yes, the matrix is a sparse matrix
알고리즘
1단계 - 시작 2단계 - 정수형 행렬 input_matrix를 선언한다 3단계 - 행렬의 값을 정의한다 4단계 - 두 개의 for 루프를 사용해 행렬의 모든 요소를 순회하며 값이 0인 요소의 개수를 센다 5단계 - 0인 요소의 개수가 전체 요소 수의 절반보다 크면 희소 행렬이고, 그렇지 않으면 희소 행렬이 아니다 6단계 - 결과를 출력한다 7단계 - 종료
예제 1: main 메서드에서 처리하기
이 예제에서는 모든 연산을 'main' 메서드 안에서 한 번에 처리합니다.
public class Sparse {
public static void main(String args[]) {
int input_matrix[][] = {
{ 4, 0, 6 },
{ 0, 0, 9 },
{ 6, 0, 0 }
};
System.out.println("The matrix is defined as: ");
int rows = 3;
int column = 3;
int counter = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < column; j++) {
System.out.print(input_matrix[i][j] + " ");
}
System.out.println();
}
for (int i = 0; i < rows; ++i)
for (int j = 0; j < column; ++j)
if (input_matrix[i][j] == 0)
++counter;
if (counter > ((rows * column) / 2))
System.out.println("\nYes, the matrix is a sparse matrix");
else
System.out.println("\nNo, the matrix is not a sparse matrix");
}
}출력 결과
The matrix is defined as: 4 0 6 0 0 9 6 0 0 Yes, the matrix is a sparse matrix
예제 2: 객체 지향 방식으로 구현하기
이 예제에서는 연산을 별도의 메서드로 캡슐화하여 객체 지향 프로그래밍 스타일로 작성합니다.
public class Sparse {
static int rows = 3;
static int column = 3;
static void is_sparse(int input_matrix[][]){
int counter = 0;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < column; j++) {
System.out.print(input_matrix[i][j] + " ");
}
System.out.println();
}
for (int i = 0; i < rows; ++i)
for (int j = 0; j < column; ++j)
if (input_matrix[i][j] == 0)
++counter;
if (counter > ((rows * column) / 2))
System.out.println("\nYes, the matrix is a sparse matrix");
else
System.out.println("\nNo, the matrix is not a sparse matrix");
}
public static void main(String args[]) {
int input_matrix[][] = { { 4, 0, 6 },
{ 0, 0, 9 },
{ 6, 0, 0 }
};
System.out.println("The matrix is defined as: ");
is_sparse(input_matrix);
}
}출력 결과
The matrix is defined as: 4 0 6 0 0 9 6 0 0 Yes, the matrix is a sparse matrix
동작 원리 정리
- 요소 개수 세기: 중첩된 for 루프를 사용해 행렬의 모든 요소를 하나씩 확인하고, 값이 0인 요소의 개수를 counter 변수에 저장합니다.
- 판별 조건: 0인 요소의 개수가 전체 요소 수(행 × 열)의 절반보다 많으면 희소 행렬로 판별합니다.
- 시간 복잡도: 행렬의 모든 요소를 한 번씩만 확인하므로 시간 복잡도는 O(행 × 열)입니다.
두 예제 모두 동일한 로직을 사용하지만, 예제 2처럼 기능을 메서드로 분리하면 코드의 재사용성과 가독성이 향상되어 유지보수에 더 유리합니다.