최소 공통 조상(LCA) 구현 톺아보기 - 3

작성

최소 공통 조상 구현 톺아보기 목록

  1. 부모를 따르는 시뮬레이션
  2. 깊이 우선 탐색의 순서
  3. 구간 최솟값 질의

이번 글에서는 구간 최솟값 질의를 이용하여 최소 공통 조상을 찾는 알고리즘을 알아보겠습니다. 구간 최솟값 질의를 이용하면 최소 공통 조상을 실시간으로 찾을 수 있다는 장점이 있고, 점근적으로 최적의 실행 시간을 얻을 수 있습니다.

이전 글에서 깊이 우선 탐색을 여러 번 하는 대신 질의를 모아서 차리했습니다. 매 깊이 우선 탐색은 항상 같은 동작의 반복이니, 깊이 우선 탐색의 과정을 이용하기 쉬운 형태로 바꾼다면 전처리 정보로 이용할 수 있을 것 같습니다.

깊이 우선 탐색에서 중요한 것은 정점의 방문 순서이고, 최소 공통 조상을 구할 때 중요한 것은 정점의 깊이입니다. 깊이 우선 탐색에서 특정 정점으로 실행 흐름이 옮겨갈 때마다 전처리 정보를 저장할 배열에 정점을 추가합시다. 그러면 전처리 배열에서 정점의 위치가 깊이 우선 탐색에서의 방문 순서가 됩니다.

function precompute(u)

  1. u.begin := len(dfs_ordering)

  2. append u to dfs_ordering

  3. for each v in u.children

    1. precompute(v)

    2. append u to dfs_ordering

  4. u.end := len(dfs_ordering)

어떤 정점 A를 방문 시작하고 B를 방문 종료하기까지 도달한 정점 중 가장 얕은 정점이 최소 공통 조상입니다. 정점을 방문 시작한 위치와 방문 종료한 위치를 기록해 두었으므로, 최소 공통 조상은 이 구간 내에서 정점의 깊이가 최소인 정점과 같습니다.

function lca(u, v)

  1. return dfs_ordering.range_min(u.begin, v.end)

하지만 구간 최솟값을 배열을 순회하며 구하면 O(VQ)\mathcal{O}(VQ) 시간이 걸립니다. 자료구조를 이용해서 이 한계를 극복할 수 있습니다.

세그먼트 트리

세그먼트 트리Segment Tree는 추가 공간 O(N)\mathcal{O}(N)을 사용하여 구간 최솟값을 O(log⁡N)\mathcal{O}(\log N)에 구하는 자료구조입니다. 배열을 길이 202^0의 조각들로 분할하여 각 조각의 최솟값을 저장해 두고, 212^1의 조각들로 분할하여 저장해 두고, …, 2⌈log⁡2N⌉2^{\lceil \log_2 N \rceil}의 조각들로 분할하여 저장해 둡시다. 모든 구간 [l,r)[l, r)은 다음과 같이 최대 2log⁡2N2 \log_2 N 개의 구간으로 분할할 수 있습니다.

a1<a2<⋯<am>am+1>⋯>aka_1 \lt a_2 \lt \cdots \lt a_m \gt a_{m+1} \gt \cdots \gt a_k [l0=l,l1=l0+2a1)⊎[l1,l2=l1+2a2)⊎⋯⊎[lk−1=r−2ak,lk=r)[l_0 = l, l_1 = l_0 + 2^{a_1}) \uplus [l_1, l_2 = l_1 + 2^{a_2}) \uplus \cdots \uplus [l_{k-1} = r - 2^{a_k}, l_k = r)

각 구간의 값을 전처리해 두었으므로 O(log⁡V)\mathcal{O}(\log V) 시간에 최소 공통 조상을 구할 수 있습니다. 전처리에는 O(V)\mathcal{O}(V) 시간이 걸립니다.

희소 배열

구간 [l,r)[l, r)은 단 두 개의 구간만으로도 분할할 수 있습니다.

[l,r)=[l,l+2a)∪[r−2a,r)[l, r) = [l, l + 2^a) \cup [r - 2^a, r)

모든 ii와 11 이상 ⌈log2N⌉\lceil log_2 N\rceil 이하의 모든 aa에 대해 구간 [i,i+a)[i, i + a)에서의 최솟값을 저장해 둔다면 최소 공통 조상을 O(1)\mathcal{O}(1) 시간에 구할 수 있습니다. 단, 전처리 시간와 공간 모두 O(Vlog⁡V)\mathcal{O}(V \log V)이고, 전처리 중 캐시 비적중에 의한 시간 손실이 다소 발생하는 편입니다.

이러한 전처리 방식을 희소 배열Sparse Table이라고 부릅니다.

Bender & Farach-Colton

배열의 특성을 이용하는 것으로 전처리 시간을 더욱 떨어뜨릴 수 있습니다. 배열을 길이 B=0.5log⁡2NB = 0.5 \log_2 N의 덩어리로 쪼개 각 덩어리를 덩어리 내의 최솟값으로 치환한 배열 SS를 만듭니다. 이 과정은 O(N)\mathcal{O}(N)에 가능합니다. SS에 대한 희소 배열을 만들면, 전처리에 시간 O(N)\mathcal{O}(N)이 걸리게 됩니다.

NBlog⁡NB=2Nlog⁡Nlog⁡(2Nlog⁡N)≤2Nlog⁡Nlog⁡2N=O(N)\frac{N}{B} \log \frac{N}{B} = \frac{2N}{\log N} \log \left(\frac{2N}{\log N}\right) \le \frac{2N}{\log N} \log 2N = \mathcal{O}(N)

구간의 최솟값을 구할 때는 ll이 포함된 덩어리의 뒷부분과, rr이 포함된 덩어리의 앞부분과, 그 사이 덩어리의 최솟값을 구하면 됩니다. 사이 덩어리의 최솟값은 희소 배열을 이용하여 구할 수 있고, 각 덩어리 내부의 최솟값을 구하는 것이 문제입니다.

이제 배열의 특성을 이용합니다. 배열에서 인접한 정점의 깊이는 항상 11 차이가 나므로, 덩어리의 첫 값을 나머지 값들에서 빼주면 가능한 덩어리는 −1-1과 11이 B−1B-1번 반복된 2B−12^{B-1}가지가 됩니다. 2B−1=20.5log⁡2N−1=O(N)2^{B-1} = 2^{0.5 \log_2 N - 1} = \mathcal{O}(\sqrt{N})이므로, 가능한 모든 덩어리의 종류마다 앞부분과 뒷부분의 최솟값을 전처리하는 데는 O(NB)=O(Nlog⁡N)\mathcal{O}(\sqrt{N}B) = \mathcal{O}(\sqrt{N}\log N) 시간이 걸립니다.

이제 최소 공통 조상을 전처리 O(V)\mathcal{O}(V), 질의당 O(1)\mathcal{O}(1)에 구할 수 있고, 이는 자명하게 점근적으로 최적인 알고리즘입니다. 구현이 복잡하기도 하고, 실증적인 성능이 높지 않아 많이 쓰이지는 않지만 점근적으로 최적이라는 점에서 알아둘 만한 알고리즘인 것 같습니다.

이번 글, 구간 최솟값 질의를 이용해 최소 공통 조상을 한꺼번에 구하는 알고리즘들을 마지막으로 최소 공통 조상 알고리즘의 소개는 막을 내립니다. 잘못된 내용이나 추가가 필요한 내용, 궁금하신 내용 등은 덧글로 달아주시면 감사하겠습니다. 읽어주셔서 감사합니다!