5-1. 다이나믹 프로그래밍

다이나믹 프로그래밍 큰 문제를 작은 문제로 나눠서 푸는 알고리즘을 말한다. Devide and Conquere와 비슷하지만, 큰 문제를 작은 문제로 나눴을 때 작은 문제들 중 동일한 문제를 계산하지 않는다는 차이점이 있다. 두 가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있다. 겹치는 부분 문제가 나타난다. (Overlapping Subproblem) 최적 부분 구조가 나타난다. (Optimal Substructure) 즉, 문제의 정답을 작은 문제의 정답에서 구할 수 있다. 다이나믹 프로그래밍에서 각 문제는 한 번만 풀어야 한다. 따라서, 정답을 한 번 구했으면 정답을 어딘가에 저장해놓는다. 이런 방법을 Memoization이라고 한다. 다이나믹 프로그래밍을 해결하는 방법에는 Top-do..

2019.05.20