피보나치 수열. _ 재귀함수.
1,1,2,3,4,8
1 + 1 = 2
fibo(1)=1
fibo(2)= 1
fibo(3) =fibo(1)+fibo(2)
fibo(n) = fibo(n-2) + fibo(n-1)
같은 계산을 N^n 반복.
결과를 기록해서 이용. = 메모이제이션 Memoization
문제를 쪼갤수 있는 구조= 겹치는 부분문제 = Overlapping subproblem.
input = 100
# memo 라는 변수에 Fibo(1)과 Fibo(2) 값을 저장해놨습니다!
memo = {
1: 1,
2: 1
}
# Top Down 방식. 반대는 바텀업
def fibo_dynamic_programming(n, fibo_memo):
if n in fibo_memo:
return fibo_memo[n]
nth_fibo = fibo_dynamic_programming(n - 1, fibo_memo)+ fibo_dynamic_programming(n - 2, fibo_memo)
fibo_memo[n] = nth_fibo
# print(nth_fibo)
return nth_fibo
print(fibo_dynamic_programming(input, memo)) # 354224848179261915075
'Algorithm' 카테고리의 다른 글
[1028 알고리즘 22] 유클리드호제법 : 최댓값 구하기 (0) | 2021.05.13 |
---|---|
[1028알고리즘 FROM 동빈나 21]그래프 탐색 : DFS vs BFS (0) | 2021.04.13 |
[1028알고리즘 19]해쉬 (0) | 2021.04.10 |
[1028알고리즘 18]정렬 (0) | 2021.04.10 |
[1028알고리즘 17]재귀함수(Recursive function) (0) | 2021.04.10 |