[백준 파이썬 2748] 피보나치 수 2 (브론즈 1)

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

2748번: 피보나치 수 2

n = int(input())

cache = [-1] * 91 # n이 최대 90이므로, 0~90까지 91개의 공간 필요.
cache[0] = 0 # 피보나치 수의 F0은 0
cache[1] = 1 # 피보나치 수의 F1은 1

def fi_bottomup(n): # Tabulation, 순서 중요
    for i in range(2, n + 1): # 0, 1은 미리 초기화 해뒀으므로 2부터 n까지 반복문을 돌림.
        cache[i] = cache[i - 1] + cache[i - 2]
    return cache[n]

def fi_topdown(n): # Memoization
    if cache[n] == -1: # 초기값인 경우 
        cache[n] = cache[n-1] + cache[n-2] 
    return cache[n]


print(fi_bottomup(n))
# print(fi_topdown(n))

다이나믹 프로그래밍은 동적 계획법으로, 큰 문제를 작게 쪼개서 해결하는 방법으로, 동적할당의 그거랑은 전혀 상관이 없다고 한다.. 몰랐네 

 

	Top-Down	Bottom-Up
구현	재귀	반복문
저장방식	Memoization	Tabulation

DP는 2가지 방법을 쓸 수 있는데, 개인적으로는 재귀보다는 반복문이 더 잘 머릿속에 그려져서 애용하고 있다. 위 코드에서는 상향식과 하향식을 다 구현해두었다. 탑다운은 필요할 때만 구하는 lazy-evaluation이지만, 바텀업은 미리 다 구해놓고 시작하는 Eager-evaluation이라고 한다.