Python으로 푸는 백준 1003. 피보나치 함수

백준 1003. 피보나치 함수

이 문제에서는 피보나치 수 N을 구하려고 할때,

fibonacci(N) = fibonacci(N-1) + fibonacci(N-2)

라는 점을 활용하여 

fibonacci(1)과 fibonacci(0)이 각각 몇 번 구해지는지를

구할 수 있도록 코드를 짜야 한다.

백준에서 푼 문제 리스트 보기

github에서 코드 보기

문제 풀이

문제에서는 재귀를 활용하여 피보나치의 수를 구할 때 0과 1이 필요할 때마다 출력되는 C++ 함수를 보기에 제공하고 있다.

C++함수에서 처럼 재귀를 활용한다면 코드를 이해하기 쉽고 피보나치 수도 구할 수 있지만 N의 수가 커지면 커질 수록 함수를 호출하는 일이 많아지면서 고스란히 스택 메모리에 쌓이게 된다. 스택이 꽉 차게 되면 스택 오버플로우(stack overflow)로 프로그램이 종료되기도 한다.  그러므로 재귀 함수는 단순히 코드의 구조를 이해하고 다양한 알고리즘 문제를 푸는데에만 사용하고 반복문을 통해서 이를 해결할 수 있어야 한다.모든 재귀 함수는 반복문으로 코드를 바꿔서 해결해 나갈 수 있다.

실제로 이 문제를 보기에서 주어진 재귀를 활용해, 전역변수를 2개 선언하고 0과 1이 호출되는 수를 세기만 하면 시간 초과가 난다. 아래 코드에서는 bottom-up 방식으로 피보나치 수의 작은 값부터 0과 1의 수를 구하여 저장해두면서 스택 오버플로우를 피하고 시간 초과 문제를 해결하고 있다. 

파이썬 코드

 
import sys
input = sys.stdin.readline
 
def solve(n):
    global fibolist
    return fibolist[n]
 
 
if __name__ == "__main__":
    fibolist = [(1, 0), (0, 1)]
    for i in range(2, 41):
        first = fibolist[i-2][0] + fibolist[i-1][0]
        second = fibolist[i-2][1] + fibolist[i-1][1]
        fibolist.append((first, second))
 
    t = int(input().strip())
    for i in range(t):
        n = int(input().strip())
        result = solve(n)
        print("{0} {1}".format(result[0], result[1]))
 

#파이썬 피보나치 함수 #파이썬 피보나치 #python fibonacci #백준 1003 피보나치 #백준 1003 피보나치 python