PS를 위한 수학 - 변형 피보나치 수열의 행렬 점화식
변형 피보나치 수열의 행렬 점화식
다음과 같은 점화식을 보자.
$$
f(n)=A \cdot f(n-1)+B \cdot f(n-k)
$$
여기서 $A=1,~B=1,~k=2$ 라면 일반 피보나치 수열이다.
이 문제를 그냥 푸는것보다 피보나치 수열꼴의 점홧기에 $A,B,k$ 값이 달라졌을 때 행렬을 어떻게 구성할 수 있는지 살펴보자.
이 글에선 위와 같은 꼴을 다룰 뿐이지만, 결국 위와 같은 선형 점화식 대한 행렬을 구성함에 있어 이해를 돕는다.
이 글에서 다루진 않지만 더 고급 개념인 키타마사법이나 벌레캠프 메시를 이해하는데도 도움이 될 것이다.
일반 피보나치 수열에 쓰이는 행렬을 살펴보자.
$$
\begin{pmatrix}
f(n)\\
f(n-1)
\end{pmatrix}
=
\begin{pmatrix}
1 & 1 \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
f(n-1) \\
f(n-2)
\end{pmatrix}
$$
여기서 $A, B$ 를 추가해보자.
$$
f(n)=A \cdot f(n-1)+B \cdot f(n-2)
$$
라 하자.
$$
\begin{pmatrix}
f(n)\\
f(n-1)
\end{pmatrix}
=
\begin{pmatrix}
A & B \\
1 & 0
\end{pmatrix}
\begin{pmatrix}
f(n-1) \\
f(n-2)
\end{pmatrix}
$$
단순히 $1$행의 $1, 1$을 $A, B$로 바꾸는 것으로 원하는 결과를 만들었다.
$f(n-k)$ 란 값이 등장하기 위해 $k$행 $k$열의 행렬이 필요하다는 것을 유추할 수 있다.
결국 최종 점화식은 다음과 같다.
$$
\begin{pmatrix}f(n) \\ f(n-1) \\ f(n-2)\\ \vdots \\ f(n-k+2) \\ f(n-k+1)\end{pmatrix}
=
\begin{pmatrix}A & 0 & \cdots & 0 & B \\ 1 & 0 & \cdots & 0 & 0 \\
0 & 1 & \cdots & 0 & 0 \\ &&\vdots \\
0 & 0 & \cdots & 0 & 0 \\ 0 & 0 & \cdots & 1 & 0
\end{pmatrix}
\begin{pmatrix}
f(n-1) \\ f(n-2) \\ f(n-3) \\ \vdots \\ f(n-k+1) \\ f(n-k)
\end{pmatrix}
$$
이런식으로 행렬을 구성하면 $O(k^3 \log n)$ 에 문제를 해결할 수 있다.
연습 문제
$$
f(n)=f(n-1)+f(n-k)
$$
를 구하는 문제이다.
Comments