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

8. Circular LCS

두 문자열 $S, T$ 가 주어질 때 둘의 LCS를 구하는 문제는 잘 알려져 있고, $n = |S|, m = |T|$ 일 때 $O(nm)$ 보다 빨리 하기 힘든 것으로도 유명하다. Circular LCS 문제는 $S$ 를 Cyclic shift 할 수 있을 때, 각 cyclic shift에 대해서 LCS를 계산하는 문제이다. 기호로 표현하면, 모든 $0 \le i \le |S| - 1$ 에 대해, $LCS(S[i:] + S[:i], T)$ 의 값을 계산하는 문제가 된다. 이 문제는 일반적인 LCS 계산법을 사용하면 쉽게 $O(n^2m)$ 에 해결할 수 있으니, 이 글에서는 더 빠른 풀이를 논의한다.

Circular LCS라는 문제는 경시대회에 간혹 등장하긴 하나, 이 문제 자체가 중요해서 이 글에서 소개하는 것은 아니다. 이 글에서 소개될 3가지 해결 방법은 접근 방법 자체가 꽤 다르고, 응용될 수 있는 문제의 종류도 다르다. 고로 하나의 문제로 묶였지만 아주 다른 알고리즘들을 배운다고 생각하는 것이 좋고, LCS라는 문제 자체를 깊게 다룬다는 관점보다는, 여러 문제를 푸는 데 응용될 수 있는 3가지 접근법을 배운다는 관점이 좋다. 특히, 다 넘어가더라도 마지막 풀이인 Solution 3은 일독을 강력히 권한다.

Solution 1. Using Bitset

첫번째 풀이는 Bitset을 사용해서 LCS 하나를 $O(\frac{nm}{w})$ 시간에 빠르게 계산하는 전략을 취한다. 이렇게 되면 Circular LCS를 구하는 건 LCS 함수를 단순히 $n$ 번 호출하는 식으로 해도 $O(\frac{n^2m}{w})$ 시간에 해결할 수 있고, 이렇게만 해도 $n, m = 2000$ 일 때 큰 문제 없이 해결 가능하다. 이 단락은 박수찬의 비트 연산을 활용하여 두 문자열의 LCS 빠르게 구하기 의 내용을 토대로 작성되었다.

LCS를 구하는 기초적인 점화식을 다시 한번 살펴보자. (문자열이 1-based라고 가정한다)

$D[i][j] = \begin{cases} 0 &\quad\text{if }i = 0, j = 0 \newline
D[i-1][j-1] + 1 &\quad\text{if }S[i] = T[j] \newline
max(D[i][j-1], D[i-1][j]) &\quad\text{otherwise.} \newline
\end{cases}$

이 점화식의 반환값은 정수이기 때문에, 점화식만 봐서는 어떻게 bitset을 사용하여 최적화할 수 있는지 보기 힘들다. 하지만 $0 \le D[i][j + 1] - D[i][j] \le 1$ 이라는 관찰을 하면 이야기가 달라진다. 값 자체가 boolean이 되기 때문에 bitset을 응용해 볼 수 있다. $B[i][j] = D[i][j + 1] - D[i][j]$ 라고 정의하면, $D[i][j] = \sum_{k = 0}^{j-1} B[i][k]$ 의 방식으로 최종 결과값을 알 수 있다. 일반적으로 DP 배열의 마지막 행만이 관심사기 때문에 문제를 해결하기 충분하다.

$D[i]$ 배열이 있을 때, 이를 토대로 $D[i + 1]$ 배열이 어떻게 구성되는지 살펴보자. 새로운 배열을 만드는 데 필요한 값은 $S[i + 1]$ 문자의 값, $T$ 문자의 값, 그리고 $D[i]$ 배열, 이 3가지 정보가 필요하다. $S[i + 1] == T[x]$ 인지 아닌지의 정보를 알기 위해, $Match^\prime[alpha][x] = (T[x] == alpha)$ 와 같은 불리언 배열을 $O(|\Sigma| m)$ 시간에 전처리 할 수 있다. ($|\Sigma|$ 는 알파벳 대문자만 있다면 26가지일 수도 있고, 일반적인 알파벳의 경우에는 $m$ 가지가 전부 등장할 수도 있다.) 이렇게 하면 두 개의 bitset $D[i], Match^\prime[S[i + 1]]$ 만이 관심사가 된다. 이들을 어떻게 조합하면 되는지 살펴보자.

$B[i][j]$ 는 모든 $0 \le j \le m - 1$ 에 대해서 올바르게 정의되는데, 추가적으로 $B[i][m] = 1$ 이라고 하자. 이렇게 되면 $B[i][j] = 1$ 인 $j$ 의 인덱스들을 ${j_0, j_1, \ldots, j_k}$ 라고 하였을 때 $(0 \le j_0 < j_1 \ldots j_k = m)$, $j \in [0, j_0 ]$ 구간에서는 $D[i][j] = 0$, $j \in [j_0 + 1, j_1]$ 구간에서는 $D[i][j] = 1$ 을 만족한다. 일반적으로, $j \in [j_{x-1} + 1, j_x]$ 인 구간에서는 $D[i][j] = x$ 를 만족한다.

$0 \le D[i+1][j] - D[i][j] \le 1$ 이 만족하니, 이 구간에서 어떠한 위치부터는 $D[i+1][j] = x + 1$ 이 만족하게 될 수도 있다. 물론 이러한 위치가 없을 수도 있다. 만약 저러한 위치가 존재한다면 이 위치는 $Match^\prime[S[i + 1]]$ 에서 찾을 수 있는데, 만약 $j \in [j_{x-1} + 2, j_x]$ 구간에 $Match^\prime[S[i + 1]][j]$ 가 참인 위치가 존재한다면, 이 위치를 포함하여 거기서 오른쪽으로 뻗어나가는 구간에는 모두 $D[i+1][j] = x + 1$ 이 만족하게 된다. 저러한 위치가 존재한다고 할 때 그 곳을 $pos$ 라고 하면, $B[i+1][pos - 1]$ 이 참이 되는 것이다. 뭔가 불편한 느낌이 드니

$Match[alpha][x] = (T[x + 1] == alpha)$

로 재정의하여 0-based로 바꿔주자. 이제 $j = [j_{x -1} + 1, j_x]$ 구간에 $Match[S[i + 1]][j]$ 가 참인 위치가 존재하면, 해당 위치로 $B[i][j_x]$ 를 옮겨주면 되고, 그러한 위치가 존재하지 않으면 $B[i][j_x]$ 를 그대로 유지하면 된다. x = Match[S[i + 1]] | B[i] 라고 정의하면, $[j_{x-1} + 1, j_x]$ 구간에 무조건 참인 위치가 존재하니, 해당 구간에서 가장 낮은 비트만 살려주면 된다. 만약 구간 개념이 없다면, 정수에서 가장 낮은 비트를 찾는 법은 여러 가지가 알려져 있다: x - x & -x, x ^ (x & (x - 1)) 등이 그 예시이다.

여러 구간에서 동시에 낮은 비트만 남기기 위해서는, 각 구간에 대한 x-1 값을 전부 모으는 것이 필요하다. $x$ 는 쉽게 알 수 있으니, 각 구간에서 1에 대응되는 숫자들을 알아야 하는데, 이는 ${0, j_0 + 1, j_1 + 1, \ldots, j_k + 1}$ 비트에 대응된다. 각 구간이 비지 않았기 때문에 (즉, $x \neq 0$ 이기 때문에) 이들을 전부 합쳐서 x 에서 한꺼번에 빼 주면 된다. 위와 같은 비트가 켜진 비트셋은 매우 간단하게 계산 가능하다: (D[i] << 1) | 1

결론적으로, x = Match[S[i + 1]] | B[i], y = (D[i] << 1) | 1 이라고 하면,

B[i + 1] = x ^ (x & (x - y))

이라는 멋진 상태 전이가 유도된다. 마지막으로, $B[i][m] = 1$ 일 이유가 전혀 없기 때문에, 코드 상에서 이러한 처리는 필요없다.

Bitset을 사용한 LCS 계산은 속도 때문에 그 자체로도 유용한 면이 많으나, 비슷한 형태의 문제 해결법을 통해서 다른 문제들을 해결할 수 있다는 점에 의미가 있다. 특히 String matching / Approximate string matching 문제를 풀 때도 비슷한 풀이를 사용할 수 있는데, 사실 이 경우에는 이렇게 Bitset DP 최적화를 어렵게 적용하지 않아도 문제가 잘 해결되는 편이다. 예를 들어 Fuzzy searching algorithm인 Bitap algorithm 에서도 최적화를 위해 비슷한 아이디어를 사용한다.

Practice problems

• Codeforces: Substrings in a String
• Algospot: Maximal K-Edit Subset
• SPOJ: LCS
• BOJ: LCS 6
• BOJ: LCS 7

Solution 2. Quadratic Ad-hoc

두 번째 풀이는 Cyclic LCS 문제를 $O(nm)$ 에 해결하는 방법이다. 이 풀이는 지금 소개할 풀이들 중에서 가장 구현이 간결하고 시간 복잡도가 빠르지만, 정확히 LCS 문제만 해결할 수 있고, 조금이라도 일반화가 되면 (예를 들어 매칭에 weight가 걸리는 등) 알고리즘의 정당성이 바로 깨진다는 단점이 있다. 이러한 점에서, 이 풀이는 특정 문제만 해결할 수 있는 Ad-hoc한 성질이 있다고 표현할 수 있다. 아래 알고리즘은 Andy Nguyen의 Solving Cyclic Longest Common Subsequence in Quadratic Time 논문에서 유래하였다.

Solution 2부터는 단순히 LCS를 빠르게 푸는 전략이 먹히지 않기 때문에 문제의 특성을 관찰해야 한다. 먼저 $S := S + S$ 로 입력으로 주어진 문자열을 자신과 이어붙인 문자열을 사용한다. 이제 Cyclic LCS 문제는 결국 $LCS(S[i, i + n - 1], T)$ 를 모든 $i$ 에 대해서 구하는 문제가 된다.

여기서 문제의 성질에 대한 관찰이 들어간다. DP 배열을 계산하는 과정은, 각 상태를 노드로 둔 DAG에서 최장 경로를 구하는 과정과 동일하다 (아래 사진 참고). $S, T$ 의 LCS를 계산하는 DAG를 구성했을 때, $S$ 와 $T$ 의 LCS를 계산하는 것은 결국 DAG의 왼쪽 위 노드에서 오른쪽 아래 노드로 가는 경로를 찾는 문제라고 볼 수 있다. $S$의 "부분 배열"과 $T$ 의 LCS를 계산하는 것은 DAG의 왼쪽 사이드에 있는 어떤 노드에서, 오른쪽 사이드에 있는 어떤 노드로 가는 경로를 찾는 문제가 된다. 이제, $DP[i][j]$ 엔트리를 그리드 상의 격자점으로 생각하고 $(i, j)$ 라고 표현한다.

이제 우리가 풀게 될 문제는 모든 $0 \le i \le n-1$ 에 대해 $(i, 0) \rightarrow (i+n, m)$ 으로 가는 최장 경로를 찾는 것이다. 편의상 최장이 아니라 최단 경로라고 하자 (DAG이기 때문에 부호만 바꿔주면 된다). 이 경우 $(i, 0)$ 을 루트로 하는 최단 경로 트리를 만들면, $(i + n, m)$ 에서 $n+m$ 개의 정점을 따라가는 식으로 최단 경로를 알 수 있다.

모든 $0 \le i \le n - 1$ 에 대해서 최단 경로 트리를 알아내기 위해, $(0, 0)$ 을 루트로 하는 최단 경로 트리를 $O(nm)$ 시간에 구한 후, $(i, 0)$ 을 루트로 하는 최단 경로 트리를 $(i + 1, 0)$ 을 루트로 하는 최단 경로 트리로 바꿔나가는 연산 (Rerooting) 을 수행할 것이다. 사실 이 Rerooting 연산은 DP 배열의 맨 윗 행을 지우는 연산으로 볼 수 있다.

변경을 수월하기 위해서 최단 경로 트리가 최대한 낮은 경로 를 유지한다고 가정하자. 이는 어떠한 정점에서 가능한 모든 최단 경로 중, 각 가로/대각선 선분의 위치가 가능한 낮은 (행 번호가 가능한 큰) 위치에 있는 최단 경로만을 택한다는 것을 뜻한다. 평면 그래프이기 때문에 이러한 가장 낮은 경로 가 존재한다. 초기 최단 경로가 낮은 경로를 유지하게 하기 위해서는, 여러 선택지가 있을 때 가장 낮은 간선을 선택하는 식으로 부모를 이어주기만 해도 충분하다. 즉, $(i, j-1), (i-1, j-1), (i-1, j)$ 와 같은 3가지 선택지 중 몇 개의 선택지가 똑같은 DP 값을 준다면, 왼쪽/대각선/위쪽 순서대로 택해주는 것이다. 이제 이러한 낮은 경로 조건을 만족하게끔 하면서 Rerooting 연산을 설계해보자.

$i+1$ 번 행에서 $i$ 번 행으로 올라오는 방법은 대각선 간선을 타고 올라오거나, 위쪽 간선을 타고 올라오는 두 가지 방법이 있다. 만약 어떠한 경로가 위쪽 간선을 타고 온다면 이 때 사용한 간선은 무조건 $(i + 1, 0) \rightarrow (i, 0)$ 간선이 된다. 그렇지 않을 경우 $(i + 1, j) \rightarrow (i+1, 0) \rightarrow (i, 0)$ 을 타고 올라오는 식으로 가중치가 같은 낮은 경로로 변환 가능하기 때문이다. 같은 논리로 인해, 대각선 간선을 타고 올라오는 경우도 많아야 한 가지이다. 만약 대각선 간선을 탈 수 있는 경로가 2개 이상이면, 오른쪽 간선을 타는 경로를 낮게 만들 수 있기 때문이다. 이 때, $(i+1, 0) \rightarrow (i, 0)$ 으로 올라오는 간선의 서브트리에 있는 노드들은 최단 경로 트리가 바뀌지 않는다. 최단 경로 트리는 대각선 간선 $(i + 1, j + 1) \rightarrow (i , j)$ 이 존재할 때 이 간선을 타고 올라오는 서브트리에 대해서만 바뀌게 된다. ($(i, j + 1) \rightarrow (i, j)$ 간선도 있으나 이는 전부 $i$ 번 행에 속하니 상관 없다.)

이제 일반성을 잃지 않고 대각선 간선을 타고 올라오는 서브트리가 존재한다고 하고, 이를 $D$ 라고 하자. 위쪽 간선으로 올라오는 서브트리는 $U$ 라고 한다.

$D$ 에 있는 노드들에 대해서 새로운 부모를 부여해 주자. 부모를 부여할 때 중요한 것은

• 최단 경로 조건이 유지되어야 하며
• 가장 낮은 경로를 유지해야 한다

는 것이다. 먼저 첫번째 조건에 대해서 생각해 보자. 최단 경로 트리는 가장 낮은 경로를 유지하였다는 것이 가정이니 만약 $S[i] = T[j]$ 라는 매칭을 택하지 않고 최단 경로로 갈 수 있었다면 그렇게 했을 것이다. 이는 즉 $D$에 있는 모든 정점들의 LCS 길이는 정확히 1 감소할 수 밖에 없다는 것이다. 지금 현재 대각선 간선 하나를 끊어 1씩 감소시켰으니, 단순하게는 $(i+1, j+1) \rightarrow (i+1, j)$ 로 그냥 간선을 이어주기만 해도 최단 경로 트리 조건은 유지할 수 있다. 단지 가장 낮은 최단 경로가 아닐 뿐이다.

두번째 조건에 대해서도 생각해 보자. Rerooting 후 $D$ 에 있는 임의의 정점에서 $(i + 1, 0)$ 으로 가는 가장 낮은 경로를 생각해 보자. 이 경로는 $D$ 에 있는 정점에서 시작하여 $(i + 1, 0) \in U$ 에서 끝난다. 고로 $D$ 정점 $x$ 에서 $U$ 정점 $y$ 로 가는 첫 시점이 있을 텐데, $y$ 이후부터는 가정에 의해 무조건 $U$ 에 있는 경로를 따라 부모로 올라간다. 또한 경로의 시작점에서 $x$ 를 가는 경로를 생각했을 때, $x$ 라는 위치에서 $y$ 가 아니라 $(i+1, j+1) \rightarrow (i+1, j)$ 방향으로 올라가도 비용은 동일하다 (가정에 의해 이득은 못 보고, 손해를 봤다면 해당 정점에서 LCS 길이를 줄이지 않을 수 있어 역시 가정에 모순). 고로 $x$ 를 가는 경로가 최단 경로 트리 상 경로와 다르다면 모순을 보일 수 있게 된다.

위 상황을 종합했을 때, 결국 최단 경로 트리의 조정은 $D$ 와 $U$ 를 잇는 간선들에 대해서만 일어나게 되고, 그 외 내부 간선들에 대해서는 변화가 없다는 것을 알 수 있다. 정확히는, DAG 상에서 $D$ 와 $U$ 를 가르는 "강" 이 생기게 되는데, 이 강에 접해있지 않은 정점들은 최단 경로 트리에 변화가 없게 된다. 강은 우하단으로만 향하기 때문에, 결국 최단 경로 트리에 $n+m$ 개 간선들만 갱신된다는 결론을 얻게 된다. 이는 정확히 우리가 원하던 결과이니, 이제 $n+m$ 개 간선을 갱신시키는 방법을 알아보자.

먼저, 위에서 정의한 "강" 을 찾는 것은 어렵지 않다. 각 정점에 대해서 부모 정점이 무엇인지를 저장해 두면, 단순히 $(i, j)$ 지점에서 시작해서 갈 수 있는 가장 남쪽 자식 정점을 반복해서 따라가면 된다. 이제 이렇게 방문한 정점들에 대해서 새로운 부모를 부여해야 하는데, 생각보다 할 수 있는 선택지가 많지 않아 쉽게 부여할 수 있다. 현재 정점을 $(i, j)$ 라고 하고, $p(i, j)$ 를 이 정점의 부모라고 하자.

• $p(i, j) = (i, j-1)$ 이면 갱신이 불가능하다.
• $p(i, j) = (i-1, j-1)$ 이면 새로운 선택의 후보는 $(i-1, j)$ 이다. Rerooting 전 기준 이 선택은 많아야 1의 손해를 준다. Rerooting 이후 이 선택이 줄 수 있는 손해가 0 이하이니 무조건 $p(i, j) = (i, j-1)$ 로 해 주면 된다.
• $p(i, j) = (i-1, j)$ 이면 $S[i] \neq T[j]$ 이기 때문에 (아니면 무조건 $(i-1, j-1)$ 로 타면 된다) 역시 새로운 선택의 후보는 $(i-1, j)$ 이 된다. $DP[i-1][j] - DP[i][j-1] \le DP[i-1][j] - DP[i-1][j-1] \le 1$ 이니 역시 이 선택도 손해가 많아야 1이다. Rerooting 이후 이 선택이 줄 수 있는 손해가 0 이하이니 무조건 $p(i, j) = (i, j-1)$ 로 해 주면 된다.

결론적으로, 강에서 만나는 모든 정점들에 대해서 대각선/수직 방향 조상들을 수평선으로 바꿔주면 Rerooting이 끝난다. 각 Rerooting이 $O(n+m)$ 이니 시간 복잡도 $O(n(n+m))$ 에 문제가 해결된다.

Practice problems

• Pacific Northwest 2011: Bracelets
• IZhO 2013: Round words
• BOJ: 제곱 부분문자열
• Petrozavodsk Winter 2014: Total LCS

Solution 3. Divide and Conquer

Solution 3 역시 Solution 2에서 도입한 Shortest Path DAG 개념을 활용하여, $(i, 0) \rightarrow (i + n, m)$ 으로 가는 최단 경로를 찾는 문제를 효율적으로 해결하려 한다. 여기서 Solution 3은 조금 더 일반적인 성질만을 사용해서 문제를 해결한다. 아래에 이 핵심 Lemma를 소개한다.

• Lemma 1. $0 \le i, j \le n, i \neq j$ 에 대해, $(i, 0) \rightarrow (i+n, m)$ 으로 가는 임의의 최단경로와 교차 (간선이 겹칠 수는 있음)하지 않는 최단 경로 $(j, 0) \rightarrow (j+n, m)$ 이 존재한다.
• Proof. 교차한다고 하였을 때 $i$ 의 최단 경로를 따라서 가게끔 수정해 주면 되어 가정에 모순이다.

이 사실은 일반적인 평면 그래프에서 성립하는 성질이다.

이제 바로 분할 정복 알고리즘을 설계하자. 전략은 간단하다. $(n/2, 0) \rightarrow (3n/2, m)$ 으로 가는 최단 경로를 구해주면, 그보다 더 아래에서 출발하는 모든 최단 경로는 해당 경로 위로 침범하지 않고, 그 위에서 출발하는 모든 최단 경로 역시 아래로 침범하지 않는다. 고로, 이 최단 경로를 $O(nm)$ 시간에 구해준 후 그리드를 최단 경로 기준 위 아래로 쪼개버릴 수 있다. 이렇게 쪼갠 후에 나머지 최단 경로들은 쪼개진 그리드에서만 최단 경로를 찾도록 해 주면 된다.

일반적인 상황에서 이를 소개하자면 다음과 같다. $solve(L, R, A)$ 를 $i \in [L, R]$ 에 대해 각각 최단 경로를 찾는 재귀함수라고 하고, $A$ 를 검색을 하게 될 평면 DAG의 부분이라고 하자. $M = \lfloor (L+R)/2 \rfloor$ 에 대해서, $(M, 0) \rightarrow (M + n, m)$ 으로 가는 최단 경로를 $A$ 의 정점 개수에 비례하는 시간 복잡도에 찾을 수 있다. 이렇게 찾고 나면, 해당 경로 위/아래로 평면 DAG를 분리할 수 있게 된다. 위쪽에 있는 평면 DAG는 Lemma에 의해 $[L, M-1]$ 구간에만 필요하고, 아래는 $[M+1, R]$ 구간에만 필요하다. 이 때 각 구간이 받는 그래프의 크기는 다를 수 있지만, 그 합은 $|V(A)| + (\text{경로 길이})$ 임을 알 수 있다.

이 때의 시간 복잡도는

$T(n, A) = T(n / 2, X) + T(n / 2, A - X + n) + O(A)$

$T(n, (A - n) + n) = T(n/2, (X-n)+n) + T(n/2, (A-X)+n) + O((A-n)+n)$

$T(n, (A-n)+n) = O((A-n) \log n) + O(n^2)$

$T(n, O(nm)) = O(nm \log n)$

이 된다.

More insights about solution 3

이렇게 원형 구조에서 최적해를 찾는 것을 Planar DAG에서의 경로 찾기 문제로 환원했을 때, 여러 흥미로운 문제들을 원형 구조에서 효율적으로 풀 수 있다. 다음 문제를 생각해 보자.

• K-median in Cycle. 지름이 $L$ 인 원에 $N$ 개의 점 (마을)이 있다. $K$ 개의 우체국을 설치할 것인데, 각 점에 대해서 가장 가까운 우체국과의 거리를 계산한 후, 이의 합을 최소화해야 한다. 원 상에 있는 두 점 $0 \le x, y < L$ 의 거리는 $min(|x - y|, L - |x - y|)$ 로 정의한다. (아래 연습 문제로 나온 "IOI Problem Revisited" 문제가 이와 동일하다.)

먼저 이 문제를 직선에서 푸는 방법을 논의하자. (직선에서 풀기 쉽지 않기 때문에 짧게만 언급한다.)

• K-median in line. 직선 위에 $N$ 개의 점 (마을)이 있다. $K$ 개의 우체국을 설치할 것인데, 각 점에 대해서 가장 가까운 우체국과의 거리를 계산한 후, 이의 합을 최소화해야 한다. 두 점 $x, y$ 의 거리는 $|x-y|$ 로 정의한다. (IOI 2000 Post Office 문제와 동일하다.)

우체국을 지을 마을들을 고정시키면, 각 마을에서 사람들은 가장 가까운 마을에 있는 우체국으로 가려고 한다. 이 때, 각 우체국들에 대해서 해당 우체국으로 모이는 사람들을 나열하면, 이들은 입력 상에서 연속된 구간을 이룬다. 이제 거꾸로, 입력으로 주어진 사람들을 $P$ 개의 연속된 구간으로 분할하는 식으로 문제를 해결해 보자. 한 구간 $[s, e]$ 에 대해서, 최소 비용으로 사람들이 모이는 우체국 하나를 짓는다면, 그 위치는 $m = \lfloor (s+e)/2 \rfloor$ 번 마을의 위치가 된다.

$DP_{i, j} = (i$ 개의 구간으로 $[1, j]$ 를 분할했을 때 최소 비용), $Cost(s, e) = ([s, e]$ 구간에서, 최소 비용으로 우체국을 지었을 때의 비용) 이라고 정의하면, $DP_{i, j} = Min_{k < j}{(DP_{i - 1, k} + Cost(k + 1, j))}$ 라는 점화식을 유도할 수 있다. 한 구간에 대한 최적 위치를 알고 있으니, $Cost(s, e)$ 는 $O(N^3)$ 에 전처리 가능하고, 고로 전체 문제가 $O(N^3)$ 에 해결된다. $Cost(i, j)$ 가 Monge이기 때문에, 이 풀이를 Monotone Queue Optimization과 Aliens Trick을 사용하여 최적화하면 $O(N \log X \log N)$ 으로 최적화할 수 있다.

다시 원형 문제로 돌아오자. 위 line의 알고리즘을 그대로 적용하면, $O(N^2 \log X \log N)$ 에 원형의 문제를 해결할 수 있다. 원 상에서도 어떠한 우체국으로 모이는 사람들이 연속된 원호상 구간을 이루기 때문에, 원에서 $i$ 번 마을과 $i+1$ 번 마을의 연결을 자르는 모든 $N$ 개의 경우를 다 시도해 본 후, 위에서 설명한 알고리즘을 사용해 $O(N \log X \log N)$ 에 문제를 해결하면 된다.

Aliens trick을 통해서 최적값 뿐만 아니라 답 자체 역시 복원할 수 있기 때문에, 실제 파티션을 알 수 있다. 이 파티션은 길이 $N$의 구간을 $K$ 개의 연속 구간으로 분할했으니, 이 중에는 길이가 $\frac{N}{K}$ 이하인 연속 구간이 무조건 존재한다. 그렇다면, 원 전체를 끊을 필요가 없이, 이 연속 구간에 있는 점들만 끊어보면 되지 않을까? 아래 Lemma를 통해서 그것이 사실임을 증명한다.

• Lemma 2. $[1, n]$ 구간을 최적으로 분할했을 때, 분할 된 구간 중 하나를 $[s, e]$ 라고 하였을 경우, $(s-1, s), (s, s+1), \cdots, (e, e+1)$ 중 하나만 끊어도 답을 찾을 수 있다.
• Proof. 모순을 가정하자. 위 구간을 끊어서 찾은 어떠한 원형 파티션 $P$가 존재하고, $cost(P) > cost(Q)$ 이며, 위 구간을 끊지 않은 최적 원형 파티션 $Q$ 가 존재한다. 이 분할에 존재하는 어떤 구간은 $[s, e]$ 구간을 완전히 포함할 것인데, 이를 $[l, r]$ 이라고 하자. ($l < s \le e < r$) 또한, $Q$ 에 있는 어떠한 구간은 $P$ 에 있는 구간에 완전히 포함되는데, 이를 $I_1 = [x_1, y_1], I_2 = [x_2, y_2]$ 라고 하자. ($x_1 \le x_2 \le y_2 \le y_1$) . Monge Property에 의해서, $[s, e], [l, r]$ 을 $[s, r], [e, l]$ 로 바꾸고, $[x_1, y_1], [x_2, y_2]$ 를 $[x_1, y_2], [x_2, y_1]$ 로 바꿔도 비용은 증가하지 않는다. 고로 새로운 partition $R, S$ 를 정의하는데
  • $R$ 은 $[s, r]$ 구간을 포함하고, 시계 방향으로 $Q$ 의 파티션을 따라가다가, $[x_2, y_1]$ 구간을 포함하고, 시계 방향으로 $P$의 파티션을 따라간다.
  • $S$는 $[e, l]$ 구간을 포함하고, 시계 방향으로 $P$ 의 파티션을 따라가다가, $[x_1, y_2]$ 구간을 포함하고, 시계 방향으로 $Q$의 파티션을 따라간다.
• 이렇게 바꿀 경우, 우리는 $(s-1, s)$ 를 끊은 원형 파티션 $R$, $(e, e+1)$ 를 끊은 원형 파티션 $S$ 를 얻게 되는데, $cost(P) + cost(Q) \geq cost(R) + cost(S)$ 이다. 고로 $cost(R) < cost(P), cost(S) < cost(P)$ 중 하나가 만족해야 한다. 이는 $P$가 최적이라는 가정에 모순이다.

$[1, n]$ 구간에 대해서 Aliens trick을 사용하여 $O(N \log N \log XV)$ 에 답을 찾자. 이렇게 했을 경우 직선은 $K$ 개의 구간으로 쪼개지며, 이 중 최소 한 구간은 길이가 $\frac{N}{K}$ 이하일 것이다. $K$ 개의 행으로 이루어진 2차원 구조를 생각하자. 각 행의 길이는 다를 수 있으며, 1행의 길이는 $\frac{N}{K}$ 이하이고, 모든 나머지 행들의 길이 합은 $N$이다. (1행이 $\frac{N}{K}$ 이하의 길이를 갖지 않을 수도 있으나, 적절한 rotation을 통해 그렇게 바꿔줄 수 있다.) 이제 편의상, $K+1$ 개의 행으로 바꾸고, $K+1$ 번째 행은 1행과 똑같은 원소를 배정하자. 이렇게 되면 문제는 다음과 같이 바뀐다.

• 모든 $0 \le i \le |V[1]|$ 에 대해서, $(1, i) \rightarrow (2, *) \rightarrow \cdots \rightarrow (K, *) \rightarrow (K+1, i)$ 로 가는 최단 경로를 찾아라.

2차원 격자로 변환하니, 위에서 논의했던 Circular LCS와 상당히 비슷한 문제 정의가 가능해졌다. 그래프가 평면은 아니지만, Monge array의 특성을 사용하여, 분할 정복 풀이에서 가정한 Lemma 1를 계속 유지시키는 것이 목표이다.

이러한 경로를 찾으면, 이 경로에서 실제로 방문한 위치들은 새로운 partition에서 두 구간이 갈라지는 위치에 대응된다. 고로, $(i, x)$ 에서 $(i+1, y)$ 로 가는 간선의 가중치는 $Cost$ 함수를 통해서 제공하는 식으로 문제를 해결할 수 있다. 꼭 최단 경로가 모든 행을 방문해야 할 필요가 없다고 생각할 수 있겠지만, Lemma 2에 의해서, 한 행을 건너뛰는 경우를 생각할 필요가 없어서, 이러한 경우만 고려해 줘도 된다. 이 격자에서 바로 경로를 찾을 경우 단순하게는 한 $i$ 당 $O(N^2)$ 의 시간이 걸리는데, 선형 케이스와 유사하게 Monotone queue optimization을 활용하면 $O(N\log N)$ 으로 시간을 줄일 수 있다.

이제, Solution 3의 Lemma 1에 대응되는 새로운 Lemma를 소개한다.

• Lemma 3. $0 \le i < j \le |V[1]|$ 에 대해, $(1, i) \rightarrow (K+1, i)$ 로 가는 경로는 $(1, j) \rightarrow (K+1, j)$ 경로를 넘어가지 않는다 (만날 수 있으나, 교차해서 반대편으로 가지 않는다.)
• Proof. Lemma 2와 비슷하게 Monge property를 사용하여 가정에 모순임을 보일 수 있다.

Lemma 3에 의해서 Cyclic LCS와 동일하게 문제를 해결할 수 있음을 보였다. 고로 Solution 3을 그대로 적용하면 된다. 이제 시간 복잡도를 분석한다.

$T(n, A) = T(n / 2, X) + T(n / 2, A - X + k) + O(A\log A)$

$T(n, (A - k) + k) = T(n/2, (X-k)+k) + T(n/2, (A-X)+k) + O(((A-k)+k)\log A)$

$T(n, (A-k)+k) = O((A-k) \log n \log A) + O(nk \log A)$

$T(N/K, N) = O(N\log ^2 N) + O((N/K) K \log N) = O(N\log^2 N)$

전체 문제가 $O(N \log X \log N) + O(N \log^2 N)$ 에 해결된다.

Practice problems

• 2차원 평면 상에 $N$개의 점이 있을 때, 이 중 $K$ 개의 점을 골라서, 이 $K$ 개의 점으로 만든 Convex hull의 넓이를 최대화하자. 채점 가능한 문제는 아니지만, $K = 3, 4$ 의 경우 $O(N^2)$ 에 해결하도록 하는 문제들이 있다. 이 문제의 $O(N \log X \log N$) 풀이를 찾아라.
• IOI 2013 Wombats
• BOJ: 우체국 5
• Petrozavodsk Summer 2010. Underground

다른 글 보기

​
Part 1 (Convex Hull, D&C, Monotone Queue)
​
Part 2 (Knuth, Lagrange, Slope, Hirschberg)
​
Part 3 (Circular LCS)
​
Part 4 (Dynamic Tree DP)