다이나믹 프로그래밍 (Dynamic Programming; DP)
하위의 작은문제들을 풀고, 이를 이용해서 더 큰 문제를 풀어나가는 방법이다. 동적 계획법이라고도 한다.
조금 장난스럽게 말해서 답을 재활용하는 거다. 앞에서 구했던 답을 뒤에서도 이용하고, 옆에서도 이용하고…엄밀히 말해 동적 계획법은 구체적인 알고리즘이라기보다는 문제해결 패러다임에 가깝다. 동적 계획법은 “어떤 문제를 풀기 위해 그 문제를 더 작은 문제의 연장선으로 생각하고, 과거에 구한 해를 활용하는” 방식의 알고리즘을 총칭한다.
답을 구하기 위해서 했던 계산을 또 하고 또 하고 계속해야하는 류의 문제의 구조를 Optimal Substructure라고 부른다. 동적 계획법은 이런 문제에서 효과를 발휘한다.
동적 계획법의 접근 방식은 기본적으로 분할 정복 알고리즘과 비슷하다. 위에서도 설명했지만 동적 계획법을 사용하는 알고리즘 역시 주어진 문제를 부분 문제로 나누어 각 부분 문제의 답을 계산하고, 이 계산한 결과값을 이용해 원래 문제의 답을 산출하기 때문이다. 여기서 분할정복과 차이가 생기는 부분은 원래의 문제를 부분 문제로 나누는 방식에 있다. 동적 계획법의 경우 주어진 문제를 나눌 때 부분 문제를 최대한 많이 이용하도록 나눈 다음, 주어진 부분 문제의 정답을 한 번만 계산하고 저장해둔 뒤 다시 한 번 이 부분 문제를 이용할 때에는 저장해둔 정답을 바로 산출하여 이용함으로써 속도를 향상시킨다.
- 문제의 크기를 먼저 찾아야 한다.
- 큰 문제를 작은 문제로 나눠서 푸는 알고리즘. 뭔가 작게 만든다… 싶으면 다이나믹이다.
- 각 문제는 한 번만 풀어야 한다.
- Optimal Substructure를 만족하기 때문에 같은 문제는 구할 때마다 정답이 같다.
- 따라서 정답을 한 번 구했으면 정답을 어딘가에 메모(배열에 저장)해놓는다.
다음 두 가지 속성을 만족해야 다이나믹 프로그래밍으로 문제를 풀 수 있다
- Overlapping Subproblem(중복 발생 - 작은 문제가 겹치는 것)
- Optimal Substructure(한번만 구해서 그 답을 재사용)
다이나믹을 푸는 두 가지 방법
시간복잡도는 서로 같다. 자신있는 방법으로 풀자.
- Top-down(재귀)
- Bottom-up(for)