최소 공통 조상 (Lowest Common Ancestor) 정의, 원리

이것이 코딩테스트다. 나동빈 신님의 강의를 바탕으로 작성하였습니다.

---

최소 공통 조상

N(2 ≤ N ≤ 50,000)개의 정점으로 이루어진 트리가 주어진다. 
트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.
두 노드의 쌍 M(1 ≤ M ≤ 10,000)개가 주어졌을 때,
 두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.
 

 최소 공통 조상(LCA) 문제는 '두 노드의 공통된 조상 중에서 가장 가까운 조상을 찾는 문제'
  

 기본적인 최소 공통 조상 알고리즘

 최소 공통 조상 찾기 알고리즘 원리
 1) 모든 노드에 대한 깊이를 계산함.
 2) 최소 공통 조상을 찾을 두 노드를 확인함.
  2-1) 먼저 두 노드의 깊이가 동일하도록 거슬러 올라갑니다.
  2-2) 이후에 부모가 같아질 때까지 반복적으로 두 노드의 부모 방향으로 거슬러 올라감.
 3) 모든 LCA (a,b) 연산에 대하여 2번의 과정을 반복함.

 매 쿼리마다 부모의 방향으로 거슬러 올라가기 위해 최악의 경우 O(N)의 시간 복잡도 요구
  >따라서 모든 쿼리를 처리할 때의 복잡도는 O(NM) 임.

 

 

 예시)
 N(2 ≤ N ≤ 100,000)개의 정점으로 이루어진 트리가 주어진다. 
트리의 각 정점은 1번부터 N번까지 번호가 매겨져 있으며, 루트는 1번이다.

두 노드의 쌍 M(1 ≤ M ≤ 100,000)개가 주어졌을 때, 
두 노드의 가장 가까운 공통 조상이 몇 번인지 출력한다.

 각 노드가 '거슬러 올라가는 속도를 빠르게 만드는 방법' 에 대해 고민하여 본다.
  -만약 총 "15칸 거슬러 올라가야 한다"
 2의 제곱 형태로 거슬러 올라가도록 하면 O(logN)의 시간 복잡도를 보장할 수 있음.
 메모리를 조금 더 사용하여 각 노드에 대해 2 i승 번째 부모에 대한 정보를 기록함.
 > 다이나믹 프로그래밍을 이용해 시간 복잡도를 개선할 수 있음.

  세그먼트 트리를 이용하는 방법도 존재함.
 > 매 쿼리마다 부모를 거슬러 올라가기 위해 O(logN)의 복잡도가 필요함.
  따라서 모든 쿼리를 처리할 때의 시간 복잡도는 O(MlogN)임.

 

 

---