[Introduction to Algorithms] 동적 프로그래밍

 

1) 동적 프로그래밍이란?

- 동적 프로그래밍은 분할정복 기법과 같이 부분 문제의 해를 결합해 문제를 해결한다

  분할정복 알고리즘은 문제를 서로 겹치지 않는(disjoint) 부분 문제로 분할하고,

  해당 부분 문제를 재귀적으로 해결한 후,  해결 결과를 결합하여 원래의 문제를 해결한다. 

 

- 반면, 동적 프로그래밍은 부분 문제가 서로 중복될 때, 즉, 부분 문제가 다시 자신의 부분 문제를 공유할 때 적용할 수 있다.

  이 경우, 분할정복 알고리즘은 공유되는 부분 문제를 반복적으로 해결하여 일을 필요 이상으로 더 많이 하게 된다.

  동적 프로그래밍 알고리즘을 이용하면 모든 부분 문제를 한 번만 풀어 

  그 해를 테이블에 저장함으로써 그 해를 테이블에 저장함으로써 

  각 부분 문제를 풀 때마다 다시 계산하는 일을 피할 수 있다. 

 

 

2) 동적 프로그래밍의 활용

 

- 일반적으로 최적화 문제(Optimization Problem)에 동적 프로그래밍을 적용한다.

  이런 문제는 다양한 해를 가질 수 있다.

  각 해는 값을 가져 이 중 최적(최소 또는 최대)의 값인 해를 찾기를 원한다.

  이런 해를 그 문제에 대한 유일한 최적해라 하지 않고 한 개의 최적해라 한다.

  최적의 값을 가지는 해가 여러 개 존재할 수 있기 때문이다.

  프로그래밍 알고리즘을 개발할 때는 다음 4단계를 따른다. 

 

1. 최적해의 구조의 특징을 찾는다

2. 최적해의 값을 재귀적으로 정의한다.

3. 최적해의 값을 일반적으로 상향식(bottom-up) 방법으로 계산한다

4. 계산된 정보들로부터 최적해를 구성한다. 

 

- 1~3단계는 주어진 한 문제에 대한 동적 프로그래밍 해의 기초가 된다.

  4단계는 최적해 자체는 필요 없고 최적해의 값만 필요할 경우 생략할 수 있다.

  4단계를 수행할 경우, 최적해를 쉽게 구성하기 위해 3단계에서 부가적인 정보를 유지하기도 한다. 

 

 

3) 동적 프로그래밍 문제들

 

- (1) 막대 하나를 더 작은 막대 여러 개로 나누어 총 가치가 최대가 되도록 하는 문제

  (2) 일련의 행렬을 곱할 때 스칼라 곱의 전체 횟수를 최소화하는 곱 순서

  (3) 두 개의 시퀀스에서 최장 공통 부분 시퀀스(Longest Common Subsequence)를 

  (4) 검색할 키들의 분포가 주어졌을 때, 

       동적 프로그래밍을 이용해 최적인 이진 검색 트리(binary search tree)를 만들기