점화식
메모이제이션(memoization)
- 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술
- 동적 계획법의 핵심이 되는 기술
- 추가적인 메모리 공간이 필요
- 재귀 함수 호출로 인한 시스템 호출 스택을 사용하게 되고 실행 속도 저하 또는 오버플로우가 발생할 수 있음
동적 계획 알고리즘
- 그리디 알고리즘과 같이 최적화 문제를 해결하는 알고리즘
- 최적화 문제 : 최적(최대값이나 최소값 같은) 값을 구하는 문제
- 해당 문제에 여러 해가 있을 수 있다.
- the 최적해를 구하는 것이 아니라 an 최적해를 구하는 것
- 먼저 작은 부분 문제들의 해들을 구하고 이를 이용하여 보다 큰 크기의 부분 문제들을 해결하여, 최종적으로 원래 주어진 문제를 해결하는 알고리즘 설계 기법
- 동적 계획법을 적용하려는 문제는 필히 다음과 같은 요건을 가지고 있어야 함
- 중복 부분문제 구조(Overlapping subproblems)
- 최적 부분문제 구조(Optimal substructure)
- 중복 부분문제 구조(Overlapping subproblems)
- DP는 큰 문제를 이루는 작은 문제들을 먼저 해결하고 작은 문제들의 최적 해(Optimal Solution)를 이용하여 순환적으로 큰 문제를 해결
- 순환적인 관계(recurrence relation)를 명시적으로 표현하기 위해서 동적 계획법에서는 일반적으로 수학적 도구인 점화식을 사용
- DP는 문제의 순환적인 성질 때문에 이전에 계산되어졌던 작은 문제의 해가 다른 어딘가에서 필요하게 되는데(Overlapping subproblems), 이를 위해 DP에서는 이미 해결된 작은 문제들의 해들을 어떤 저장 공간(table)에 저장하게 됨
- 그리고 이렇게 저장된 해들이 다시 필요할 때마다 해를 얻기 위해 다시 문제를 재계산하지 않고 table의 참조를 통해서 중복된 계산을 피하게 됨
- 최적 부분문제 구조(Optimal substructure)
- 동적 계획법이 최적화에 대한 어느 문제에나 적용될 수 있는 것은 아니다. 주어진 문제가 최적의 원칙(Principle of Optimality)을 만족해야만 동적 계획법을 효율적으로 적용할 수 있다
- 최적화의 원칙
- 어떤 문제에 대한 해가 최적일 때 그 해를 구하는 작은 문제들의 해 역시 최적이어야 한다.
- 동적 계획법의 방법 자체가 큰 문제의 최적 해를 작은 문제의 최적해들을 이용하여 구하기 때문에 만약 큰 문제의 최적해가 작은 문제들의 최적화의 해들로 구성되지 않는다면 이 문제는 동적 계획법을 사용할 수 없다.
분할 정복과 동적 계획법의 비교
- 분할 정복
- 연관 없는 부분 문제로 분할함
- 부분 문제를 재귀적으로 해결함
- 부분 문제의 해를 결합(combine)함
- 예) 병합정렬, 퀵정렬
- 동적 계획법
- 부분 문제들이 연관이 없으면 적용할 수 없음
- 즉, 부분 문제들은 더 작은 부분 문제들을 공유함
- 모든 부분 문제를 한 번만 계산하고 결과를 저장하고 재사용한다
- 분할 정복은 같은 부분문제가 나타날 경우 다시 계산한다
- DP에는 부분 문제들 사이에 의존적 관계가 존재함
- 이러한 관계를 문제에 따라 다르고, 대부분의 경우 뚜렷이 보이지 않아서 합축적인 순서(implicit order)라고 함
- 분할 정복은 하향식 방법으로, DP는 상향식 방법으로 접근
3단계 DP 적용 접근 방법
- 최적해 구조의 특성을 파악하라
- 최적해의 값을 재귀적으로 정의하라
- 부분 문제의 최적해 값에 기반하여 문제의 최적해 값을 정의한다
- 상향식 방법으로 최적해의 값을 계산하다
- 가장 작은 부분 문제부터 해를 구한 뒤 테이블에 저장한다
- 테이블에 저장되어 있는 부분 문제의 해를 이용하여 점차적으로 상위 부분 문제의 최적해를 구한다
