동적 계획법

메모이제이션

컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술, 동적 계획법의 핵심

추가적인 메모리 공간이 필요.

재귀 함수 호출로 인한 시스템 호출 스택을 사용, 실행 속도 저하 또는 오버플로우 발생

1. 중복 부분문제 구조

• DP는 큰 문제를 이루는 작은 문제들을 먼저 해결하고 작은 문제들의 최적 해를 이용하여 순환적으로 큰 문제를 해결한다.
  • 순환적인 관계를 명시적으로 표현하기 위해서 동적 계획법에서는 일반적으로 수학적 도구인 점화식을 사용한다.
• DP는 문제의 순환적인 성질 때문에 이전에 계산되어졌던 작은 문제의 해가 다른 어딘가에 필요하게 되는데 이를 위해 DP에서는 이미 해결된 작은 문제들의 해들을 어떤 저장 공간에 저장
• 저장된 해들이 다시 필요할 때 마다 해를 얻기 위해 다시 문제를 재계산 하지 않고 table의 참조를 통해 중복된 계산을 피하게 된다.

2. 최적 부분문제 구조

• 동적 계획법이 최적화에 대한 어느 문제에나 적용될 수 있는 것은 아님. 주어진 문제가 최적회의 원칙을 만족해야만 동적 계획법을 효율적으로 적용할 수 있다.
• 최적화의 원칙 : 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야함. 동적 계획법의 방법자체가 큰 문제의 최적해를 작은 문제의 최적해 들을 이용하여 구하기 때문에 만약 큰 문제의 최적해가 작은 문제들의 최적해들로 구성되지 않는다면 이 문제는 동적 계획법에 적용할 수 없다.

3. 분할 정복과 동적계획법의 비교

분할정복

• 연관 없는 부분 문제로 분할 한다.
• 부분문제를 재귀적으로 해결
• 부분문제의 해를 결합
• ex) 병합 정렬, 퀵 정렬

DP

• 부분 문제들이 연관이 없으면 적용할 수 없다. 부분 문제들은 더 작은 부분 문제들을 공유
• 모든 부분 문제를 한번만 계산하고 결과를 저장하고 재사용한다.

DP에는 부분 문제들 사이에 의존적 관계가 존재

DP 적용 접근 방법

1. 최적해 구조의 특성을 파악
   • 문제를 부분 문제로 나눔
2. 최적해의 값을 재귀적으로 정의
   • 부분 문제의 최적해 값에 기반하여 문제의 최적해 값을 정의
3. 상향식 방법으로 최적해의 값을 계산
   • 가장 작은 부분 문제부터 해를 구한 뒤 테이블에 저장
   • 테이블에 저장되어 있는 부분 문제의 해를 이용하여 점차적으로 상위 부분 문제의 최적해를 구한다.

4. 0-1 Knapsack

배낭 문제는 n개의 물건과 각 물건 i의 무게 w와 가치 v가 주어지고, 배낭의 용량은 W일 때, 배낭에 담을 수 있는 물건의 최대 가치를 찾는 문제이다. 단, 배낭에 담은 물건의 무게의 합이 W를 초과하지 말아야 하고, 각 물건은 1개씩만 있다.