IX. Dynamic Programming & Divide and Conquer (2)

오늘은 연습문제만 있습니다.

1. Segment Tree : 수열을 다루는 자료구조중 하나입니다. 어떤 수열 $a_1, a_2, \dots a_n$ 이 주어집니다.

   • 구간 $[i, j]$가 주어지면, $a_i + a_{i+1} + \dots + a_j$ 의 값을 구합니다.

   • $i, v$ 가 주어지면, $a_i$ 에 $v$를 더합니다.

   1. 첫번째 쿼리만 주어지고, 두번째 쿼리가 주어지지 않는다면, 이 문제를 쿼리당 $O(1)$ 에 처리할 수 있습니다. 부분합 배열이라고 부릅니다. 이 방법을 설명하세요.

   2. 우리는 Complete Binary Tree를 만들어서 이 문제를 해결하고자 합니다. 각 노드는 어떤 구간을 담당할 것입니다. 각 노드들은 다음 원칙을 지킵니다. “노드의 값은, 두 자식 노드의 값을 합한 값을 갖는다. 각 노드는 두 자식 노드가 담당하는 구간을 합한 구간을 담당한다"

   3. 전체 노드의 개수가 몇 개인지 생각해 보세요. 첫 번째 쿼리가 주어졌을 때, 이를 해결하기 위해 총 확인해야 하는 노드가 몇 개인지 생각해 보세요. 두 번째 쿼리에 대해서도 같은 과정을 반복해 보세요.

   4. 이 방법이 두 쿼리를 빠르게 해결할 수 있음을 이해하고, 시간 복잡도를 계산해 보세요.

2. Segment Tree with Lazy Propagation : 위 문제와 거의 같습니다.

   • 구간 $[i, j]$가 주어지면, $a_i + a_{i+1} + \dots + a_j$ 의 값을 구합니다.

   • 구간 $[i, j]$와 값 $v$ 가 주어지면, $a_i, a_{i+1}, \dots a_j$ 에 모두 $v$를 더합니다.

   1. 일반적인 세그먼트 트리가 이 문제를 잘 해결하지 못함을 관찰하세요.

   2. 추가적인 기법으로, 갱신을 “미루는” 방법을 사용하겠습니다. 각 노드마다, 이 노드가 지금까지 얼마나 갱신을 미루고 있었는지를 추가로 저장합니다.

   3. 1번, 2번 쿼리가 주어졌을 때 각각 어떻게 이 정보를 이용하여 값을 계산할지 제시하고, 그 방법들의 시간 복잡도를 계산하세요.

3. Merge Sort Tree : 이번에는 위와 같이 수열이 주어지는 상황에서, 이런 문제를 생각하겠습니다.

   • 구간 $[i, j]$와 어떤 수 $k$가 주어지면, $a_i, a_{i+1}, \dots a_j$ 에서 $k$보다 큰 값의 개수를 구합니다.

   1. 머지 소트 트리는, 세그먼트 트리와 거의 같은 방법으로 만들되, 각 트리가 머지 소트의 중간 과정을 담고 있는 트리입니다.

   2. 즉, 각 트리가 정수값 하나가 아닌 작은 수열을 들고 있습니다.

   3. 이 트리가 위 문제를 빠르게 해결할 수 있음을 보이세요. 목표하는 시간복잡도는 쿼리당 $O(\log^2 n)$ 입니다.

4. Edit Distance : 편집 거리란, 두 수열 $S, T$에 대해, 값의 삽입, 삭제, 대체 연산을 이용하여 $S$를 $T$로 만들고자 할 때 필요한 최소한의 연산 횟수로 정의합니다. 각 수열의 길이가 $m, n$ 일 때, 편집 거리를 $O(mn)$에 구하는 알고리즘을 제시하세요.

5. Longest Common Subsequence : 두 수열 $S, T$에 대해, 두 수열이 가지고 있는 최대 공통 부분 수열을 구하고자 합니다. 두 수열의 길이가 $m, n$일 때, LCS의 길이를 $O(mn)$에 구하는 알고리즘을 제시하세요.

6. Longest Increasing Subsequence : 어떤 수열 $a_1, \dots a_n$ 이 주어졌을 때, 이 중 가장 긴 증가하는 부분 수열 (not necessarily contiguous) 의 길이를 구하고자 합니다.

   1. 자명한 DP식을 생각해 봅시다. 각 $i$에 대해, $D_i$는 $i$번째를 끝 원소로 하는 가장 긴 증가하는 부분 수열의 길이로 정의합니다.

   2. 이제, $D_i = \max_{j < i, A_j < A_i} D_j + 1$ 로 계산 가능합니다.

   3. 이 DP를 그대로 계산하면 $O(n^2)$ 시간이 걸릴 것입니다.

   4. 이보다 빠른 시간 복잡도 $O(n \log n)$ 을 달성하는 방법이, 지금까지 공부한 내용만으로 2가지가 가능합니다. 두 가지를 제시하세요. ¹

7. Lowest Common Ancestor - Binary Lifting & Sparse Table : 트리 $T$에 대해, 정점 $u, v$의 최소 공통 조상을 구하고자 합니다.

   1. 가장 자명한 방법은 두 노드를 루트까지 타고 올라가면서 모든 조상 노드를 찾은 뒤, 조상 노드 번호의 수열을 루트부터 거꾸로 확인하면서 어디까지 겹치는지 확인하는 방법입니다. 이는 $O(n)$ 시간이 걸립니다.

   2. 약간의 Preprocessing을 통해, 각 쿼리를 $O(\log n)$ 에 처리하는 방법을 이해해 보고자 합니다.

   3. 각 노드 $u$의 부모 노드를 안다면, 모든 노드의 2대 부모 노드를 빠르게 구할 수 있음을 이해하세요. 이를 확장하여 $2^{k-1}$ 번째 부모를 안다면 $2^{k}$ 번째 부모도 알 수 있음을 이해하세요.

   4. 따라서, par[x][i] 를 $x$의 $2^i$번째 부모로 정의할 때, 이 배열을 모두 채우는 데 $O(n \log n)$ 시간이 걸립니다.

   5. 이 배열을 이용, $O(\log n)$ 시간에 각 쿼리에 답하는 방법을 제시하세요. 일반성을 잃지 않고, 깊이가 같은 경우만 보여도 됨을 관찰하세요.

   6. 목표는 $u$ 의 $k$번째 부모가 $v$의 $k$번째 부모와 같은 최소 $k$ 찾기입니다. $k$ 를 이진수로 맞추고, par 배열로 짜 맞춰 봅시다.