동적 계획법? (DP, Dynamic Programming?)

동적 계획법(DP, Dynamic Programming)이 뭐야?

• 주어진 문제를 여러개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법을 결합해서 최종 문제를 해결하는 문제 해결 방식이다.
• 탐욕 알고리즘이 매 순간 최적의 선택을 찾는 방식이라면, DP는 모든 경우의 수를 조합해 최적의 해법을 찾는 방식이다.
• 탐욕 알고리즘에 비해 시간이 오래 걸리지만, 결과적으로는 항상 최적의 해를 구할 수 있다는 이점을 가지고 있다.
• 하위 문제를 한번 계산하게 되면 그 해결책을 저장해두고, 나중에 만약 동일한 하위 문제를 만나게 된다면 이전에 저장해놓은 해결책을 적용시켜서 다시 계산해야 하는 경우를 줄인다. 즉 다시 말해 하나의 문제는 단 한 번만 풀도록 하는 알고리즘이다.
• 아래와 같은 조건일때 해당 알고리즘을 사용할 수 있다.
  • 큰 문제를 작은 문제로 나눌 수 있고, 이 작은 문제가 중복해서 발견될 때. (Overlapping Sub-problems)
  • 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 같다. 즉, 작은 문제에서 구한 정답은 큰 문제에서도 사용할 수 있다. (Optimal Substructure)
• 하위 문제의 해결책을 저장한 뒤 동일한 하위 문제가 나왔을 때 저장해놓은 해결책을 적용한다고 했는데, 이때 결과를 저장하는 방법을 Memoization 이라고 한다.