다이내믹이라고 할지 다이나믹이라고 할지 참 고민이 된다...
다이나믹 프로그래밍은 정말 많은 곳에 쓰이며, 정말 유용하고 때로는 정말 '다이나믹'하게 어렵기도 하다.
문제를 풀다보면 다이나믹 프로그래밍으로 풀리는 문제들에 대한 느낌 같은 것이 있다. 주로 연속된 정점들이 각각 동일한 옵션을 가질 때이다. 옵션이 m이고 정점의 갯수가 n이라면, 모든 케이스를 완전 탐색하기 위해 O(m^n) 이 걸릴 것 같은 문제들.
하지만 다이나믹 프로그래밍은 이것을 O(nm) 에 해결해준다.
즉, 각 옵션이 행이 되고, 각 정점들이 열에 배치되는 형태가 된다. 각 정점에서 어떤 옵션을 택했을 때 어떤 결과가 되는지를 기록해 나가는 것이다. 그리고 중요한 점은 그 결과들이 누적될 때 어떻게 처리해야 하는지이다.
필자가 생각하는 이러한 힘은 '메모'에서 온다고 본다. 어떠한 규칙에 의해 메모를 매번 작성해주어서 다시 돌아가지 않아도 되게 하는 것이다. 실제로 메모이제이션이라고 부르지만 더 직관적으로 보기 위해 '메모'라고 칭했다. 마치 어두운 산속에서 자신이 지나온 길에 있는 나무에 표시를 해두는 것처럼, 특정 정점을 지날 때마다 그 곳에 메모를 해두면(최적값) 중간중간 지나온 정점들에 대한 조건이 바뀌었더라도 다시 시작하지 않을 수 있는 것이다.
한 가지 예시를 들어보자.
2, 3, 5, 9, 1, 6 숫자들이 주어졌다. 여기서 3개를 골라 만들 수 있는 최대값을 구한다고 하자.
물론 정렬한 후에 3개만 고르면 쉽게 끝나겠지만, DP로 풀어보자.
매 정점에서 우리는 이 수를 고를 지 안 고를지를 선택해야 한다. 하지만 여기에 한가지 옵션이 더 있다. 바로 몇개의 수를 더 했느냐이다. 즉 사실 매 정점에서 우리가 선택할 수 있는 옵션은 3가지이다.
- 이 수를 선택한다 (현재까지 1개 선택)
- 이 수를 더해준다 (현재까지 2개 선택)
- 이 수를 더해준다 (이제 총 3개 선택 - 완료)
매 정점에서 3가지의 옵션이 있고, 정점에 6개(총 6개의 숫자)이므로 일일이 따져본다면, 3^6=729번의 연산을 해야 한다.
하지만 DP는 이것을 단 18번(3 곱하기 6)의 연산으로 끝낸다.
아래의 표를 보자. 상단에는 주어진 수 (2, 3, 5, 9, 1, 6)이 있고, 좌측에는 옵션들이 있다.
| 2 | 3 | 5 | 9 | 1 | 6 | |
| 1 | 2 | |||||
| 2 | 2 | |||||
| 3 | 2 |
가장 먼저 2에서 시작했을 때, 1개만 선택 가능하므로, 해당 열에 모두 2를 넣어준다. (노랑색 표시)
이제 각 셀의 의미는 첫번째 정점인 2에 대해 1번 값을 더했을 때의 최대값, 2번 ...최대값, 3번... 최대값이 된다!
그럼 이제 다음 정점 3에 왔을 때를 보자.(주황색 표시)
| 2 | 3 | 5 | 9 | 1 | 6 | |
| 1 | 2 | 3 | ||||
| 2 | 2 | 5 | ||||
| 3 | 2 | 5 |
처음에는 2와 비교를 해야 한다. 하나만 더했을 때의 최대값은 3이 2보다 크므로 갱신이 일어난다.
이제 3정점에서의 2행에는 앞선 정점2에서의 1행값 2에 3을 더해주고 (2+3), 정점2에서의 2행값 2와 비교하여 갱신해준다. 그러면 이 셀의 의미는 정점3까지 오면서 2개의 수를 선택하여 만들 수 있는 값들 중 최대값이 되는 것이다. 이 말은 이제 앞선 정점들에서 수를 더했든 안더했든 (어떠한 옵션을 선택했든) 지나온 자리마다 최적값(이번 예제에서는 최대값)이 기록되어 있으므로, 처음부터 연산을 다시하지 않아도 된다는 것이다.
이제 완성된 표는 다음과 같다.
| 2 | 3 | 5 | 9 | 1 | 6 | |
| 1 | 2 | 3 | 5 | 9 | 9 | 9 |
| 2 | 2 | 2+3 | 3+5 | 5+9 | 5+9 > 9+1 | 6+9>5+9 |
| 3 | 2 | 2+3 | 2+3+5 | 3+5+9 | 3+5+9>5+9+1 | 5+9+6 |
위의 완성된 표를 보면 정점9에 도달했을 때, 그 앞선 정점 5에서 2+3+5이던 값이 3+5+9로 갱신되었다. 즉 정점5까지 올때는 2+3+5가 만들 수 있는 합들 중 가장 큰 값이었지만, 9가 추가되면서 3+5+9로 갱신된 것이다. 하지만 어떻게 바로 최대값 3+5+9 를 찾았을까? 그것은 바로 정점5에 2행에 담겨진 3+5덕분이다. 정점5의 2행에 2가지 수로 만들 수 있는 최대합이 기록되어있기에 거기에 9만 더하고 앞선 값과 비교해주면 되는 것이다. 그리고 정점 1에서는 9+1이 5+9보다 크지 않기에 갱신되지 않았고, 마찬가지로 5+9+1도 기존 최대값보다 작다.
이렇게 마지막 정점 6까지 탐색하면 최대값은 20임을 구할 수 있다.
i가 정점번호, j를 옵션번호, 각 정점을 이루는 수들이 담긴 배열을 arr라고 할 때,
매 정점에서는 DP[i][j]=max(DP[i-1][j], DP[i-1][j-1]+arr[i]) 의 점화식을 갖게 된다. 물론 i-1이나 j-1의 범위에는 주의한다.
이제 같은 수들이 순서만 다르게 주어졌다면 어떨까? 아래의 표를 보자
| 2 | 1 | 9 | 5 | 3 | 6 | |
| 1 | 2 | 2 | 9 | 9 | 9 | 9 |
| 2 | 2 | 3 | 11 | 14 | 14 | 15 |
| 3 | 2 | 3 | 12 | 16 | 17 | 20 |
중간중간 기록된 값들은 조금 다르지만, 결국 마지막에는 20으로 끝난다.
다이나믹 프로그래밍으로 문제를 해결하는 가장 쉽고 기본적인 예제를 들어봤다. DP에는 자주 보이는 유형들도 있고, 정말 기막힌 방법으로 적용하는 경우들도 많지만, 대개 위와 같은 핵심 원리에 의해 동작하게 된다: 정점들이 순서대로 연결되어있고, 점프없이 하나씩 순회하면서 진행할 때, 최적의 값을 기록하는 방식.
<연습문제>
백준 11726 2xn 타일링 - dp의 직전값만 보는 것이 아니라 i-1, i-2 2개를 참조하는 방식
백준 11727 2xn타일링 2 - dp의 직전값만 보는 것이 아니라 i-1, i-2 2개를 참조하는 방식, 위와 같으나 약간의 추가 처리가 필요.
백준 2293 동전 1 - 각 동전으로 케이스를 계속 누적하는 방식
백준 1633 - 3중 루프로 최대값 찾아나가는 방식
백준 9657 돌 게임 3 - 주어진 돌의 가지 수만큼 이전 값을 확인하여 승리할 수 있는 방법을 찾는 방식 (개인적으로 꼭 한번 풀만한 문제)
백준 9658 돌 게임 4 - 위의 돌 게임 3이 되면 이것도 가능함.
타일링 문제가 직전 2개의 이전 값을 참조했다면, 동전 문제와 돌 게임 문제들은 동전의 종류, 돌을 몇개 가지고 오는지 등에 따라 얼마 이전의 값을 참조할 지가 결정된다고 할 수 있다. 그리고 몇개의 이전 값을 봐야하는지도.
