동적 계획법 (1) 썸네일형 리스트형 [알고리즘] 동적 계획법(Dynamic Programming) 동적 계획법(Dynamic Programming) 큰 문제의 해답에 그보다 작은 문제의 해답이 포함되어 있으면 최적 부분 구조(Optimal Substructure)라고 한다. 이 최적 부분 구조가 지켜진 상태에서 문제에 대한 해답을 찾는 과정이 바로 동적 계획법이다. 동적 계획법은 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법이다. 예시로 피보나치 수를 보자. 피보나치 수는 다음과 같다. 1, 1, 2, 3, 5, 8, 13, 21, 34, ... 이를 점화식으로 나타내면 다음과 같다. $$\begin{align} f(1) & = f(2) = 1 \\ f(n) & = f(n-1) + f(n-2) \end{align}$$ \(n\)의 피보나치 수는 더 작은 크기인 \(n-1\)의 피보나치 수와.. 이전 1 다음