2. 다이나믹 프로그래밍(DP)

다이나믹 프로그래밍을 간단히 말하면, 주어진 문제보다 작은 문제를 풀어놓고 그것을 통해서 큰 문제를 풀어내는 방식의 알고리즘이다. 간단한 예시로는 점화식이 주어진 수열의 특정 항의 값을 구하는 문제가 있다. 잘 알려진 수열 중 피보나치 수열을 생각해보자. 피보나치 수열의 점화식은 다음과 같다.

 

$F_0=F_1=1, F_n=F_{n-1} +F_{n-2} (n \geq 2)$

 

이때 "피보나치 수열의 10번째 항($F_{10}$)을 구하시오"라는 질문에 대답하기 위해서는 종이에 "1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89"를 적게 된다. 구현 방식은 사람마다, 상황마다 다를 수 있지만 DP로 문제를 풀 때는 기본적으로 위와 같은 알고리즘을 작성하게 된다고 생각하면 편하다.

---

실제 문제를 보며 이어나가자.

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

단순히 모든 경로의 합을 구해서 비교하는 방식은, 한 층을 내려올 떄마다 경로의 개수가 2배가 되므로 매우 비효율적이다. 하지만 다음과 같은 사실을 생각해볼 수 있다.

"특정 칸에 도달하는 경로 중 합이 최대인 경로는, 직전 칸에 도달하는 경로 중 합이 최대인 경로를 포함한다."

즉 $dp[i][j]$를 '$i$번째 줄의 $j$번째 수에 도달하는 경로의 합 중 최대인 것'이라고 정의하면, 다음과 같은 점화식을 세울 수 있게 된다. (단, $tri[i][j]$는 주어진 삼각형의 $i$번째 줄에서 $j$번째 수를 의미한다.)

 

$$dp[i][j] = max(dp[i-1][j-1], dp[i-1][j])+tri[i][j]$$

 

이런 계산 방식을 사용하면 각 칸까지의 최대 합을 아주 간단하게 구할 수 있게 된다. 이 예시에서 볼 수 있듯 점화식을 세울 때는 인덱스($i$, $j$, ...)를 꼭 1개만 넣지 않아도 된다. 고등학교에서 배우는 수열과의 다른 점이라고 할 수 있다.

---

한 가지 예시를 더 살펴보자.

https://www.acmicpc.net/problem/9251

9251번: LCS

이름까지 붙어 있는 어려운 알고리즘 같지만, 잘 생각해보면 단순한 DP 문제이다. 여기서도 위 문제와 같이, 어떤 순간까지의 최선의 경우는 그 직전 순간까지의 최선의 경우를 포함한다는 사실을 관찰하면 풀 수 있다.

주어지는 두 문자열을 $a$, $b$라 하고, $dp[i][j]$를 '두 문자열의 $i$번째, $j$번째 글자까지 사용하여 만들어지는 LCS의 길이'라고 정의하자. 이때 $a[i]$와 $b[j]$가 같다면, 그 둘을 매칭시키지 않을 이유가 없다. 의심이 간다면 $a[i]$를 $b[k]$와 매칭시켰다고 가정하고$(k<j)$, $a[i]$와 $b[i]$를 매칭시켰을 때보다 더 긴 공통 부분 수열을 만들 수 있는지 생각해보면 된다. 반대로 $a[i]$와 $b[i]$가 같지 않다면, 둘 중 하나는 공통 부분 수열에 포함되지 않는다. 따라서 $dp[i-1][j]$와 $dp[i][j-1]$ 중 더 큰 것을 따르면 된다. 즉 다음과 같은 점화식을 얻을 수 있다.

 

$$dp[i][j] = \begin{cases} dp[i-1][j-1]+1 & \text{if } a[i]=b[j] \\ max(dp[i-1][j], dp[i][j-1]) & \text{if } a[i]!\neq b[j] \end{cases}$$

---

마지막으로 한 문제만 더 살펴보고 끝내자.

https://www.acmicpc.net/problem/14505

14505번: 팰린드롬 개수 구하기 (Small)

$dp[i][j]$를 '$S[i]$부터 $S[j]$ 사이의 글자들을 사용하여 만들 수 있는 팰린드롬의 개수'라고 정의하자. 이때 이러한 팰린드롬은 다음과 같이 4개로 나눌 수 있다.

 

1. $S[i]$가 포함되고 $S[j]$가 포함되지 않는 팰린드롬 - $dp[i][j-1]-dp[i+1][j-1]$가지가 존재한다.

2. $S[j]$가 포함되고 $S[i]$가 포함되지 않는 팰린드롬 - $dp[i+1][j]-dp[i+1][j-1]$가지가 존재한다.

3. $S[i]$와 $S[j]$가 모두 포함되지 않는 팰린드롬 - $dp[i+1][j-1]$가지가 존재한다.

4. ($S[i]=S[j]$인 경우) $S[i]$와 $S[j]$가 모두 포함되는 팰린드롬 - $dp[i+1][j-1]+1$가지가 존재한다. ($+1$이 들어간 이유는 이 경우에서 나올 수 있는 길이 2인 팰린드롬을 생각해보면 알 수 있다.)

 

따라서 $S[i]=S[j]$인 경우와 그렇지 않은 경우로 나눠 위 케이스를 모두 더하면 아래의 점화식을 얻게 된다.

 

$$dp[i][j] = \begin{cases} dp[i+1][j]+dp[i][j-1]+1 & \text{if } S[i]=S[j] \\ dp[i+1][j]+dp[i][j-1]-dp[i+1][j-1] & \text{if } S[i] \neq S[j] \end{cases}$$

 

예제들의 코드를 직접 짜보고 있다면 이 문제에서 막힐 수 있다. 앞 문제들의 경우 $i$와 $j$가 작을 때를 초기 조건으로 잡고, 각각을 키워나가는 for문을 이용해서 구현하는 것이 가능했던 반면 이 문제는 점화식의 형태상 그렇지 않기 때문이다. 그렇다면 어떻게 해야 할까?

 

글의 맨 윗부분을 다시 읽어보자. 다이나믹 프로그래밍은 작은 문제를 풀어놓고 그것을 이용해 더 큰 문제를 푸는 기법이다. $i$와 $j$를 점점 늘려가는 구현이 불가능한 이유는, 이 상황의 경우 $i$와 $j$가 작다고 꼭 더 작은 문제가 아니기 때문이다. $dp[1][5]$가 $dp[7][8]$보다 작은 문제라고 보기는 어렵다는 뜻이다. 하지만, 점화식의 형태를 살펴보면 항상 점화식의 우변에는 구간의 크기가 더 작은 항들이 오게 됨을 확인할 수 있다. 즉 $j-i$가 작다면 더 작은 문제라고 볼 수 있다. 따라서 이 문제를 이중 for문으로 구현하고 싶다면, 구간의 길이 $l$을 하나의 인자로, $i$를 나머지 하나의 인자로 넣는 방법이 가능하다.

 

위 예시들에서 볼 수 있듯, 다이나믹 프로그래밍으로 문제를 풀 때는 어떤 값을 점화식의 인덱스로 할지, 점화식을 어떤 방식으로 계산할지에 따라 그 효율성이 달라진다.이를 잘 판단하는 것이 어려운 DP 문제를 풀 때의 핵심이라고 할 수 있다.

---

숙제)

위에서 소개한 모든 예제 +

https://www.acmicpc.net/problem/11726 

https://www.acmicpc.net/problem/2156

https://www.acmicpc.net/problem/12865