피보나치 수를 구하는 다양한 방법

알고리즘 문제를 풀다 보니 피보나치 수를 구하는 방법이 상당히 많다. 따라서 이 피보나치 수로 배울 수 있는 알고리즘이 다양하기에 한번 정리를 해보려고 한다.

피보나치 수열이란?

기원전 5세기 인도의 수학자 핑갈라가 쓴 책에서 처음 언급 됐으며 유럽에서 레오나르도 피보나치가 토끼 수의 증가에 대해서 이야기 하면서 유명해졌다.

해당 내용은 n번째 달의 토끼 쌍의 수는

• 첫 달에는 새로 태어난 토끼 한 쌍만이 존재한다.
• 두 달 이상이 된 토끼는 번식이 가능하다.
• 번식 가능한 토끼 한 쌍은 매달 새끼 한 쌍을 낳는다.
• 토끼는 죽지 않는다

이 문제를 통해서 나온 것이 바로 피보나치 수열이다.

첫 번째 달, 두 번째 달 까지는 1쌍이 존재할 것이다. 세 번째 달이 되면서 토끼가 번식이 가능해지면서 2쌍이 되고 3번째 달은 3쌍, 4번째 달은 5쌍과 같이 점점 불어나 n번째 달에는 a, n+1번째 달에는 b, n+2번째 달에는 a+b가 될 것이다.

 

이를 점화식으로 정리하면

$ F_{0} = 0 $

$ F_{1} = F_{2} = 1$

$ F_{n} = F_{n-1} + F_{n-2}  \ \ \ ( n >= 3) $

혹은

$ F_{0} = F_{1} = 1$

$ F_{n} = F_{n-1} + F_{n-2}  \ \ \ ( n >= 2) $

으로 나타낼 수 있다. 하지만 나는 전자로 구현을 하도록 하겠다.

 

구현해보기

이를 구현하는 방법에는 여러 가지 방법이 있다.

가장 먼저 단순하게 구현을 해보자

여기서 나는 항이 0번째부터 시작을 하는 것으로 구현을 하겠다.

1. 재귀 함수 - $O(N^2)$

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

가장 간단한 방법으로 하향식으로 단순하게 더해주는 방법이다. 함수를 두 번씩 호출하면서 하기 때문에 (했던 연산을 또 해야 하므로 매우 비효율적) n이 작을 때는 괜찮지만 비효율적인 방법으로 수가 조금만 커져도 커지면 오래 걸린다는 단점이 있다. 

 

2. 반복문(for문) 이용 - $ O(N) $

def fibonacci_for(n):
    a, b = 0, 1
    for i in range(n):
        a, b = a + b, a
    return a

 

단순하게 for문을 이용하여 상향식으로 단순 재귀로 구현한 방법보다 효율적으로 구현한 방법이다.

3. dp문(메모이제이션, 타뷸레이션) - $ O(N) $

1. 메모이제이션(하향식)

cache = {
    0: 0,
    1: 1
}
def fibonacci_memo(n):
    if n in cache:
        return cache[n]
    cache[n] = fibonacci_memo(n - 1) + fibonacci_memo(n - 2)
    return cache[n]

1. 타뷸레이션(상향식)

cache = {
    0: 0,
    1: 1
}


def fibonacci_tabul(n):
    if n in cache:
        return cache[n]
    for i in range(2, n + 1):
        cache[i] = cache[i - 1] + cache[i - 2]
    return cache[n]

 

1번(재귀)의 방법에서 이전에 했던 연산들의 결과를 메모리에 저장을 하여 불필요한 연산을 없앤 방법이다. 따라서 1번의 방법보다는 재귀 함수를 이용해서 해결을 하고 싶다면 해당 방법을 사용하는 것이 보다 효율적이다. 

동적 프로그래밍(DP)에 관한 설명은 https://teching.tistory.com/89 에서 좀 더 알아보았다.

동적 계획법 (파이썬)

 

5. 분할 정복(행렬의 제곱) - $ O(logN) $

def matrix_multiple(matrix1, matrix2):
    res = [[0] * len(matrix2[0]) for _ in range(len(matrix1))]
    for i in range(len(matrix1)):
        for j in range(len(matrix2[0])):
            for k in range(len(matrix1[0])):
                res[i][j] += matrix1[i][k] * matrix2[k][j]
    return res


def matrix_square(matrix, b):
    if b == 1:
        return matrix
    div_matrix = matrix_square(matrix, b // 2)
    square_matrix = matrix_multiple(div_matrix, div_matrix)
    if b % 2 == 0:
        return square_matrix
    else:
        return matrix_multiple(square_matrix, matrix)


def fibonacci_div(n):
    matrix = [[1, 1], [1, 0]]
    if n <= 1:
        return n
    else:
        answer = matrix_square(matrix, n - 1)
        return answer[0][0]

갑자기 어려운 방법이 등장하였다. 이를 이해하기 위해서는 분할 정복에 대해서 이해를 먼저 해야 하는데 동적 프로그래밍(DP)과 차이점을 간략하게 설명하자면 DP는 메모리를 사용하여 이전에 구했던 계산을 재사용한다는 느낌이지만 분할 정복을 메모리를 사용하는 것이 아닌 단순히 문제를 조그마한 문제로 쪼개어 작은 문제를 반복되게 만들어 연산 횟수를 줄이는 것이다. 위의 코드도 단순히 피보나치 수를 전부 구하는 것이 아닌 n을 반으로 쪼개는 방법을 사용해 연산 횟수를 획기적으로 줄여 다른 방법들보다 확연히 빠른 속도를 보여주게 된다.

 

구현 방법에 대해서 간략하게 설명해보자면 피보나치 수의 점화식을 행렬로 표현하면

$ \begin{bmatrix}f(n+1) & f(n) \\f(n) & f(n-1) \end{bmatrix} =  \begin{bmatrix}1 & 1 \\1 & 0 \end{bmatrix} ^{n}  $ 으로 나타낼 수 있다.

즉 $  \begin{bmatrix}1 & 1 \\1 & 0 \end{bmatrix}  $ 행렬을 거듭제곱 하는 것으로 원하는 n번째의 피보나치 수열을 구할 수 있는데 여기서 거듭제곱을 할때 분할정복을 이용해서 구현해주면 된다.

예를 들어 10번째 피보나치 수를 구하고 싶으면

$ \begin{bmatrix}1 & 1 \\1 & 0 \end{bmatrix}  ^ {10} =  \begin{bmatrix}1 & 1 \\1 & 0 \end{bmatrix}  ^ {5}  \times \begin{bmatrix}1 & 1 \\1 & 0 \end{bmatrix}  ^ {5} $

이고 5 제곱은

$ \begin{bmatrix}1 & 1 \\1 & 0 \end{bmatrix}  ^ {5} =  \begin{bmatrix}1 & 1 \\1 & 0 \end{bmatrix}  ^ {2}  \times \begin{bmatrix}1 & 1 \\1 & 0 \end{bmatrix}  ^ {2} \times \times \begin{bmatrix}1 & 1 \\1 & 0 \end{bmatrix} $

2 제곱은

$ \begin{bmatrix}1 & 1 \\1 & 0 \end{bmatrix}  ^ {2} =  \begin{bmatrix}1 & 1 \\1 & 0 \end{bmatrix}  \times \begin{bmatrix}1 & 1 \\1 & 0 \end{bmatrix} $

 

이렇게 계산 횟수를 획기적으로 줄일 수 있다. 계산해보면 $ O(log{N}) $의 시간이 걸린다!

 

6. 일반 항 $ O(logN)  $

def past_pow(a, b):
    if b == 0:
        return 1
    elif b == 1:
        return a
    else:
        div_con = past_pow(a, b // 2)
        if b % 2 == 0:
            return div_con * div_con
        else:
            return div_con * div_con * past_pow(a, 1)


def fibonacci_gen(n):
    root_5 = 5 ** .5
    alpha = (1 + root_5) / 2
    beta = (1 - root_5) / 2
    return int((1 / root_5) * (past_pow(alpha, n) - past_pow(beta, n)))

 

마지막으로 피보나치 수의 일반항을 이용하는 것이다. 이번 게시글을 작성하면서 새롭게 알게 된 내용이다.

자세한 내용은 https://ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98에서 확인할 수 있다.

피보나치 수 - 위키백과, 우리 모두의 백과사전

 

피보나치의 항등식은 

해당 방법으로 구할 수 있다.  해당 방법을 통해서 단순히 구현을 해주면 되는데 여기서 거듭제곱을 사용하기 때문에 분할 정복을 사용해서 구현해주면 빠른 방법으로 구현할 수 있다. (단순히 5번 방법을 조금 더 단순화시킨 것과 같다.)