동적 계획법을 최적화하는 9가지 방법 (4/4)

9. Dynamic Tree DP

Dynamic Tree DP는 특수한 형태의 Tree DP를 최적화할 수 있는 방법으로, 일반적인 직선에서 행렬과 같은 구조를 사용하여 DP를 최적화하는 것과 비슷한 방식이다. 사실 Tree DP가 아니라 일직선에서 하는 DP 문제라 하더라도 최적화 방법이 자명하지 않기 때문에, 이 글에서는 먼저 일직선에서의 DP 최적화를 먼저 설명한다. (일직선에서의 이러한 DP 최적화를 부르는 말은 잘 모른다.)

In Line

다음과 같은 문제를 생각해 보자.

• Problem. 길이 $N$ 의 배열이 있을 때, 다음 두 연산을 쿼리당 $O(\log N)$에 계산하여라.
  • 원소 갱신: $A[x] := v$
  • 최대 부분합 쿼리: 부분배열을 골라, 그 안의 원소 합을 최대화하여라. 즉, $Max_{i\le j}{\sum_{x=i}^{j} A[x]}$ 를 계산하라.

이 문제는 Segment tree를 사용하여 $O(\log N)$ 에 계산할 수 있음이 잘 알려져 있다. $[l \ldots r]$ 구간을 대표하는 노드에 다음 4개의 정보를 저장하면 된다:

• 구간 전체 합
• 구간 내 최대합 부분배열
• $A[l]$ 을 포함하는 최대합 부분배열
• $A[r]$ 을 포함하는 최대합 부분배열

이 4개의 정보를 저장할 경우, 왼쪽과 오른쪽에서 해결한 문제의 정답을 $O(1)$ 시간에 합쳐줄 수 있어서 Segment tree를 사용하여 문제를 해결할 수 있다.

이러한 식의 해결 방법을 일반화 해 보자. 다음과 같은 DP 점화식이 있다고 하자:

• $DP[i][j] = min_{k}(DP[i-1][k] + Cost[i][k][j])$

이러한 형태의, 일종의 "행렬" 로 표현되는 DP는 다양한 상황을 모델링할 수 있다. 예를 들어 위에서 설명한 최대 부분합 문제 역시 동일한 형태로 DP 식을 써 줄 수 있다. 배열 전체를 두고 봤을 때, 최대 부분합 배열은 원소를 고른 부분 배열 안에 넣고 싶은지, 그 왼쪽/오른쪽에 넣고 싶은지를 결정하는 문제라고 볼 수 있다. 즉, 예를 들어 $N = 10$ 인 배열에서 $[2 \ldots 5]$ 부분배열을 골랐다면, $[1 \ldots 1]$ 은 고른 배열 왼쪽이라고 하고, $[2 \ldots 5]$ 는 고른 배열, $[6 \ldots 10]$ 은 고른 배열 오른쪽이라고 할 수 있다. 이들 각각을 0/1/2 라고 번호를 매기면, 우리는 배열의 각 원소에

• 0/1/2 라는 번호를 매김
• 매긴 번호는 감소하지 않아야 함 (1 오른쪽에 0, 2 오른쪽에 0 1 이 오는 것 불가능)
• 1을 매겼을 경우 $A[x]$ 의 이득이 있고 아닐 경우 이득은 0

와 같이 번호를 매기는 문제가 최대 부분합 문제라고 생각할 수 있다. 이러한 경우

$Cost[i][j][k] = \begin{cases} \infty &\quad\text{if }j > k\newline
0 &\quad\text{if }k \neq 1\newline
-A[i] &\quad\text{otherwise.} \
\end{cases}$

라는 식을 사용하면 위 최대 부분합 DP를 위와 같은 점화식으로 환원할 수 있다. (min으로 써서 부호는 편의상 음수) 그 외에도 이러한 식으로 환원할 수 있는 문제가 여럿 있으니, 생각해 보면 좋을 것이다.

이제 위 문제의 일반화된 변형을 생각해 보자.

• Problem. 길이 $N \times M \times M$ 의 3차원 배열이 있을 때, 다음 두 연산을 쿼리당 $O(\log N)$에 계산하여라.
  • 원소 갱신: $Cost[i][j][k] := v$
  • DP 값 확인: $DP[n][i]$ 의 값을 모든 $0 \le i \le M-1$ 에 대해서 구하여라.

처음 설명한 최대부분합 문제와 비슷한 접근법을 사용하자. 먼저, 이 문제 역시 일종의 "최적 경로 찾기" 문제의 종류라고 불 수 있다. $(N + 1) \times M$ 격자를 그린 후, $Cost[i][j][k]$ 를 $(i-1, j) \rightarrow (i, k)$ 로 가는 간선의 비용이라고 보면, 결국 $DP[n][i]$ 는 모든 $x$ 에 대해 $(0, x) \rightarrow (n, i)$ 로 가는 최단경로의 길이라고 생각할 수 있다. 이렇게 되면, 내가 점 $(l-1, j) \rightarrow (r, k)$ 로 가기 위해서는, $mid = \lceil \frac{l + r}{2} \rceil$ 에 있는 점 $(mid, 0), (mid, 1), \ldots, (mid, M - 1)$ 중 하나를 거쳐야 함을 알 수 있다. 고로, $ShortestPath[l \rightarrow r][i][j]$ 를 $(l-1, i) \rightarrow (r, j)$ 로 가는 최단 경로의 길이라고 보면,

$ShortestPath[l \rightarrow r][i][j] = min_{k = 0}^{M-1}(ShortestPath[l \rightarrow mid][i][k] + ShortestPath[(mid + 1) \rightarrow r][k][j])$

눈치빠른 독자들은 벌써 다음에 무엇이 나올지 예측했을 것이다. $[l \ldots r]$ 구간을 대표하는 노드에, $(l-1, i) \rightarrow (r, j)$ 로 가는 최단 경로의 길이를 $M \times M$ 의 행렬 형태로 저장하자. 이렇게 될 경우 $[l \ldots l]$ 구간에 대한 행렬은 그냥 $Cost[i]$ 행렬이 되고, 더 큰 구간에 대한 행렬은 $Merge[i][j] = Min_{k=0}^{M-1}(L[i][k] + R[k][j])$ 와 같이 계산해 줄 수 있다. 고로 노드 하나를 계산하는데 $O(M^3)$ 시간이 걸리고, 이는 위 문제를 각 쿼리당 $O(M^3 \log N)$ 에 풀 수 있다는 것을 뜻한다. 즉, $M = O(1)$을 가정할 수 있다면, 위 문제는 $O(\log N)$ 에 해결되는 것이다.

이 글에서는 정확히 행렬 형태만 해결할 수 있는 추상적인 모델만을 언급했으나, 실제로는 정확히 행렬을 가지고 다닐 필요는 없다. 예를 들어 최대 구간합을 원래 구하는 방식처럼 $3 \times 3$ 행렬이 아니라 4개의 정수 값만 가지고 다니는 접근이 일반적으로 가능하다. 문제에 따라서 구현의 간단함, 상수 문제 (노드 당 27~64개의 연산은 정말 비싸다), 혹은 문제에서 요구하는 특수한 성질들로 인해서 행렬을 갖고 다니는 것보다 이러한 ad-hoc한 구조를 갖고 다니는 게 좋을 수 있다. 고로 무조건 "행렬 형태로 환원해야만 한다" 와 같이 닫힌 생각을 하는 것은 위험할 수 있다.

문제를 해결한 방식에 의해, 다음과 같은 "구간 쿼리" 역시 자연스럽게 처리할 수 있음을 기억하자.

• 구간 DP 값 확인: 배열에서 $l \le i \le r$ 인 구간만 확인한다고 하였을 때, $DP[r-l+1][i]$ 의 값을 모든 $0 \le i \le M-1$ 에 대해서 구하여라.

이러한 DP를 계산하는 방법은 구간에 대한 행렬 곱을 관리하는 것과 굉장히 유사하다. 실제로 min-plus algebra라고 이러한 형태의 행렬에 대한 수학적인 모델이 있다고 알고 있으나, 이 부분은 내가 잘 모르는 내용이고, 이러한 내용을 전혀 모르더라도 문제를 해결하는 데 지장이 없으니 이 글에서는 이름만 언급하고 넘어간다.

Practice problems

• KOI 2015 중등부 4번. 금광
• USACO Dec13 Gold. Optimal Milking
• 서울대학교 2019. 여우 퀴즈
• SEERC 2019. Max or Min
• 고려대학교 2019. 실시간 내비게이션
• CEOI 2019. Dynamic Diameter (아래 적혀 있는 트리에서의 최적화를 사용하지 않고 해결해보자!)
• JOI Camp 2018. Wild Boar (Challenge problem)

In Tree

위 DP 점화식을 트리용으로 일반화 해 보자. 대략 다음과 같은 형태를 생각할 수 있다.

• $DP[i][j] = \sum_{v \in son(i)} min_{k}(DP[v][k] + Cost[v][k][j])$

위와 같은 점화식으로 어떠한 문제들을 해결할 수 있을까?

• 독립 집합 (Independent Set), 정점 덮개 (Vertex Cover): 독립 집합은 $Cost[v][1][1] = -\infty$, 정점 덮개는 $Cost[v][0][0] = \infty$ 이다.

• 최대 크기 부분 서브트리: 선택한 서브트리를 1, 서브트리의 가장 높은 노드 위쪽을 2, 서브트리 아래를 0으로 두면 된다. 위에서 설명한 최대 부분합 문제와 유사하다.

• 트리의 지름: 조금 복잡하다. 지름 경로의 LCA를 2, 그 외 지름 경로를 1, 지름 경로 LCA의 조상을 3, 그 외 노드를 0으로 두면 될 것이다.

그 외에도 전형적인 트리 DP 유형 중에서는 위와 같은 점화식으로 모델링 할 수 있는 경우가 상당히 많다. 이제, Cost 배열이 바뀌었을 때 이 DP 값을 빠르게 갱신하는 방법을 알아보자.

먼저 단순한 최적화부터 시작하자. 다음과 같은 두 가지 사실을 관찰할 수 있다.

• $Cost[v]$ 의 값이 갱신될 경우, $v$ 의 조상인 정점들만 DP 값이 변화한다. 고로, 이 조상들에 대해서만 재계산을 해 주면 된다. $Cost[v]$ 의 값이 갱신될 때, $v$ 의 부모에서부터 올라가면서 DP 값을 위 식대로 계산해 주면, 전체 노드를 순회할 필요 없이 재계산이 가능하다. 이렇게만 해 줘도 트리가 Full binary tree일 경우 이미 문제가 해결된다. 하지만, 깊이가 낮은 트리에서 전부 문제가 해결된 것은 아니다. 예를 들어 트리의 모든 정점의 루트랑 인접한 성게(star graph) 의 경우, 갱신해야 할 정점은 최대 1개지만 해당 정점을 갱신할 때 모든 자식을 돌기 때문에 여전히 비효율적이다.
• $DP[v][]$의 값이 어떠한 자식 DP값 $DP[w][]$ 의 변화로 인해서 재계산이 필요할 때, 이 자식에 대한 변홧값만 갱신해주면 된다. 결국 자식에 대한 합의 형태이니, 합에서 갱신 전 DP 값을 빼 주고, 갱신 후 DP 값을 더해주기만 해도 된다. 만약에 $DP[v]$ 의 값이 합이 아니라 최소/최댓값으로 결정된다면, 각 DP 테이블 값에 대응되는 Heap 자료구조를 관리하는 식으로 똑같은 연산을 할 수 있다.

여기까지 할 경우, DP 값을 갱신하는 데 걸리는 시간은 순전히 조상으로 가는 경로의 길이에 좌우된다. 이는 또한 트리가 일직선에 가까운 모양일 때 문제가 생김을 뜻한다. 한편으로, 우리는 위에서 일직선에서 이러한 DP 문제를 어떠한 식으로 해결하는 지를 알아보았다. 이러한 상황에서는 일반적으로 HLD가 매우 유용하다. HLD를 사용하면 부모로 올라가는 경로를 $O(\log N)$ 개의 일직선으로 분해할 수 있으니, Light edge에서 값이 올라가는 상황을 잘 처리해 주면 문제가 해결된다.

이를 위해, 먼저 Heavy edge와 Light edge 상에서 일어나는 일을 따로 처리해주자. Heavy edge는 하나의 일직선 체인 안에 있으니, 위에서 사용한 직선 풀이의 방법을 그대로 사용해서 각 체인에 대한 세그먼트 트리를 사용해 주면 될 것이다. 이렇게 되면, 각 정점으로 들어오는 Light edge에 대한 DP 값을 모을 수 없으니, 각 정점 $v$ 에 대해서, "해당 정점의 light edge 자식들의 DP 값 합" 을 저장해 주자 (합이 아니라 최소일 경우 heap 등으로 관리한다). 위에서 DP 값의 갱신을 $O(deg(v))$ 보다 빠르게 하기 위해서 사용했던 기법과 동일하다.

이렇게 값을 모아주면, 해당 정점에 어떠한 상태를 매겼을 때 이에 따라서 지불해야 하는 비용을 바로 알 수 있다. 이를 $Slack[i][j]$ 라고 하자. 이제 일직선에서 다음과 같은 DP를 빠르게 해결하면 된다:

• $DP[i][j] = min_{k}(DP[i-1][k] + Cost[i][k][j] + Slack[i][j])$

$Cost^\prime[i][k][j] = Cost[i][k][j] + Slack[i][j]$ 라고 새롭게 정의만 해 주면 위 일직선 경우와 동일한 방식으로 최적화할 수 있다. 이로써 하나의 체인에 대해서 올바른 값을 관리하는 방법을 완성했다.

이렇게 HLD를 통해서 DP 값을 모아주는 방법을 알았으니, 갱신은 어렵지 않다. 결국 각각의 체인에 대해서 중요한 값은, 해당 체인의 가장 루트에 가까운 정점이 가지는 DP 값 뿐인데, 이는 세그먼트 트리에서 해당 체인에 대응되는 구간에 쿼리를 하면 바로 알아낼 수 있다. 고로, Light edge든 Heavy edge든 상관없이, 해당 간선의 Cost를 바꾼 후 대응되는 체인에 갱신해주고, 그 값을 계속 부모 체인으로 전파시켜주면 된다. 이 방법을 사용하면 $O(\log N)$ 번의 쿼리로 문제를 해결할 수 있으니 시간 복잡도가 $O(N \log^2 N)$ 이 된다.

마지막으로, 위와 같은 테크닉은 HLD를 동적으로 관리하는 자료구조인 Link-cut tree에서도 그대로 적용할 수 있으며, 이 때의 시간 복잡도는 $O(N \log N)$ 이 된다.

Practice problems

• BOJ. 트리와 쿼리 6
• BOJ. 트리와 쿼리 7
• Jakarta 2017. Rotating Gears (여기까지의 3문제는 DP가 간단한 형태라 행렬을 사용할 필요가 없다.)
• JOI Open 2018. Cats or Dogs
• Codechef AUG18. Chef at the River
• Innopolis Open 2019. Yet Another Tree Problem (Challenge)
• 제2회 IDTCup. SUN인장 만들기 (Challenge)

다른 글 보기

Part 1 (Convex Hull, D&C, Monotone Queue)

Part 2 (Knuth, Lagrange, Slope, Hirschberg)

Part 3 (Circular LCS)

Part 4 (Dynamic Tree DP)