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

메모이제이션 (memoization)

컴퓨터 프로그램을 실행할 때, 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여

전체적인 실행속도를 빠르게 하는 기술이다.

 

 

동적 계획법 (Dynamic Programming)

동적 계획법(Dynamic Programming)은 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘이다.

 

먼저 작은 부분 문제들의 해들을 구하고 이들을 이용하여 보다 큰 크기의 부분 문제들을 해결하여,

최종적으로 원래 주어진 문제를 해결하는 알고리즘 설계 기법이다.

 

큰 크기 문제 -> 작은 크기 문제

해결방법이 동일하게 적용되는지 확인한다.

 

💡 요건

중복 부분문제 구조

최적 부분문제 구조

 

 

💡 최적 부분문제 구조 (Optimal substructure)

 

동적 계획법은 주어진 문제가 최적화의 원칙 (Principle of Optimality)을 만족해야만 동적 계획법을 효율적으로 적용할 수 있다.

 

최적화의 원칙?

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

동적 계획법의 방법자체가 큰 문제의 최적 해를 작은 문제의 최적해 들을 이용하여 구하기 때문에 

만약 큰 문제의 최적해가 작은 문제들의 최적해들로 구성되지 않는다면 이 문제는 동적 계획법을 적용할 수 없다.

 

 

💡 중복 부분문제 구조 (Overlapping subproblems)

 

- DP는 큰 문제를 이루는 작은 문제들을 먼저 해결하고 작은 문제들의 최적 해(Optimal Solution)를 이용하여 순환적으로 큰 문제를 해결한다. (순환적인 관계를 명시적으로 표현하기 위해서 점화식을 사용한다.)

 

- 문제의 순환적인 성질 때문에 이전에 계산되어졌던 작은 문제의 해가 다른 어딘가에서 필요하게 되는데(Overlapping subproblems) 이를 위해 DP에서는 이미 해결된 작은 문제들의 해들을 어떤 저장 공간(table)에 저장하게 된다.

 

- 이렇게 저장된 해들이 다시 필요할 떄 마다 해를 얻기 위해 다시 문제를 재계산하지 않고 table의 참조를 통해서 중복된 계산을 피하게 된다.

 

 

💡 DP 적용 접근 방법 3단계

 

1. 최적해 구조의 특성을 파악

문제를 부분 문제로 나눈다.

 

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

부분 문제의 최적해 값에 기반하여 문제의 최적해 값을 정의한다.

 

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

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

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