[Algorithm] 다이나믹 프로그래밍

내가 생각하는 다이나믹 프로그래밍 문제 풀이 과정은 다음과 같다.

한 단계 한 단계 살펴보며 디테일한 사항들을 확인하자.

1) DP 문제임을 인지한다

우선 첫 번째로 내가 풀려하는 문제가 DP 문제임을 인지해야 한다. DP 문제를 풀 때 다음과 같은 생각이 들면 DP 문제임을 의심하자.

🙇🏻‍♂️ 음, 이 문제를 어떻게 풀까? 완전 탐색 알고리즘으로 접근해 볼까? (완전 탐색 알고리즘으로 접근해 본다) 헉! 이러면 시간이 너무 많이 걸리는데? 메모리가 너무 많이 사용되는데?

해를 구하기에 시간 혹은 메모리 공간이 매우 많이 필요하다

🙇🏻‍♂️ 음, 이 문제를 어떻게 풀까? 이렇게 풀면 되려나?. 먼저 이 걸 구하고, 그 다음 이 걸 구하고, 그 다음 .. 어 ?.. 이거 구했던 건데..

중복되는 연산이 많다

2) DP 테이블을 ‘잘’ 정의한다.

DP 문제를 푸는 과정에서 가장 어렵고 가장 중요한 단계이다. 나동빈님은 DP 문제의 특징을 다음과 같이 정의했다.

🎯 1. 큰 문제를 작은 문제로 나눌 수 있다

🎯 2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다

여기서 문제 라는 단어가 다소 추상적일 수 있다. 나는 문제를 정의한다는 것 은 DP 테이블의 각 인덱스에 해당하는 값들의 의미를 정의한다는 것과 같다고 생각한다.

DP 문제에서 작은 문제의 정답은 그것을 포함하는 큰 문제에서 사용이 가능하다. 이 때 우리는 DP 테이블의 특정 인덱스의 값을 구하기 위해 다른 인덱스의 값을 사용할 수 있도록 그 의미를 잘 정의해야 한다.

이것을 여실히 보여주는 문제가 있어서 소개한다. 바로 백준 #14501 퇴사 [링크] 이다.

맨처음에 해당 문제를 풀 때 DP[i] 의 의미를

첫 번째 날부터 i 번째 날 까지 낼 수 있는 최대 이익 이라고 정의하였다.

이렇게 정의하였을 때 점화식을 세우기 다소 어렵다. 하지만 DP[i] 의 의미를

i 번째 날 부터 마지막 날까지 낼 수 있는 최대 이익 이라고 정의하면, 다른 DP[인덱스] 를 이용할 수 있게 된다.

이처럼 DP 테이블을 잘 정의하는 것은 매우 중요하다.

3) 해에 대응하는 DP 테이블 원소 규정

이 단계는 직전의 DP 테이블을 잘 정의하는 단계와 거의 동시에 진행되어야 한다.

앞선 문제 예시에서, DP[i] 의 의미를

첫 번째 날부터 i 번째 날 까지 낼 수 있는 최대 이익 이라고 정의했을 때는 DP[N] 이 최종 정답이다.

한 편, i 번째 날 부터 마지막 날까지 낼 수 있는 최대 이익 이라고 정의하면 DP[0] 이 최종 정답이다.

이처럼 항상 DP 테이블의 마지막 원소가 정답일 거라고 생각하지 말고, 정답에 대응하는 원소를 잘 찾길 바란다.

4) 점화식을 세운다

점화식은 알아서 잘 세우길 바란다. 이 단계에서는 점화식을 세운 후에 유의점에 대해서 이야기 해보겠다.

1. 초기 항은 dp 테이블에 직접 입력해야 할 수도 있다

2. 점화식을 다 세웠다면 탑다운으로 코드를 구현할지 바텀업으로 구현할지 생각하자

3. 바텀업으로 구현할 계획이라면 dp 테이블을 참조하는 과정에서 segmentation fault 가 발생할 수 있음을 유의하자

4. Dp[i] = f(Dp[i-k], …) 라고 세울 수도 있고 Dp[i+k] = f(Dp[i], …) 라고 세울 수도 있다

코드는 알아서 잘 세우고 짜길 바란다.

---

한편, DP와 분할정복 알고리즘 모두 큰 문제를 작게 나누어 푸는 방법이다. 차이점은 다이나믹 프로그래밍은 문제들이 서로 영향을 미친다는 것이다. 즉 한 번 해결했던 문제를 다시금 해결해야 하는 상황이 발생한다. 하지만 분할정복 알고리즘의 경우 한 번 해결한 작은 문제를 다시 해결할 일은 없다.