[알고리즘] 동적계획법(Dynamic Programming)

• 동적계획법 : 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘
• 최적화 문제는 최대값이나 최소값 혹은 경우의 수 등과 같은 최적값을 구하는 문제이다.
• 동적계획법은 먼저 작은 부분 문제들의 해들을 구하고 이들을 이용하여 보다 큰 크기의 부분문제들을 해결하여, 최종적으로 원래 주어진 문제를 해결하는 알고리즘 설계 기법이다.

---

동적계획법은

중복 부분문제 구조, 최적 부분문제 구조

이 두 요건을 모두 만족해야만 사용할 수 있다.

 

- 최적 부분문제 구조

: 어떤 문제에 대한 해가 최적일 때 그 해를 구성하는 작은 문제들의 해 역시 최적이어야 한다.

 

- 중복 부분문제 구조

: 큰 문제를 이루는 작은 문제들을 먼저 해결하고 작은 문제들의 최적 해를 이용하여 순환적으로 큰 문제를 해결한다.

-> 점화식 사용

이전에 계산했던 작은 문제들의 해를 재계산 하지 않기 위해 어딘가에 저장해놓고 필요할 때 사용한다.

---

그렇다면 분할정복과 DP 의 차이점은?

- 분할 정복 : 연관없는 부분 문제로 분할하여 부분문제를 재귀적으로 해결하고 그 해들을 결합한다.

                같은 부분문제가 나타날 경우 다시 계산한다.

                하향식 방법으로 접근

                 ex) 병합 정렬, 퀵 정렬

 

- DP : 부분문제들은 더 작은 부분 문제들을 공유한다. 모든 부분 문제를 한 번만 계산하고 결과를 저장하여 재사용한다.

        상향식 방법으로 접근.

        하향식 + memoization 으로 접근하는 것도 괜찮다.

---

DP 적용 접근 방법

1. 최적해 구조의 특성을 파악하라. -> 문제를 부분 문제로 나눈다.

2. 최적해의 값을 재귀적으로 정의하라 -> 부분 문제의 최적해 값에 기반하여 문제의 최적해 값을 정의한다.

3. 상향식 방법으로 최적해의 값을 계산하라.

    -> 가장 작은 부분 문제부터 해를 구한 뒤 테이블에 저장한다.

    -> 테이블에 저장되어 있는 부분 문제의 해를 이용하여 점차적으로 상위 부분 문제의 최적해를 구한다.