동적 프로그래밍 (Dynamic Programming)
동적 프로그래밍은 일반적으로 최적해에 도달하기 위해 일련의 선택이 이루어지는 최적화 문제에 적용된다.
동적 프로그래밍은 어떤 부분 문제가 둘 이상의 부분적인 선택 집합에서 발생하는 경우에 효과적이다.
동적 프로그래밍의 중요한 특징은 부분 문제의 해가 다시 나타나는 경우를 대비해 그 해를 저장해두는 것이다.
동적 프로그래밍은 이미 계산된 결과를 별도의 메모리 영역에 저장하여 다시 계산하지 않는다.
동적 프로그래밍은 부분 문제가 서로 중복될 때, 즉 부분 문제가 다시 자신의 부분 문제를 공유할 때 적용할 수 있다.
동적 프로그래밍의 구현은 일반적으로 두 가지 방식으로 구성된다.
동적 프로그래밍 알고리즘을 개발할 때는 다음 4단계를 따른다.
- 최적해의 구조의 특징을 찾는다.
- 최적해의 값을 재귀적으로 정의한다.
- 최적해의 값을 일반적으로 상향식(bottom-up) 방법으로 계산한다.
- 계산된 정보들로부터 최적해를 구성한다.
1. 최적 부분 구조
동적 프로그래밍을 이용해 최적화 문제를 풀기 위해서 가장 먼저 최적해의 구조의 특징을 파악해야 한다. 문제의 최적해가 그 안에 부분 문제의 최적해를 포함하고 있을 때 그 문제는 최적 부분 구조(Optimal Substructure)를 가진다. 어떤 문제가 최적 부분 구조를 가진다는 것은 동적 프로그래밍이 적용될 수 있다는 것을 의미한다. 따라서 고려하고 있는 부분 문제가 최적해를 구하는 데 사용되는 부분 문제를 모두 포함하는지 확인해야 한다.
2. 중복되는 부분 문제
동적 프로그래밍을 적용하기 위해 최적화 문제의 부분 문제들의 범위가 작아야 한다. 재귀 알고리즘을 사용하면 항상 새로운 부분 문제를 계속 만들어 풀기보다는 같은 문제를 반복해서 풀게 된다는 것을 의미한다. 재귀 알고리즘이 같은 문제를 반복해서 풀게 되는 경우, 그 최적화 문제가 중복되는 부분 문제(Overlapping Subproblems)를 가진다. 분할정복 기법을 사용하기에 적합한 문제는 재귀적으로 호출하는 매 단계마다 중복되지 않는 새로운 문제를 만들지만 동적 프로그래밍은 중복되는 부분 문제를 이용한다.
메모이제이션 (Memoization)
메모이제이션은 동적 프로그래밍을 구현하는 방법 중 하나로 한 번 계산한 결과를 메모리 공간에 메모하는 기법이다. 같은 문제를 다시 호출하면 메모했던 결과를 다시 호출한다.
