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

수정

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

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

루트가 있는 트리에서, 두 정점의 최소 공통 조상Lowest Common Ancestor은 두 정점의 공통 조상 중 가장 깊은 조상을 말합니다. 트리에서 두 정점 사이의 경로는 유일하며 항상 최소 공통 조상을 지나기 때문에 문제 해결 과정에서 최소 공통 조상을 구하는 일이 잦습니다.

문제 해결 분야에서 자주 쓰이는 알고리즘 중에서도 최소 공통 조상 알고리즘은 특히나 구현 방법이 다양한데, 이번 글부터 앞으로의 몇 글에 걸쳐 널리 알려진 구현 방법들과 그 장단점을 정리하려고 합니다.

이 글에서 VV는 트리의 정점 수, QQ는 최소 공통 조상을 구하는 횟수를 나타냅니다. O~(f(V))\tilde{\mathcal{O}}(f(V))는 O(f(V)log⁡kg(V))\mathcal{O}(f(V) \log^k g(V))와 같습니다.

부모를 따르는 시뮬레이션

최소 공통 조상을 구하기 위해 가장 쉽게 떠올릴 수 있는 방법은 정의를 직접 사용하는 것입니다. 각 정점의 조상들을 나열하고, 공통되는 조상들의 깊이를 비교하면 됩니다. 조상을 나열하기 위해서는 정점의 부모를 따라가는 것을 반복하면 됩니다. 부모 정보는 문제에서 주어지는 대로 사용하거나, 루트에서 그래프 탐색을 시행해서 구할 수 있습니다. 깊이 정보 또한 그래프 탐색을 통해 구할 수 있습니다.

부모 정보가 미리 주어진다고 가정하겠습니다. 조상을 나열하는 데 조상의 개수, 즉 정점의 깊이만큼 부모를 따라가야 합니다. 정점의 깊이는 최대 VV이고, 부모를 따라가는 것은 O(1)\mathcal{O}(1)에 가능하므로 O(V)\mathcal{O}(V) 시간에 조상을 나열할 수 있습니다.

공통되는 조상을 빠르게 구하기 위해서는 집합 자료구조를 사용할 수 있습니다. O~(1)\tilde{\mathcal{O}}(1) 시간에 원소의 포함 여부를 알 수 있으므로, 공통 조상을 모두 탐색하여 깊이를 비교하는 데에는 O~(V)\tilde{\mathcal{O}}(V) 시간이 걸립니다.

따라서, 위 알고리즘의 시간복잡도는 O~(V)\tilde{\mathcal{O}}(V)입니다.

깊이 정보를 보다 적극적으로 이용해서 시간을 개선할 수 있습니다. 두 정점이 같아질 때까지 더 깊은 정점의 부모를 따라가는 것입니다. 두 정점이 같아졌을 때가 정확히 최소 공통 조상에 도달한 것이므로, 이 알고리즘의 시간은 각 정점에서 최소 공통 조상까지의 거리에 달려 있습니다.

일자형 트리에서 루트와 유일한 리프 정점 사이의 거리는 VV이므로 이 알고리즘의 시간복잡도는 O(V)\mathcal{O}(V)입니다. 더 빠르게 할 수 있을까요?

여러 부모 건너뛰기

기존 시뮬레이션 방식의 문제점은 정점이 아무리 깊어도 부모 하나만을 건너뛰었습니다. 부모를 한 번에 BB세대 건너뛴다면 최대 V/BV/B번 건너뛰어 최소 공통 조상에 도달하므로 속도가 개선될 것으로 보입니다.

문제는 BB세대를 건너뛸 때 최소 공통 조상을 지나칠 수 있다는 데 있습니다. 이를 해결하기 위해서는 약간의 관찰이 필요합니다.

기존 시뮬레이션에서 두 정점의 깊이가 같아질 때까지 한쪽만 계속해서 부모를 따른다는 점을 관찰할 수 있습니다. BB세대를 건너뛰어서 더 낮아지지 않을 때까지 더 깊은 쪽의 부모를 BB세대씩 건너뜁시다. 그리고 깊이가 같아질 때까지 부모를 한 세대씩 따르면 기존 시뮬레이션의 초반 동작을 구현할 수 있습니다.

일단 깊이가 같아지고 나면, 기존 시뮬레이션에서는 양 정점을 번갈아 가며 부모를 따르게 됩니다. 즉 양 정점을 동시에 건너뛰어도 상관이 없습니다.

두 정점은 최소 공통 조상에 도달했을 때 처음으로 같아지고 이후 계속 같다는 점에 착안해 봅시다. 두 정점이 같아지기 직전까지, BB세대씩 건너뛰다 BB세대보다 적게 남았을 때 한 세대씩 건너뛰면 최소 공통 조상의 직전까지 도달할 수 있습니다. 이후 한 세대를 건너뛰면 최소 공통 조상에 도달할 수 있습니다. 구현 시 두 정점이 같은 경우를 조심해야 합니다.

BB세대씩 건너뛰는 동작을 최대 ⌊V/B⌋\lfloor V/B \rfloor번, 한 세대씩 건너뛰는 동작을 최대 BB번 수행하므로 이 알고리즘의 시간복잡도는 O(V/B+B)\mathcal{O}(V/B+B)입니다. BB가 상수라면 O(V)\mathcal{O}(V)와 같지만, B=O(V)B = \mathcal{O}(\sqrt{V})로 잡으면 O(V/B+B)=O(V)\mathcal{O}(V/B+B) = \mathcal{O}(\sqrt{V})가 됩니다. 산술평균과 기하평균의 관계에 의해 이러한 BB가 최적임을 증명할 수 있습니다.

더 빠르게 할 수 있을까요?

이진 도약

BB세대씩 건너뛰면서, 이런 생각을 하셨을지도 모르겠습니다.

모든 깊이 dd에 대해서 dd씩 부모를 건너뛴 결과를 저장해 두면 BB번 추가로 부모를 따라갈 필요가 없지 않나?

맞는 말입니다. 하지만 깊이는 11부터 VV까지 존재할 수 있으므로 모든 깊이만큼 부모를 건너뛴 결과를 저장하는 데에는 O(V2)\mathcal{O}(V^2)의 공간이 필요합니다. 많은 문제 해결 상황에서 O(VQ)\mathcal{O}(VQ) 시간이 제한을 만족시키지 못한다면 O(V2)\mathcal{O}(V^2)의 공간은 더욱 만족시키기 어려울 것이라 생각합니다.

다만 여러 깊이를 건너뛴 결과를 저장한다는 발상은 빌려올 수 있을 듯싶습니다. 공간을 조금만 희생해서 시간을 줄이려면 어떻게 해야 할까요?

모든 00 이상의 정수 NN은 다음 꼴로 나타낼 수 있습니다.

0≤a1<a2<⋯<aK≤log⁡2N0 \le a_1 \lt a_2 \lt \cdots \lt a_K \le \log_2 N N=2a1+2a2+⋯+2aKN = 2^{a_1} + 2^{a_2} + \cdots + 2^{a_K}

이는 NN의 이진법 표현이 유일하다는 것으로부터 직관적으로 알 수 있습니다. 여기서 KK가 아무리 커도 log⁡2N\log_2 N이라는 사실을 기억합시다. 20=12^0 = 1, 21=22^1 = 2, …, 2⌊log⁡2N⌋2^{\lfloor \log_2 N \rfloor}세대만큼 부모를 건너뛴 결과를 저장하더라도 공간을 O(Vlog⁡N)\mathcal{O}(V \log N)밖에 사용하지 않습니다.

dd세대를 건너뛰어야 할 때, 2⌊log⁡2d⌋2^{\lfloor \log_2 d \rfloor}만큼 건너뛸 수 있는지 확인하고 건너뛸 수 있으면 건너뜁니다. 다음으로 2⌊log⁡2d⌋−12^{\lfloor \log_2 d \rfloor - 1}만큼 건너뛸 수 있는지 확인하고 건너뛸 수 있으면 건너뜁니다. 같은 방법으로 202^0까지 반복하면 dd세대를 O(log⁡d)\mathcal{O}(\log d) 시간에 건너뛸 수 있습니다.

이제 B=VB = \sqrt{V}만큼 건너뛰던 방식을 응용해 보겠습니다. 두 정점의 높이가 같아지려면 정확히 두 정점의 높이 차만큼의 부모를 건너뛰어야 합니다. 높이 차는 최대 V−1V - 1이므로 O(log⁡V)\mathcal{O}(\log V) 시간에 건너뛸 수 있습니다.

다음으로 같은 높이에 있는 두 정점을 동시에 최소 공통 조상까지 건너뛰게 해야 합니다. 최소 공통 조상까지의 높이는 최대 O(V)\mathcal{O}(V)이므로 O(log⁡V)\mathcal{O}(\log V) 시간에 건너뛸 수 있습니다.

따라서, O(log⁡V)\mathcal{O}(\log V) 시간에 문제를 풀 수 있고, O(Vlog⁡V)\mathcal{O}(V \log V)만큼의 공간밖에 사용하지 않았습니다!

이 방법은 일반적으로 Binary Jumping이라 불리며 이분 탐색의 응용으로도 볼 수 있습니다. 가장 흔하게 사용되는 최소 공통 조상 알고리즘인 것 같습니다. 전처리를 포함한 시간은 O((V+Q)log⁡V)\mathcal{O}((V + Q) \log V)로, Vlog⁡VV \log V 항이 추가된다는 단점이 있습니다. 또한 메모리 사용량 및 접근 규칙이 다소 비효율적이라 다른 O~(1)\tilde{\mathcal{O}}(1) 구현에 비해 성능이 약간 떨어질 수 있습니다.

어떻게 하면 더 잘할 수 있을까요?

경쇄-중쇄 분할

경쇄-중쇄 분할Heavy-Light Decomposition은 트리를 직선 경로인 사슬로 나누는 방법입니다. 자세한 구현과 원리는 설멍하지 않겠지만, 각 사슬마다 가장 얕은 정점을 저장해 두면 O(1)\mathcal{O}(1) 시간에 사슬의 길이만큼 부모를 건너뛸 수 있습니다. 모든 두 정점 사이의 경로는 최대 log⁡2V\log_2 V개의 사슬로 분할된다는 특징을 가지고 있어서, 두 정점이 같은 사슬에 위치할 때까지 사슬의 길이만큼 부모를 건너뛰면 O(log⁡V)\mathcal{O}(\log V) 시간에 최소 공통 조상을 구할 수 있습니다.

경쇄-중쇄 분할을 수행하는 데에는 O(V)\mathcal{O}(V) 시간이 걸리고, 각 정점의 깊이와 사슬의 정보 등을 저장하는 데 O(V)\mathcal{O}(V) 공간을 사용합니다. 전처리를 포함한 시간은 O(V+Qlog⁡V)\mathcal{O}(V + Q \log V)로, 시간과 공간 모두 이진 도약보다 점근적으로 우수함을 알 수 있습니다. 메모리 사용량도 적고 접근 규칙도 효율적이기 때문에 경험적인 성능 또한 우수합니다. 원리가 어렵고 코드가 이진 도약보다는 복잡하기 때문에 많이 쓰이지는 않는 것으로 보입니다.

경쇄-중쇄 분할에 대한 자세한 설명은 영문 위키백과에서, Rust 구현체는 제 코드 조각 저장소에서 보실 수 있습니다.

이번 글에서는 부모를 따르는 시뮬레이션 방식으로 최소 공통 조상을 구하는 방법들을 소개했습니다. 다음 글에서는 그래프 탐색에 기반한 최소 공통 조상 알고리즘을 살펴보겠습니다.

잘못된 내용이나 추가가 필요한 내용, 궁금하신 내용 등은 덧글로 달아주시면 감사하겠습니다. 읽어주셔서 감사합니다!

다음 글 보기