동적계획(Dynamic Programming, DP)

동적계획(Dynamic Programming, DP)

---

동적 계획법(DP)은 복잡한 문제를 작은 하위 문제로 나누어 해결한 결과를 저장(메모이제이션)하거나 점진적으로 계산(Top-Down 혹은 Bottom-Up)하여 전체 문제를 해결하는 알고리즘 설계 기법입니다.

 

동적 계획법의 특징

1. 부분 문제의 중복성 : 동일한 하위 문제가 여러 번 재계산되는 문제를 해결하는데 적합합니다. 
2. 최적 부분 구조 : 문제의 최적해가 하위 문제의 최적해로 구성될 수 있어야 합니다.

 

동적 계획법의 접근 방법

1. 하향식 접근방법 
   • 재귀와 메모이제이션을 이용해 해결
   • 큰 문제를 작은 문제로 분할하면서 해결
   • 이미 계산된 하위 문제의 결과를 저장하여 중복 계산을 방지
2. 상향식 접근방법
   • 작은 문제부터 차례대로 해결하여 큰 문제를 해결
   • 보통 배열을 이용해 결과를 저장

 

동적 계획법 문제 해결 단계

1. 문제를 정의하고 분석
   • 문제를 하위 문제로 나눌 수 있는지 확인
   • 중복되는 하위 문제가 있는지 분석
2. 점화식(재귀 관계) 정의
   • 하위 문제와 전체 문제 사이의 관계를 수식으로 나타냄
3. 메모리 구조 설계
   • 결과를 저장할 배열이나 테이블 설계
4. 알고리즘 구현
   • 하향식(재귀) 또는 상향식(반복문)으로 구현

 

동적 계획법 응용 문제

1. 최대 부분 합 문제
   • 배열에서 연속된 부분의 합 중 최대값을 찾는 문제
   • 예 Kadane's 알고리즘
2. 최장 공통 부분 수열(LCS)
   • 두 문자열에서 공통으로 나타나는 가장 긴 부분 수열을 찾는 문제
3. 배낭 문제(Knapsack Problem)
   • 제한된 무게에서 최대 가치를 찾는 문제
4. 최단 경로 문제
   • 그래프에서 한 노드에서 다른 노드로 가는 최단 거리를 찾는 문제

 

장점	단점
중복 계산을 방지해 효율적	문제를 DP로 모델링하는 것이 어렵다.
점진적 해결로 메모리 사용을 최소화 가능	테이블이나 배열 사용으로 메모리 사용이 많아질 수 있음