최소 공통 조상(LCA) 알고리즘 (트리 탐색 최적화 기법)

우리가 가족의 가계도(족보)를 펼쳐놓고 나와 내 육촌 형제가 도대체 어떤 조상님을 기준으로 피가 갈라졌는지 거슬러 올라가 본 적이 있으신가요? 이 과정을 컴퓨터 과학의 트리(Tree) 자료구조에 그대로 적용한 것이 바로 최소 공통 조상(Lowest Common Ancestor, 이하 LCA) 알고리즘입니다. 코딩 테스트의 그래프나 트리 심화 문제에서 두 노드 간의 최단 거리를 구하거나, 네트워크 라우팅 경로를 최적화할 때 반드시 등장하는 핵심 알고리즘입니다. 오늘은 가장 무식하게 부모를 찾는 O(N) 방식부터, 동적 계획법(DP)의 원리를 차용하여 O(log N)으로 탐색 속도를 비약적으로 끌어올리는 희소 배열(Sparse Table) 최적화 기법까지 완벽하게 정복해 보겠습니다.

1. 최소 공통 조상(LCA)이란 무엇인가?

트리 구조에서 임의의 두 노드 $u$와 $v$가 있을 때, $u$의 조상이면서 동시에 $v$의 조상인 노드들 중에서 가장 깊이가 깊은(즉, 두 노드와 가장 가까운) 노드를 LCA라고 부릅니다. 예를 들어 회사 조직도에서 '개발 1팀원'과 '영업 2팀원'의 공통 조상을 찾으라고 하면 'CEO'도 공통 조상이지만, 이들을 가장 가까이서 묶어주는 '본부장'이나 '부사장'이 LCA가 되는 이치입니다.

2. 기초적인 LCA 탐색 방법 (O(N) 방식)

LCA를 구하는 가장 직관적이고 기본적인 아이디어는 매우 단순합니다. 두 노드가 같은 층(Depth)에 서서, 동시에 한 칸씩 위로 거슬러 올라가며 서로 만날 때까지 부모를 확인하는 것입니다.

2-1. 동작 과정 시뮬레이션

루트 노드부터 탐색(DFS 혹은 BFS)을 시작하여 모든 노드의 깊이(Depth)와 직속 부모(Parent) 정보를 배열에 미리 기록해 둡니다.
LCA를 찾을 두 노드 $u, v$의 깊이를 비교합니다.
만약 $u$가 $v$보다 더 깊은 곳에 있다면, $u$를 부모 노드로 이동시켜 두 노드의 깊이를 똑같이 맞춥니다.
깊이가 같아졌다면, 이제 두 노드가 같아질 때까지 동시에 한 칸씩 부모 노드로 거슬러 올라갑니다.
두 노드가 정확히 일치하는 순간, 그 노드가 바로 LCA입니다.

이 방식은 이해하기 쉽지만 치명적인 단점이 있습니다. 트리가 한쪽으로 심하게 쏠린 편향 트리(Skewed Tree) 형태일 경우, 최악의 상황에서 높이 $H$만큼 거슬러 올라가야 하므로 탐색 한 번에 O(N)의 시간 복잡도를 요구합니다. 쿼리(질문)가 수십만 개 쏟아지는 문제에서는 백발백중 '시간 초과'를 면치 못합니다.

3. 최적화된 LCA 알고리즘 (O(log N) 방식)

시간 초과를 피하기 위해서는 한 칸씩 올라가는 무식한 짓을 멈춰야 합니다. 거슬러 올라가는 속도를 2배, 4배, 8배로 증폭시키는 점프(Jump) 전략이 필요합니다. 이를 위해 사용하는 마법의 기술이 바로 '희소 배열(Sparse Table)'과 동적 계획법(DP)입니다.

3-1. DP를 활용한 2^K 번째 부모 미리 저장하기

최적화의 핵심은 내 바로 위(1번째) 부모만 기억하는 것이 아니라, 내 $2^K$번째 부모(1, 2, 4, 8, 16...)들을 메모리에 미리 다 계산해서 저장해 두는 것입니다.


// parent[k][v] : 노드 v의 2^k 번째 부모를 저장하는 2차원 배열
parent[k][v] = parent[k-1][parent[k-1][v]];

위 점화식이 핵심입니다. "나의 4번째 부모는, 나의 2번째 부모의 2번째 부모다"라는 논리를 이용하여 $O(N \log N)$의 시간만 투자하면 모든 노드의 조상 점프 테이블을 완벽하게 완성할 수 있습니다.

3-2. 이진 탐색을 응용한 고속 점프

이제 부모 배열이 준비되었으니 쿼리를 처리할 차례입니다.

깊이 맞추기 고속화: 두 노드의 깊이 차이가 `11`이라고 해봅시다. 11은 이진수로 `1011(2)`이므로, $8 + 2 + 1$칸의 조합으로 한 번에 크게 도약할 수 있습니다. 11번 올라갈 것을 단 3번의 점프로 해결합니다.
LCA 찾기 고속화: 깊이가 맞춰진 두 노드에서, $K$의 최댓값(트리 최대 높이의 로그값)부터 0까지 거꾸로 순회하며 점프를 시도합니다. "2^K 번째 부모가 서로 다른가?"를 묻고, 다르다면 그만큼 위로 확 점프합니다. 같으면 지나치게 많이 올라간 것이니 점프하지 않습니다. 이 과정을 거치면 마지막엔 항상 LCA의 바로 자식 노드에서 멈추게 됩니다.

이 최적화 알고리즘을 사용하면, 아무리 트리가 깊어도 한 번의 쿼리당 O(log N)이라는 경이로운 속도로 공통 조상을 찾아낼 수 있습니다.

[핵심 요약]
1. LCA 알고리즘은 트리 상의 두 노드가 만나는 가장 가깝고 깊은 공통 조상을 찾는 기법입니다.
2. 일반적인 한 칸씩 올라가는 방식은 O(N)의 시간이 걸려 대규모 쿼리 처리 시 시간 초과를 유발합니다.
3. 희소 배열(DP)을 활용해 $2^K$ 단위로 부모를 기록해 두면, 이진 탐색의 원리로 O(log N)만에 고속 점프하여 LCA를 찾을 수 있습니다.

tech-korea