[ 백준 ] 2748번 : 피보나치 수 2 (파이썬)

문제 )

https://www.acmicpc.net/problem/2748

2748번: 피보나치 수 2

 

[ 풀이 ]

피보나치 수열의 경우 재귀함수를 사용하면 안되는 대표적인 문제이다. 
재귀함수를 사용하게 되면 중복호출이 매우 많아지기 때문이다. 

재귀 알고리즘을 이용해 피보나치 수를 구하려면 의사코드는 이런식으로 작성된다

 

이때, Fib함수가 얼마나 호출되는지 보기 위해서 그래프로 그려보았다.

재귀함수를 이용해 피보나치 수를 구하면 그래프의 분홍색 동그라미 친 부분 뿐만아니라 많은 부분들을 계속 계산해야한다.  중복계산을 반복하기 때문에 solution을 구하는데 오랜시간이 걸린다. 

그러므로 동적 프로그래밍 알고리즘을 사용해서 중복계산을 하지 않고 solution을 구해주었다. 

 

- 동적 프로그래밍 ( Dynamic Programming) 이란?

✔  입력 크기가 작은 부분 문제들을 모두 해결한 후에 그 해들을 이용해 큰 크기의 부분 문제들을 해결하여 최종적인 solution을 해결하는 Algorithm
✔ Bottom - up 

 

동적프로그래밍을 이용해 피보나치 수를 구할때의 의사코드는 이와 같다. 

 

- python code 

def Pibonacci(n):
    F=[0,1]
    for i in range(2,n+1):
        F.append(F[i-1]+F[i-2])
    return F[n]

N=int(input())
print(Pibonacci(N))