피보나치 수열은 다음 조건을 만족하는 수열이다.
$F_0=1, F_1=1, F_n=F_{n-1}+F_{n-2} \ (n \gt 2)$
$1,1,2,3,5,8,13...$
(경우에 따라서 $F_0=0$이 되기도 함)
위 식을 사용해서 구하면 시간 복잡도가 $ O(N) $이기 때문에 $N <100,000,000$ 정도까지는 구하겠지만 그 이상되는 수는 구하기가 힘들다.
이를 최적화하여 빠르게 구해보자!
다음과 같은 행렬이 있다고 하자
$A = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end {pmatrix}$
이 행렬을 거듭제곱해보자
$A^2 = \begin {pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 2 & 1 \\ 1 & 1 \end {pmatrix}$
$A^3 = \begin {pmatrix} 2 & 1 \\ 1 & 1 \end{pmatrix}\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 3 & 2 \\ 2 & 1 \end {pmatrix}$
$A^4 =\begin {pmatrix} 3 & 2 \\ 2 & 1 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}= \begin{pmatrix} 5 & 3 \\ 3 & 2 \end {pmatrix}$
이를 일반화해보면
$A^n = \begin {pmatrix} F_n & F_{n-1} \\ F_{n-1} & F_{n-2} \end {pmatrix}$
가 된다.
따라서 우리는 행렬 $A$를 $n$제곱한 후 $0$행, $0$열의 수를 얻으면 된다.
거듭제곱 알고리즘은 $O(\log N)$임이 알려져 있고 행렬 연산은 $O(2^3)$이므로 피보나치 수를 구하는데 $O(\log N)$시간 내에 구할 수 있다.
(점화식 특성상 Berlekamp-Massey 알고리즘으로도 구할 수 있다.)
'프로그래밍 > 알고리즘' 카테고리의 다른 글
[알고리즘] 이분탐색 (0) | 2021.12.23 |
---|---|
[알고리즘] 알고리즘 문제를 풀 때 알면 좋은것들 (0) | 2021.12.05 |
[알고리즘] 모듈러 연산과 페르마의 소정리 (0) | 2021.12.02 |
[알고리즘] 피보나치 수열의 성질 (0) | 2021.12.02 |
[알고리즘] 분할 정복을 이용한 거듭제곱 (0) | 2021.12.02 |