https://www.codetree.ai/missions/2/problems/fibonacci-number?utm_source=clipboard&utm_medium=text
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
메모이제이션 방식(Top-Down방식)
n = int(input())
memo = [-1 for _ in range(n+1)]
def fibo(n):
if memo[n] != -1:
return memo[n]
if n <= 2:
memo[n] = 1
else:
memo[n] = fibo(n-1) + fibo(n-2)
return memo[n]
print(fibo(n))
Tabulation 방식 (Bottom-Up방식)
n = int(input())
MAX_NUM = 45
dp = [0 for _ in range(MAX_NUM + 1)]
dp[1] = dp[2] = 1
for i in range(3, 1+n):
dp[i] = dp[i-1] + dp[i-2]
print(dp[n])