개요
이 글에서는 C++를 사용하여 그래프 행렬(Graph Matrix)의 역행렬(Inverse)을 구하는 프로그램을 소개합니다. 역행렬은 행렬이 비특이(non-singular), 즉 행렬식(determinant)이 0이 아닌 경우에만 존재합니다. 역행렬을 구하는 방법은 여러 가지가 있지만, 여기서는 수반 행렬(adjoint matrix)과 행렬식을 이용하는 고전적인 방법을 다룹니다.
알고리즘 단계
시작
함수 INV()를 통해 행렬의 역행렬을 구한다:
1. 함수 DET()를 호출하여 행렬식을 계산한다.
2. 함수 ADJ()를 호출하여 수반 행렬을 계산한다.
3. 아래 공식으로 역행렬을 구한다.
Inverse(matrix) = ADJ(matrix) / DET(matrix)
종료
핵심 개념 정리
- 행렬식(DET): 정방 행렬의 스칼라 값으로, 값이 0이면 역행렬이 존재하지 않습니다.
- 여인수(Cofactor): 특정 행과 열을 제거한 부분 행렬(소행렬, minor)의 행렬식에 부호를 붙인 값입니다.
- 수반 행렬(ADJ): 여인수 행렬의 전치(transpose) 행렬입니다.
- 역행렬 공식: A⁻¹ = adj(A) / det(A)
C++ 코드 예제
#include<bits/stdc++.h>
using namespace std;
#define N 5
// 주어진 행 p와 열 q를 제외한 부분 행렬(소행렬)을 t에 복사
void getCfactor(int M[N][N], int t[N][N], int p, int q, int n) {
int i = 0, j = 0;
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
if (r != p && c != q) {
t[i][j++] = M[r][c];
if (j == n - 1) { // 한 행이 채워지면 다음 행으로 이동
j = 0; i++;
}
}
}
}
}
// 행렬식 계산 (재귀적 여인수 전개)
int DET(int M[N][N], int n) {
int D = 0;
if (n == 1)
return M[0][0];
int t[N][N]; // 여인수 저장용 임시 행렬
int s = 1; // 부호 곱수 (+1 / -1)
// 첫 번째 행의 각 요소를 순회하며 여인수 전개
for (int f = 0; f < n; f++) {
getCfactor(M, t, 0, f, n);
D += s * M[0][f] * DET(t, n - 1);
s = -s;
}
return D;
}
// 수반 행렬(adjoint) 계산
void ADJ(int M[N][N], int adj[N][N]) {
if (N == 1) {
adj[0][0] = 1;
return;
}
int s = 1, t[N][N];
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
getCfactor(M, t, i, j, N); // M[i][j]의 여인수 계산
s = ((i + j) % 2 == 0) ? 1 : -1; // 행+열 인덱스 합이 짝수면 양수
adj[j][i] = (s) * (DET(t, N - 1)); // 행과 열을 교환하여 전치 행렬 생성
}
}
}
// 역행렬 계산
bool INV(int M[N][N], float inv[N][N]) {
int det = DET(M, N);
if (det == 0) {
cout << "can't find its inverse"; // 행렬식이 0이면 역행렬 없음
return false;
}
int adj[N][N];
ADJ(M, adj);
for (int i = 0; i < N; i++)
for (int j = 0; j < N; j++)
inv[i][j] = adj[i][j] / float(det); // 역행렬 = 수반 행렬 / 행렬식
return true;
}
// 행렬 출력용 템플릿 함수
template<class T>
void print(T A[N][N]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
cout << A[i][j] << " ";
cout << endl;
}
}
int main() {
int M[N][N] = {
{1, 2, 3, 4, -2},
{-5, 6, 7, 8, 4},
{9, 10, -11, 12, 1},
{13, -14, -15, 0, 9},
{20, -26, 16, -17, 25}
};
float inv[N][N];
cout << "Input matrix is :\n";
print(M);
cout << "\nThe Inverse is :\n";
if (INV(M, inv))
print(inv);
return 0;
}
실행 결과
Input matrix is :
1 2 3 4 -2
-5 6 7 8 4
9 10 -11 12 1
13 -14 -15 0 9
20 -26 16 -17 25
The Inverse is :
0.0811847 -0.0643008 0.0493814 -0.0247026 0.0237006
-0.126819 -0.0161738 0.0745377 -0.0713976 0.0151639
0.0933664 0.0028245 -0.0111876 -0.0220437 0.0154006
0.143624 0.0582573 -0.0282371 0.0579023 -0.0175466
-0.15893 0.0724272 0.259728 -0.00100988 0.0150219
코드 동작 원리
1. getCfactor() – 소행렬 추출
지정된 행 p와 열 q를 제외한 나머지 요소들을 임시 행렬 t에 복사하여 (n-1)×(n-1) 크기의 부분 행렬을 만듭니다. 이 부분 행렬의 행렬식이 바로 해당 위치의 소행렬(minor) 값입니다.
2. DET() – 행렬식 계산
첫 번째 행을 기준으로 여인수 전개(cofactor expansion)를 재귀적으로 수행합니다. 각 요소에 부호(+1, -1)를 교대로 곱하고, 소행렬의 행렬식을 재귀 호출로 구해 모두 더하면 전체 행렬식이 완성됩니다.
3. ADJ() – 수반 행렬 계산
모든 요소의 여인수를 계산한 뒤, 행과 열의 인덱스를 서로 바꿔 저장(adj[j][i])함으로써 여인수 행렬의 전치 행렬, 즉 수반 행렬을 얻습니다.
4. INV() – 최종 역행렬 계산
먼저 행렬식을 확인하여 0이면 역행렬이 존재하지 않으므로 실패를 반환합니다. 그렇지 않으면 수반 행렬의 각 요소를 행렬식으로 나누어 float 형태의 역행렬을 완성합니다.
참고 사항
여인수 전개 기반의 이 방법은 개념 이해에는 매우 유용하지만, 행렬 크기가 커질수록 연산량이 팩토리얼 수준으로 급증합니다. 따라서 실무에서는 가우스 소거법(Gaussian Elimination)이나 LU 분해처럼 O(n³) 복잡도를 가지는 방법을 사용하는 것이 효율적입니다. 본 코드는 5×5 행렬처럼 작은 크기의 행렬을 학습 목적으로 다룰 때 적합합니다.