모래블로그

1. 다이나믹 프로그래밍(DP)이란 1950년대 미국의 수학자인 벨만(Richard E. Bellman)이 최적화 문제(Optimization Problem)를 해결하기 위해서 고안한 복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법을 말한다. 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용한다. (위키백과) 2. 다이나믹 프로그래밍 조건 다이나믹 프로그래밍을 적용하려면 아래 2가지 조건을 만족해야한다. 1) 부분 반복 문제(Overlapping Subproblem) 작은 문제들이 중복된다는 것이다. DP는 기본적으로 문제를 나누고, 그 문제의 결과 값을 재활용해서 전체 답을 구하므로 동일한 작은 문제들이 반복하여 나타나는 경우에 ..