행렬식(Determinant)은 정방행렬(Square Matrix), 즉 행과 열의 개수가 같은 행렬에 대해서만 계산할 수 있습니다. 계산 방법은 첫 번째 행의 각 원소에 해당하는 여인수(Cofactor) 행렬의 행렬식을 곱한 뒤, 부호를 교대로 바꿔가며 모두 더하면 됩니다.
행렬식의 수학적 정의
3×3 행렬 A의 행렬식은 다음과 같이 전개됩니다.
$$A = \begin{bmatrix}a & b & c\\d & e & f \\g & h & i \\ \end{bmatrix}$$
$$|A| = a(ei-fh) - b(di-gf) + c(dh-eg)$$
이 공식을 C++ 코드로 구현하려면 재귀 호출을 활용합니다. 큰 행렬의 행렬식을 구할 때마다 차원을 하나씩 줄여가며 작은 부분행렬의 행렬식을 반복적으로 계산하는 방식입니다.
핵심 함수 살펴보기
1. determinantOfMatrix() - 행렬식 계산 함수
이 함수는 행렬과 그 차원 값을 매개변수로 받습니다. 행렬의 차원이 1이라면 [0][0] 위치의 값 하나만 존재하므로 그 값을 그대로 반환합니다. 이 조건은 매번 재귀 호출 시 차원이 1씩 감소하므로 재귀의 기저 조건(Base Case) 역할도 합니다.
int determinantOfMatrix(int mat[N][N], int dimension){
int Det = 0;
if (dimension == 1)
return mat[0][0];2. 여인수 전개 루프
다음으로 cofactorMat[N][N] 배열을 선언하고, firstRow가 차원보다 작을 때까지 cofactor() 함수에 전달합니다. 각 반복마다 부호(sign)를 교대로 변경하면서 첫 번째 행의 원소 × 여인수 행렬의 행렬식을 누적하여 Det 변수에 저장하고, 최종 결과를 main 함수로 반환합니다.
int cofactorMat[N][N];
int sign = 1;
for (int firstRow = 0; firstRow < dimension; firstRow++){
cofactor(mat, cofactorMat, 0, firstRow, dimension);
Det += sign * mat[0][firstRow] * determinantOfMatrix(cofactorMat, dimension - 1);
sign = -sign;
}
return Det;
}
3. cofactor() - 여인수(부분행렬) 생성 함수
cofactor() 함수는 원본 행렬, 임시 행렬(temp), 제외할 행 p, 제외할 열 q, 그리고 행렬의 차원 n을 매개변수로 받습니다. 중첩 for 루프를 사용해 행렬 전체를 순회하면서, 현재 위치가 p행 또는 q열에 해당하지 않는 경우에만 해당 값을 temp 행렬에 저장합니다. 즉, 지정된 행과 열을 제거한 부분행렬(Minor Matrix)을 만들어내는 것입니다.
void cofactor(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 column = 0; column < n; column++){
if (row != p && column != q){
temp[i][j++] = mat[row][column];temp 행렬의 한 행이 가득 차면 행 인덱스를 증가시키고 열 인덱스를 초기화하여 다음 행을 채웁니다.
if (j == n - 1){
j = 0;
i++;
}4. display() - 행렬 출력 함수
마지막으로 display() 함수는 행렬과 행·열 개수를 받아 2차원 배열처럼 순회하면서 각 행과 열의 값을 화면에 출력합니다.
void display(int mat[N][N], int row, int col){
for (int i = 0; i < row; i++){
for (int j = 0; j < col; j++)
cout<<mat[i][j]<<" ";
cout<<endl;
}
cout<<endl;
}전체 예제 코드
지금까지 설명한 내용을 종합하여 3×3 행렬의 행렬식을 구하는 전체 프로그램입니다.
#include <iostream>
using namespace std;
const int N = 3;
void cofactor(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 column = 0; column < n; column++){
if (row != p && column != q){
temp[i][j++] = mat[row][column];
if (j == n - 1){
j = 0;
i++;
}
}
}
}
}
int determinantOfMatrix(int mat[N][N], int dimension){
int Det = 0;
if (dimension == 1)
return mat[0][0];
int cofactorMat[N][N];
int sign = 1;
for (int firstRow = 0; firstRow < dimension; firstRow++){
cofactor(mat, cofactorMat, 0, firstRow, dimension);
Det += sign * mat[0][firstRow] * determinantOfMatrix(cofactorMat, dimension - 1);
sign = -sign;
}
return Det;
}
void display(int mat[N][N], int row, int col){
for (int i = 0; i < row; i++){
for (int j = 0; j < col; j++)
cout<<mat[i][j]<<" ";
cout<<endl;
}
cout<<endl;
}
int main(){
int mat[3][3] = {
{ 1, 0, 2},
{ 3, 0, 0},
{ 2, 1, 4}};
cout<<"The matrix is "<<endl;
display(mat,3,3);
cout<<"Determinant of the matrix is "<<determinantOfMatrix(mat, N);
return 0;
}
실행 결과
위 코드를 실행하면 다음과 같은 출력 결과를 확인할 수 있습니다.
The matrix is
1 0 2
3 0 0
2 1 4
Determinant of the matrix is 6
마무리
이 글에서는 여인수 전개(Cofactor Expansion)를 활용해 C++에서 행렬식을 재귀적으로 계산하는 방법을 알아보았습니다. 이 알고리즘은 이해하기 쉽다는 장점이 있지만, 행렬의 크기가 커질수록 시간 복잡도가 O(n!)으로 급격히 증가한다는 점을 유의해야 합니다. 따라서 실무에서 대규모 행렬을 다룰 때는 LU 분해 등 O(n³) 복잡도의 알고리즘을 사용하는 것이 효율적입니다.