• 트리 그래프에서 임의의 두 노드를 선택했을 때 두 노드가 각각 자신을 포함해 거슬러 올라가면서 부모 노드를 탐색할 때 처음 공통으로 만나게 되는 부모 노드

핵심 이론

일반적인 최소 공통 조상 구하기

• 트리의 높이가 크지 않을 때 → 시간 제한이 크지 않을 때, 데이터가 많지 않을 때
• 예시) 14번, 15번 노드의 최소 공통 조상 구하기
• 먼저 루트 노드에서 탐색을 시작해 각 노드의 부모 노드와 깊이를 저장

• 트리라는 특징
  1. 바로 직전 탐색노드 = 부모 노드가 된다
  2. depth 구하기 가능
• 선택된 두 노드의 깊이가 다른 경우, 더 깊은 노드의 노드를 부모 노드로 1개씩 올려 주면서 같은 깊이로 맞춤
• 이때 두 노드가 같으면 해당 노드가 최소 공통 조상이므로 탐색을 종료

• 깊이가 같은 상태에서는 동시에 부모 노드로 올라가면서 두 노드가 같은 노드가 될 때까지 반복
• 이때 처음 만나는 노드가 최소 공통 조상

• 위와 같은 방식을 이용하면 최소 공통 조상을 구할 수 있지만, 트리의 높이가 커질 경우, 시간 제약 문제에 직면
• 이러한 문제를 해결하기 위해 ‘최소 공통 조상 빠르게 구하기’ → 알고리즘을 약간 변형한 형태

최소 공통 조상 빠르게 구하기

• 서로의 깊이를 맞춰 주거나 같아지는 노드를 찾을 때 기존에 한 단계씩 올려 주는 방식에서 2^k씩 올라가 비교하는 방식