다이나믹 프로그래밍 (Dynamic Programming, DP)

• 복잡한 문제를 해결하기 위해 사용되는 최적화 기법
• 큰 문제를 여러 작은 부분 문제로 나누어 해결하고, 그 결과를 저장하여 같은 부분 문제를 반복적으로 해결하지 않도록 하는 방식
• 최적화 문제나 점화식 기반 문제에서 사용됨

 

주요 개념

1. 부분 문제의 중복
   
   • 문제 해결 과정에서 동일한 부분 문제가 반복적으로 나타남
   • ex) 피보나치 수열 - 계산 시 동일한 피보나치 수가 여러 번 계산
2. 최적 부분 구조
   • 문제의 최적 해결 방법이 부분 문제들의 최적 해결 방법으로 구성되는 경우
   • ex) 최단 경로 문제 - 전체 경로의 최적 경로는 부분 경로의 최적 경로로 구성
3. 메모이제이션 (Memoization) 또는 타뷸레이션 (Tabulating)
   • 메모이제이션 : 재귀적 접근에서 이미 계산된 부분 문제의 결과를 저장하여 중복 계산 방지
   • 타뷸레이션 : 반복적 접근에서 작은 부분 문제부터 차례대로 해결하여 결과를 테이블에 저장

 

단계

1. 문제 정의 및 부분 문제 구성
   
   • 문제를 여러 작은 부분 문제로 나누어 정의
2. 점화식 (Recurrence Relation) 수립
   • 부분 문제 간의 관계를 정의하는 점화식 수립
3. 테이블 초기화
   • DP 테이블(배열)을 초기화. 초기 상태(기저 사례) 설정
4. 테이블 채우기
   • 점화식 이용해 테이블 채우기. 작은 부분 문제부터 시작하여 큰 문제로 확장
5. 해답 도출
   • 테이블에 저장된 값 중에서 최종 해답 도출

 

특징

• 효율성 : 부분 문제의 결과를 저장하여 중복 계산 피함 -> 시간 복잡도 크게 줄임
• 재사용성 : 여러 문제 해결시 다이나믹 프로그래밍 기법 재사용 가능
• 메모리 사용량 : 저장 공간 많이 필요할 수 있음
• 점화식 필요 : 문제 해결 위해 점화식 정의 필요, 직관적이지 않을 수 있음

 

예시 문제

• 최장 공통 부분 수열 (LCS)
  • 두 문자열이 주어질 때, 두 문자열에 모두 나타나는 가장 긴 부분 수열 찾기
• 배낭 문제 (Knapsack Problem)
  • 일정한 무게 제한 내에서 물건들을 선택하여 최대 가치를 얻도록 하는 문제
• 최소 편집 거리 (Edit Distance)
  • 하나의 문자열을 다른 문자열로 변환하는 데 필요한 최소 편집 작업 (삽입, 삭제, 교체)의 수를 계산