📒 동적계획법(Dynamic Programming)

📌 정의

주어진 최적화 문제를 재귀적인 방식으로 보다 작은 부분 문제로 나누어
부분 문제를 풀어 이 해를 조합하여 전체 문제의 해받에 이르는 방식

즉 하나의 문제를 여러 부분 문제로 바꾸어 푸는 방식인 것이다.

알고리즘의 진행에 따라 탐색해야 할 범위를 동적으로 결정함으로써
탐색 범위를 한정할 수 있다.

피보나치 수열 -> 재귀함수로 구현한다면?
f(4) = f(3) + f(2)
= f(2) + f(1) + f(1) + f(0)
= f(1) + f(0) + f(1) + f(1) + f(0)
복잡도 -> 지수함수의 형태

피보나치 수열 -> 동적계획법으로 구현한다면?
f(0) = 0, f(1) = 1
f(2) = f(1) + f(0) = 1
f(3) = f(2) + f(1) = 2
f(4) = f(3) + f(2) = 3
복잡도 -> 선형함수의 형태

📜 Knapsack Problem

-> 가장 높은 값을 가지도록 물건들을 골라 배당에 담기

📙 Code