행렬 거듭제곱(Matrix Exponentiation)은 행렬의 n제곱을 분할 정복으로 O(k³ log n)에 계산하는 기법이다(k: 행렬 크기). 선형 점화식의 n번째 항을 O(log n)에 구하거나 그래프의 n-hop 경로 수 계산에 활용된다.
핵심 원리
A^n = A^(n/2) * A^(n/2) (n이 짝수)
A^n = A^((n-1)/2) * A^((n-1)/2) * A (n이 홀수)
구현
python
def mat_mul(A, B, mod=10**9+7):
n = len(A)
C = [[0]*n for _ in range(n)]
for i in range(n):
for k in range(n):
if A[i][k] == 0: continue
for j in range(n):
C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % mod
return C
def mat_pow(A, n, mod=10**9+7):
size = len(A)
result = [[1 if i==j else 0 for j in range(size)] for i in range(size)] # 단위행렬
while n:
if n & 1:
result = mat_mul(result, A, mod)
A = mat_mul(A, A, mod)
n >>= 1
return result
def fibonacci(n, mod=10**9+7):
"""피보나치 n번째 항을 O(log n)에 계산"""
if n <= 1: return n
M = [[1,1],[1,0]]
R = mat_pow(M, n-1, mod)
return R[0][0]
활용
| 문제 | 행렬 크기 |
|---|
| 피보나치 수열 | 2×2 |
| 선형 점화식 (k개 항) | k×k |
| 그래프 n-hop 경로 수 | V×V |
| 문자열 DP 가속 | 상태 수 × 상태 수 |
관련 개념
