[DP/동적계획법] 백준 2748 피보나치 수 2 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

2748번: 피보나치 수 2

 

 

 

2. 문제 풀이

 N번째 피보나치 수를 구하는 문제입니다.

 

2022.02.12 - [Algorithm] - [Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

[Algorithm] 메모해두고 불러와서 사용하는 동적 프로그래밍(DP)

 피보나치 수열은 대표적인 DP 알고리즘의 예입니다. 다이나믹 프로그래밍을 이용해서 풀이합니다.

 

 

 

3. 코드

N = int(input())

def calFibonacci(n):
    cache = [0, 1] #fibo(0) = 0, fibo(1) = 1
    for i in range(2, n+1):
        cache.append(cache[i-1] + cache[i-2])
    return cache

fibo = calFibonacci(N)
print(fibo[N])

 피보나치 수열을 계산하고, cache에 결괏값을 저장합니다. 재귀적 방법을 쓰지 않기 때문에, 이전 계산값을 그대로 불러와서 사용할 수 있습니다.