[CS 지식 - 알고리즘] 최소공통조상(LCA)

1. 최소공통조상

• 트리(Tree)구조에서 특정한 두 노드의 공통된 조상 중 가장 가까운 조상을 의미
• 특징 : 트리에서 두 노드 사이의 거리를 빠르게 구하는 등 다양한 계산에 활용가능
• 일종의 다이나믹 프로그래밍
  반드시 이진트리(Binary Tree)가 아니어도 일반적인 형태의 트리라면 적용가능
• 예시)
  
  

▶ 위와 같은 트리구조에서 13,15번 의 최소 공통조상은 5번노드가 됨

 

2. 구하는 방법

 

2-1. LCA를 선형 탐색으로 구하기 : O(Depth)

• 가장 단순한방법
• 두 포인터를 두고 가리키는 정점이 같아질때까지 부모노드로 거슬러 올라가면 됨
  ▶ Parent[x]를 정점x의 부모노드라 할때, x =Parent[x]연산을 반복하면 됨

• 위의 그림과 같이 두정점의 LEVEL(깊이)가 다르다면 문제가 발생
  13번은 깊이가 4, 11번은 3임

• 깊이를 맞춘 후 9번과 11번의 정점의 최소 공통 조상을 구하는 문제로 바꿈
  ▶ 두 정점의 깊이가 같기 때문에, 동시에 거슬러 올라가면 됨

 

2-2. LCA를 이분 탐색으로 구하기 : O(log(Depth)

• 시간 효율적
• Parent배열을 2차원으로 두어, Parent[x][k] ='x번 정점의 2^k번째 조상 노드의 번호'
• 예시)

• 만약 DFS를 통해 Root부터 트리를 구성한다면, 낮은 깊이의 노드르 반드시 먼저 탐색하므로 다음이 성립한다

• 선형 시간에 구하는 방법에서 부모 노드로 거슬러가는 과정을 2의 제곱수만큼 한번에 건너 뛸 수 있음
• 만약 13,4번 정점의 최소 공통조상을 구한다면, 13번 정점의 깊이를 4번 정점의 깊이로 맞추기 위해
  5번 정점으로 바로 거슬러 올라간 뒤, 2번 정점으로 거슬러 올라 갈 수 있음

**예제문제)

https://www.acmicpc.net/problem/11437

11437번: LCA

 

참고)

https://coding-food-court.tistory.com/213#recentComments

LCA 최소 공통 조상

https://4legs-study.tistory.com/121

최소 공통 조상 (LCA, Lowest Common Ancestor)