동적 계획법 (Dynamic Programming)1. 동적 계획법(DP) 개념동적 계획법은 복잡한 문제를 더 작은 하위 문제로 나누어 해결하는 알고리즘 설계 기법이다. 핵심은 한 번 계산한 문제는 다시 계산하지 않도록 저장해 두는 것이다. 이를 통해 중복 계산을 막고 실행 시간을 획기적으로 줄일 수 있다. 2. 동적 계획법의 성립 조건모든 문제에 DP를 적용할 수 있는 것은 아니며, 다음 두 가지 조건을 만족해야 한다.최적 부분 구조 (Optimal Substructure): 큰 문제의 최적해를 작은 문제의 최적해로부터 구할 수 있는 구조다.중복 부분 문제 (Overlapping Subproblem): 동일한 작은 문제들이 반복적으로 나타나는 구조다.3. 동적 계획법을 풀기 위한 점화식 수립 DP의 핵..