동적 계획법이란? 동적 계획법(Dynamic Programming, DP)은 복잡한 문제를 간단한 여러 개의 하위 문제(subproblem)로 나누어 푸는 알고리즘 기법 중 하나입니다. DP는 부분 문제의 결과 값을 저장해놓고 재활용하여 전체 문제를 해결하는 방식으로 동작합니다. 동적 계획법의 조건 DP는 크게 2가지 조건을 만족해야 합니다. 작은 부분 문제들이 반복되어 나타나는 구조여야 합니다. 한 부분 문제에서의 정답이 다른 부분 문제에서의 정답을 결정하는 데 영향을 미쳐서는 안 됩니다. 동적 계획법의 절차 DP 알고리즘은 일반적으로 다음과 같이 세가지 절차를 따릅니다. 주어진 문제를 작은 부분 문제로 분할합니다. 부분 문제의 해결을 위해 이전 단계에서 구한 값을 저장하고 재귀로써 문제를 해결합니다...