Lowest Common Ancestor (LCA)
Tree에서 두 nodes u와 v의 LCA는, root로부터 가장 멀리(deepest) 있는 공통 조상이다.
그렇다면 어떻게 LCA를 구할 수 있을까?
Method 1
Naive 하게 root에서 각 node까지의 경로를 비교하여 풀 수 있다.
- root에서 u, v까지의 경로를 각각 배열에 저장한다
- 두 배열을 비교하여 얻은 공통 조상 중, root에서 가장 멀리 떨어진 것이 LCA이다.
시간 복잡도는 O(N)이다.
Method 2
또 다른 Naive 한 풀이는, Parent Pointer를 이용하는 것이다. method 1과 다르게, u 또는 v에서 시작해 root 방향으로 순회를 한다.
- 먼저, u에서 root로 순회하면서 ancestors를 저장한다.
- v에서 root로 순회할 때, u에서의 ancestors와 동일한 것이 있는지 확인한다. 이때, 가장 먼저 동일한 것이 곧 LCA이다.
시간 복잡도는 O(N) 이다.
Method 3
1
/ \
2 3
/ \
4 5
1
/ \
2 3
/ \
4 5
위와 같은 tree가 있을 때, DFS를 이용한 Euler tour를 한다고 해보자. sub-tree의 root인 r에 도달 했을 때, r의 자손인 u로 갔다가, 다시 r로 돌아와 다른 자손 v로 내려가게 된다. 즉, u와 v는 공통 조상인 r을 반드시 거치게 되는데, 이 특징을 이용해서 문제를 풀 수 있다.
먼저, 세 가지 배열이 필요하다.
- dfs_node[]: Euler tour로 방문하는 nodes를 순서대로 저장
- dfs_level[]: Euler tour로 방문하는 nodes의 level을 순서대로 저장
- firstOccur[]: 각 node가 Euler tour에서 처음으로 나타난 index
위 상황에서는, 다음과 같이 배열을 생성한다.
dfs_node[] = {1, 2, 4, 2, 5, 2, 1, 3, 1}
dfs_level[] = {0, 1, 2, 1, 2, 1, 0, 1, 0}
firstOccur[] = {0, 1, 7, 2, 4 }
이를 이용해서 LCA(4, 3)을 구해보자. 각 node 가 처음 발생한 index는 7, 2다. 공통 조상은 2와 7 사이에 level이 가장 낮은 node일 것이다. 이에 따라 dfs_level[2:7]를 조사하면, index = 6 일 때, level = 0으로 최소인 이 node가 곧 lca가 되며, dfs_node[6]를 통해 node 1인 것을 확인할 수 있다.
이때, 구간의 최소를 하나하나 비교하여 찾는 것이 아니라, Segment Tree를 기반으로 한 Range Minimum Query(RMQ)로 찾으면 더 빠를 것이다.
시간복잡도는, DFS를 통해 배열을 생성하고 Segment Tree를 생성하는데 O(N)이고, 매 Query마다 O(logN)이다.
Method 4
method 2에서는 root 방향으로 순회하며 서로의 ancestors를 비교한다. 그러나, 모든 ancestors를 하나하나 비교하기 때문에 빠르지 않다. 대신에, Binary Search에서 찾으려는 값이 mid보다 작으면 (l, mid-1)를 조사하고, mid보다 크면 (mid+1, r)을 조사하는 것처럼, ancestor의 조사 구간을 선택하면서 풀면 더 빠를 것이다.
먼저, 다음과 같이 각 node의 2^k 번째 조상을 미리 저장한다.
memo[i][j] = i-th node의 (2^j)-th ancestor
= memo[ memo[i][j-1] ][j-1]
( 0 <= j <= log ), ( log = ceil( log2(N) ) )
이를 이용하여 Binary 하게 LCA를 찾는다.
1. u 와 v의 level을 동일하게 맞춘다. 이때, u == v 라면, 다른 하나가 조상인 것이다.
2. loop j: log to 0
if ( memo[u][j] != memo[v][j] ){
u = memo[u][j];
v = memo[v][j];
}
3. memo[u][0] 이 LCA이다. (memo[v][0])
이렇게 Dynamic Programming을 이용해서 Binary하게 LCA를 찾을 수 있는데, 이를 Binary Lifting 방법이라고 부른다.
시간 복잡도는, dp 생성에 O(NlogN)이고, 매 Query마다 O(logN)이다.
(이러한 형식의 rmq용 data structure를 sparse table 이라고도 부른다.)
Author And Source
이 문제에 관하여(Lowest Common Ancestor (LCA)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@smsh0722/Lowest-Common-Ancestor-LCA저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)