[Codility] 13. Fibonacci numbers

피보나치수열은 다음과 같은 점화식 구조를 갖는다
$F_n\begin{cases} 0 \quad (n = 0)\\ 1 \quad (n=1)\\ F_{n-1} + F_{n-2} \quad(n \ge 2)\end{cases}$

앞의 두개의 합이 다음 항의 값이 되는 특별한 수열이고, 실제로 자연에서 많이 찾아볼 수 있는 수열이다.

재귀함수로 구현

이런 점화구조는 재귀함수로 작성할 수 있다.

def fibo(n):
    if n <= 1:
        return n
    return fibo(n - 1) + fibo(n - 2)

하지만 이럴 경우 시간복잡도가 $T(n) = T(n-1) + T(n-2)$이므로 지수승으로 증가하게 되어 매우 비효율적이 된다. 알고리즘을 공부하는 사람이 $O(n!), \;O(2^n)$과 같은 것은 알고리즘은 잘못된 접근이다.

반복문으로 구현

재귀적 표현으로 이루어져있다면 Dynamic Programming으로 해결할 수 있다.

def fibonacci(n):
    fibo = [0] * (n + 1)
    fibo[1] = 1
    for i in range(2, n + 1):
        fibo[i] = fibo[i - 1] + fibo[i - 2]
        
    return fibo[n]

피보나치 수열은 input이 $n$하나이므로 시간복잡도가 $O(n)$이다.

예제1

[BOJ 2748] 피보나치 수 2 풀기
[BOJ 10826] 피보나치수 4 풀기
$n \leq 10^8$이므로 반복문을 이용하여 풀 수 있다.

다른 방법1 (행렬곱셈)

$\left[ \begin{matrix} 1 & 1 \\ 1 & 0 \\ \end{matrix} \right]^n = \left[ \begin{matrix} F_{n+1} & F_n \\ F_n & F_{n-1} \\ \end{matrix} \right], \quad n \geq 1$ 을 이용하면 $O(\log{n})$으로 피보나치 수를 구할 수 있다. 단, 행렬의 곱셈을 계산할 때, 분할정복으로 접근해야 시간복잡도가 $O(\log{n})$이다. (행렬의 크기가 2x2이므로 두 행렬의 곱셈은 $O(1)$으로 간주할 수 있다.)
참고로, 어떤 수의 제곱을 구할 때, 반씩 쪼개서 분할정복으로 풀면 시간복잡도가 $O(\log{n})$으로 해결할 수 있다.

예제2

[BOJ 2749] 피보나치수 3
[BOJ 11444] 피보나치수 6
$n \leq 10^{18}$이므로 dp를 이용하는 $O(n)$은 어림도 없다.
두 문제는 modulo 계산하는 값만 다를 뿐, 푸는 법은 같다

# BOJ 11444 기준
n = int(input())
mod = 1000000007

def mat_mul(A, B):
    # calculate matrix C = A x B
    n = len(A)
    # C를 n x n행렬로 만들고 0으로 초기화
    C = [[0] * n for _ in range(n)]
    
    for i in range(n):
        for j in range(n):
            for k in range(n):
                C[i][j] += A[i][k] * B[k][j]
            C[i][j] %= mod

    # return C = A x B
    return C

# ans : 정답이 되는 행렬, 초기화는 행렬의 항등원 I로 세팅
ans = [[1, 0], [0, 1]]

# 피보나치 수열을 구하는 기본 행렬
a = [[1, 1], [1, 0]]

while n > 0:
    # n이 홀수라면 행렬을 한번만 곱한다
    if n % 2 == 1:
        ans = mat_mul(ans, a)
        
    # 짝수인 경우, a^n = a^n/2 x a^n/2를 이용한다
    a = mat_mul(a, a)
    n //= 2

print(ans[0][1])

다른방법2 (일반항)

피보나치수열은 일반항이 알려져있다. (이산수학에서 수열의 일반항을 구하는법 참고)
$F_n = \frac{1}{\sqrt{5}} \Big(\frac{(1+\sqrt{5})^n}{2} - \frac{(1-\sqrt{5})^n}{2} \Big)$

그런데 컴퓨터로 실수(여기서는 $\sqrt{5}$)를 표현할 때는 오차가 반드시 발생하므로 일반적으로 사용되는 방법은 아니다.