Dynamic Programming 최적 부분 구조(Optional Substructure) : 부분 문제들의 최적의 답을 이용해서 기존 문제의 최적의 답을 구할 수 있다는 것 이렇게 문제를 풀 때 중복되는 부분 문제들이 나타난다(overlapping subproblems) 이를 해결하는 알고리즘 패러다임이 dynamic programming : 한번 계산 한 것을 활용하는 방식 Memoization 말 그대로 계산한 값을 메모하고 사용하는 방식 → 재귀 사용 하향식 방법(Top-Down) 예제 1) 피보나치 수열 def fib_memo(n, cache): # base case if n < 3: return 1 # 이미 n번째 피보나치를 계산했으면: # 저장된 값을 바로 리턴한다 if n in cache..
