최소 공통 조상 솔루션

[1. 개요]

최소 공통 조상 문제는 보통 트리에서 임의의 두 노드가 있을 때,

두 노드의 공통 조상을 찾는 문제이다.

트리를 대상으로 하기 때문에,

어떤 노드의 부모노드는 단 하나 만 존재하게 된다.

최소 공통 조상을 찾는 방법은 아래와 같다.

먼저 height 를 계산해야 한다.

위 그림에서 왼쪽 트리는 root 가 5인 균형잡힌 노드이다.

오른쪽 트리는 왼쪽 트리에서 root 를 1로 했을 때의 모습이다.
즉, 왼쪽 트리와 오른쪽 트리는 본질적으로 같다.

그래서 tree 가 입력으로 주어졌을 때, LCA 를 찾기 위해서 임의의 노드를 root 로 잡아도 된다.

두번째와 세번째 과정은 비슷한 원리로 동작 한다.

sparse table 을 이용하여 빠르게 찾는데,

이 table 을 최초 1회 생성하면,

table 을 이용하여 LCA 를 찾는 과정은 상수 시간에 수렴한다.

sparse table 에 대한 이해는 아래 그림으로 설명 가능하다.

이 그림을 일반화 하면,

u 의 2^N 번째 조상 == u 의 2^N-1 번째 조상의 2^N-1 번째 조상

자세한 구현은 아래 예제1번 링크를 참조하도록 하고,

구현을 한가지 패턴으로 이해하도록 한다.

========= LCA 구현 패턴 ==========

root 를 1번 노드로 지정하고, dfs 를 진행하여, 각 노드의 높이와 부모 노드 등을 설정한다.
sparse table 을 구한다.
u 가 v 보다 root 에 더 가깝도록 한다.
=> 구현 패턴이다.
=> hegihts[u] > hegihts[v] 인 경우, u 와 v 를 swap 한다.
두 노드 u 와 v 의 높이를 맞춘다.
=> v 가 u 의 높이와 같아지도록, u 를 위로 올린다.
두 노드 u 와 v 가 서로 같은 경우 바로 종료한다.
=> 반드시 해주도록 한다.
n 값을 30 부터 0 까지 내려가면서 아래 작업을 수행한다.
=> u 와 v 의 2^n 번째 조상이 다른 경우, u 와 v 를 업데이트 한다.
반복문 종료 후, u 와 v 의 첫번째 조상이 찾고자 하는 LCA 이다.
=> 반드시 수행하도록 한다.

u 와 v 를 통해 접근해야 하는 테이블이 있다면,

이 테이블을 반드시 먼저 접근하고, u 와 v를 업데이트 하도록 한다.

[2. 예제]

test_kernelv2