[알고리즘 소개] Tree Algorithm - 최소 공통 조상(LCA, Lowest Common Ancestor)

어느 정도 수준있는 문제에서 많이 쓰이는 문제이다. 이 알고리즘이 메인이 된다기보다는, 다른 알고리즘(Tree DP 등등)과 짬뽕해서 조미료로 쓰이는 경우가 굉장히 많다.

 

최소 공통 조상이란?

예제 트리

다음과 같이 루트(위 그림에서 1번)가 있는 트리가 있을 때,

LCP(a,b)는 a와 b를 모두 자식으로 가지는 노드들 중에서 a와 b에 가장 거리가 짧은 조상을 말한다.

 

예를 들어 LCP(7,9)=2, LCP(10,12)=6, LCP(7,10)=1이 된다.

a가 b의 조상인 경우, 혹은 그 역인 경우 LCP의 값이 a 혹은 b가 될 수 있다(ex. LCP(7,1)=1)

 

일반적으로 LCP(a,b)의 쿼리가 Q개 있는 경우 DFS, BFS 등 일반적인 Search Algorithm을 사용하면 O(NQ)가 걸릴 것이다. 여기에서의 목표는 각 쿼리당 O(logN)까지 줄이는 것을 목표로 한다.

 

- Overview

이 알고리즘에서 꼭 알아야 하는 핵심 아이디어는 다음과 같다:

1. 각 노드들마다 자신의 깊이(root node로부터의 거리), 그리고 2^k번째(1,2,4,8..번째) 조상을 저장한다.
2. 어떻게든 LCS를 구한다(...)

어떻게든 구한다는 게 사실 그리 쉬운 일은 아니지만, 적어도 1번을 까먹지 않는다면 2번은 어떻게든 유도가 되기 때문에(개인적인 경험으로서) 1번이 가장 중요하다고 생각한다.

 

- LCS 전처리

각 노드들마다 (1) 깊이, (2) 2^k번째(1,2,4,8..번째) 조상을 미리 구해놓는다.

시간복잡도는 O(NlogN)

- LCS 구하기.

어떻게든 LCS를 구한다고 했긴 했는데... 여기도 사실 두 step으로 나눠진다.

1. 두 노드 a,b의 depth를 맞춘다. 즉, depth가 높은 노드를 낮은 노드의 depth에 맞게 올린다. 2. a,b의 2^k번째 조상을 찾아가면서 lca(a,b)를 찾는다.

 

1. 두 노드 a,b의 depth 맞추기

root가 1인 트리. 위의 예시에서 (a,b) = (11,13)이다.

(a,b) = (11,13)이라고 했을 때,

depth(a) = depth(11) = 10,

depth(b) = depth(13) = 7이다.

따라서 a를 높이 3만큼 올려주어야 한다. 

이 때, 우리는 각 노드들마다 2^k번째 조상노드에 대해서 알고 있다!

따라서 이를 이용하면 O(logN)만에 올릴 수 있다.

소스코드는 다음과 같다.

2. LCA 구하기

a, b의 depth가 같아졌기 때문에 a, b의 공통 조상들은 모두 a,b에 대해서 거리가 같다.

이를 이용해서 최소 공통 조상을 찾아보자.

 

[0] a와 b가 같다면 a, b 자체가 LCS이다. 이 경우가 아니라면 아래를 실행한다.

[1] depth(a)/2 < 2^k ≤ depth(a) 인 k를 찾아 초기화한다.
[2] a와 b의 2^k번째 조상을 비교한다(2^k번째 조상이 없다면 k를 1 감소시킨다)
    - 만약 같다면, a와 b를 그대로 둔다.
    - 만약 다르다면, a와 b를 2^k번째 조상으로 이동시킨다.
[3] k가 음수가 되기 전까지 k를 1 감소시키고 (2)를 반복한다.
[4] [2]~[3]이 끝났다면, a,b의 바로 윗 조상이 LCA이다.

이를 그림으로 쉽게 풀어쓰면 다음과 같다.

 

소스코드는 다음과 같다

 

- 연습문제들

https://www.acmicpc.net/step/40

최소 공통 조상 단계

https://www.acmicpc.net/problemset?sort=ac_desc&algo=41 

문제 - 1 페이지

연습문제는 많이 푸는 것도 중요하지만, 얼만큼 자신의 힘으로 풀어나갔는지가 훨씬 중요합니다.

최대한 다른 소스, 다른 사람들의 소스를 보지 말고 자신이 기억한 알고리즘을 계속 떠올리면서 하면 좋을 것 같습니다.