[기초 알고리즘] 수학: 행렬

• 수 또는 다항식 또는 함수 등을 직사각형 모양으로 배열한 것

 

피보나치 행렬

상태 벡터

$ S_n = \begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix} $

• ➡️ 위 두 값만 있으면 다음 F[n+1]을 구할 수 있음

 

행렬 표현

$ \begin{bmatrix} F_{n+1} \\ F_n \end{bmatrix}
=
\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}
\begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix} $

• 선형 변환으로 표현 가능

 

점화식

$ S_n = A^{\,n-1} S_1 $

• A: 피보나치 행렬
• ✅ 행렬 A를 한번 곱하기 = 한 단계를 한칸 이동시키는 연산
• ➡️ A의 n제곱을 빠른 거듭제곱으로 계산하면 빠르게 구할 수 있음

 

점화식 유도

A × S₁ = S₂  
A × S₂ = S₃  
...
A × Sₙ₋₁ = Sₙ

Sₙ = A × A × A × ... × A × S₁
     └───── n−1번 ─────┘
     = A⁽ⁿ⁻¹⁾ S₁

 

 

출처

• Wiki - 행렬