[백준 2748] 피보나치 수 2

해당 문제는 DP를 이용해 피보나치 수를 구현하는 문제이다.
DP는 Dynamic Programming의 약자로 한 번 구한 답들은 저장해두는 메모이제이션 방식(Top-Down)과, 미리 다 구해놓는 타뷸레이션 방식(Bottom-Up)이 있다.
이 문제는 반복문을 사용한 타뷸레이션 방식을 사용하였다.
(메모이제이션 같은 경우 재귀 함수를 사용한다고 한다.)

작성한 코드

import sys
input = sys.stdin.readline
N = int(input())
T = []
T.append(0)
T.append(1)
for i in range(N):
    T.append(T[i] + T[i+1])
print(T[N])

Top-Down 방식으로 구현하기

	cache = [-1]*91
    cache[0] = 0
    cache[1] = 1
    
	def f(n):
    	if cache[n] == -1:
        	cache[n] = f(n-1) + f(n-2)
           
        return cache[n]
        
    print(f(int(input())))

재귀함수로도 구현할 수 있다.

배운 점

1. DP는 DP 테이블을 사용하여 구현한다.
   빈 리스트에 테이블을 채우는 방식으로 구현하면 타뷸레이션 방식이다.