[BOJ] 피보나치 수 - 파이썬

February 14, 2021

문제

피보나치 수는 0과 1로 시작한다. 0번째 피보나치 수는 0이고, 1번째 피보나치 수는 1이다. 그 다음 2번째 부터는 바로 앞 두 피보나치 수의 합이 된다.

이를 식으로 써보면 Fn = Fn-1 + Fn-2 (n ≥ 2)가 된다.

n=17일때 까지 피보나치 수를 써보면 다음과 같다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597

n이 주어졌을 때, n번째 피보나치 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 n이 주어진다. n은 45보다 작거나 같은 자연수이다.

출력

첫째 줄에 n번째 피보나치 수를 출력한다.

예제 입출력

내 코드 (실패)

def fibonacci(n) :
    if n == 0 :
        return 0
    elif n == 1 :
        return 1
    else :
        return fibonacci(n-1) + fibonacci(n-2)

print(fibonacci(int(input())))

일반적인 피보나치 식을 이용하여 재귀적으로 풀어봤더니 시간 초과가 나왔다. pypy로 바꿔서 해봐도 여전히 시간 초과였다. 재귀 방법으로 할 경우 사실 답은 맞게 구할 수 있는데, 효율적인 방법은 아니었다. 이미 구한 값도 중복하여 계속 구해야하기 때문에 memoization을 적용하지 않으면 시간 제한이 있는 경우, 효율적이지 못하다.

내 코드 (정답)

N = int(input())
a, b = 0, 1
while N > 0 :
    a, b = b, a+b
    N -= 1
print(a)

그래서 정답으로 나온 방법은 다이나믹 프로그래밍(동적계획법) 방식이다. 일반적으로는 큰 문제를 작은 문제로 나누어서 푸는 분할정복(Divide and Conquer) 방식과 유사하게 생각 될 수 있다. 가장 큰 차이점은 다이나믹 프로그래밍의 경우, 반복적으로 생기는 작은 문제들을 메모이제이션 등의 방법으로 효율적으로 계산해서 푸는 것이다. 아까 실패한 코드와 같이 비효율적인 부분이 있을 때, 메모이제이션 등 효율을 높힐 방법을 선택해야 되는데, Top-Down 방식은 메모이제이션 방식이고, Bottom-Up 방식은 상향식 계산법인데, 이번 코드에서는 상향식 계산법으로 계산했다. 일반적으로 상향식 계산법이 좀 더 빠르다고 알려져 있다. 그래서 0부터 올라가면서 계속해서 피보나치 식으로 주어진 수 까지 계산헀다.