이 튜토리얼에서는 C++를 사용하여 행렬의 행렬식(determinant)을 구하는 방법을 알아봅니다. 행렬식은 정사각 행렬(square matrix)을 하나의 스칼라 값으로 변환한 것으로, 연립 선형 방정식의 해를 구하거나 역행렬을 계산할 때 핵심적으로 사용되는 개념입니다.
행렬식 구하는 단계
행렬을 초기화합니다.
행렬식을 구하는 함수를 작성합니다.
행렬의 크기가 1 또는 2라면 간단한 공식으로 바로 행렬식을 계산할 수 있습니다.
행렬식(determinant), 부분 행렬(submatrix), 부호(sign)를 저장할 변수를 초기화합니다.
첫 번째 행의 각 열(0부터 N-1까지)을 순회합니다.
현재 원소에 해당하는 부분 행렬을 생성합니다. 부분 행렬은 현재 원소가 속한 행과 열을 제외한 나머지 원소들로 구성됩니다.
현재 원소와 그 여인수(cofactor)의 곱을 행렬식에 더합니다.
부호를 번갈아 변경합니다(+1 ↔ -1).
계산된 행렬식을 출력합니다.
예제 코드
전체 코드는 다음과 같습니다.
#include <bits/stdc++.h>
using namespace std;
#define N 3
void subMatrix(int mat[N][N], int temp[N][N], int p, int q, int n) {
int i = 0, j = 0;
// 부분 행렬 채우기
for (int row = 0; row < n; row++) {
for (int col = 0; col < n; col++) {
// 현재 원소의 행(row != p)과 열(col != q)은 건너뜀
if (row != p && col != q) {
temp[i][j++] = mat[row][col];
if (j == n - 1) {
j = 0;
i++;
}
}
}
}
}
int determinantOfMatrix(int matrix[N][N], int n) {
int determinant = 0;
if (n == 1) {
return matrix[0][0];
}
if (n == 2) {
return (matrix[0][0] * matrix[1][1]) - (matrix[0][1] * matrix[1][0]);
}
int temp[N][N], sign = 1;
for (int i = 0; i < n; i++) {
subMatrix(matrix, temp, 0, i, n);
determinant += sign * matrix[0][i] * determinantOfMatrix(temp, n - 1);
sign = -sign;
}
return determinant;
}
int main() {
int mat[N][N] = {{2, 1, 3}, {6, 5, 7}, {4, 9, 8}};
cout << "Determinant: " << determinantOfMatrix(mat, N) << endl;
return 0;
}
실행 결과
위 프로그램을 실행하면 다음과 같은 결과가 출력됩니다.
Determinant: 36
동작 원리 요약
이 코드는 여인수 전개(cofactor expansion) 방식을 재귀적으로 활용합니다. 첫 번째 행의 각 원소에 대해 해당 원소를 제외한 부분 행렬을 만들고, 그 부분 행렬의 행렬식을 재귀적으로 구한 뒤 부호를 교대로 적용하여 모두 더하는 방식입니다. 시간 복잡도는 O(n!)으로, 크기가 작은 행렬에 적합합니다. 큰 행렬의 경우 가우스 소거법(Gaussian elimination)을 사용하면 O(n³)으로 더 효율적으로 계산할 수 있습니다.
마무리
이번 튜토리얼에서는 C++로 NxN 행렬의 행렬식을 재귀적으로 구하는 방법을 살펴보았습니다. 튜토리얼에 대해 궁금한 점이 있다면 댓글로 남겨주세요!