토픽 59 / 82

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

트리에서 두 노드의 공통 조상 중 가장 깊은(가까운) 노드를 찾는 문제로, Binary Lifting, Sparse Table, Segment Tree 등을 사용하여 전처리 O(n log n), 쿼리 O(log n)에 해결

목적: 공통 조상 찾기, 거리 계산, 경로 쿼리

특징: 트리 전용, 전처리 필요, 여러 알고리즘, 빠른 쿼리

활용: 두 노드 간 거리 = depth[u] + depth[v] - 2×depth[LCA(u,v)]

Binary Lifting 방법: 각 노드의 2^k 번째 조상 저장(parent[u][k]), DFS로 전처리 O(n log n), 쿼리 O(log n)

동작(Binary Lifting): ① 두 노드를 같은 깊이로 맞춤 → ② 동시에 위로 이동하며 LCA 직전까지 올라감 → ③ 한 칸 위가 LCA

Euler Tour + RMQ 방법: 트리를 Euler Tour로 변환 → 깊이 배열에서 RMQ(Range Minimum Query) → Sparse Table O(n log n) 전처리, O(1) 쿼리

시간 복잡도: Binary Lifting 전처리 O(n log n), 쿼리 O(log n), RMQ 전처리 O(n log n), 쿼리 O(1)

공간 복잡도: O(n log n)

장점: 빠른 쿼리, 거리 계산, 다양한 방법

단점: 전처리 필요, 공간 사용, 트리 전용

적용사례: 두 노드 거리, 경로 쿼리, 트리 DP, 네트워크 분석

비교: Binary Lifting(log쿼리/단순) vs RMQ(O(1)쿼리/복잡) vs Naive(O(h)/전처리없음)

연관: 트리, Binary Lifting, RMQ, Sparse Table, 경로