방대한 가계도에서 두 사람의 가장 가까운 공통 조상을 찾거나, 거대한 컴퓨터 네트워크 트리 라우팅에서 두 노드 간의 최단 통신 경로를 계산할 때 필수적으로 사용되는 알고리즘이 있습니다. 바로 최소 공통 조상(Lowest Common Ancestor, 이하 LCA)입니다. 기본적으로 트리의 부모를 한 칸씩 거슬러 올라가는 탐색 방식은 구현이 쉽지만, 트리가 한쪽으로 편향되어 있을 경우 탐색 한 번에 O(N)이라는 막대한 시간이 소요됩니다. 만약 질의(Query)가 10만 번 쏟아진다면 가차 없이 시간 초과(TLE)가 발생하게 됩니다. 이 끔찍한 병목 현상을 해결하기 위해 동적 계획법(DP)의 일종인 '희소 배열(Sparse Table)'을 도입하여, 부모 노드를 2의 거듭제곱 단위로 비약적으로 점프(Binary Lifting)하는 O(logN) 심화 탐색 기법을 완벽하게 파헤쳐 보겠습니다.
1. O(N) 탐색의 한계와 점프(Jump)의 필요성
기초적인 LCA 알고리즘은 두 노드의 깊이(Depth)를 똑같이 맞춘 후, 두 노드가 같아질 때까지 동시에 한 칸씩 위로 거슬러 올라가는 방식입니다. 100층 높이의 트리에서 밑바닥에 있는 두 노드의 공통 조상이 루트 노드라면, 무려 100번을 거슬러 올라가야 합니다. 이를 해결하기 위한 핵심 아이디어는 "1칸씩 가지 말고, 2칸, 4칸, 8칸, 16칸 단위로 한 번에 건너뛰자!"는 것입니다.
2. 2차원 희소 배열(Sparse Table) 전처리 (DP)
이 마법 같은 점프를 가능하게 하려면, 모든 노드가 자신의 1번째 부모뿐만 아니라 2번째, 4번째, 8번째 부모가 누구인지 미리 알고 있어야 합니다. 이를 위해 parent[k][v]라는 2차원 DP 배열을 선언합니다. 이 배열의 의미는 "노드 v의 $2^k$ 번째 부모 노드"입니다.
2-1. 점화식의 도출
나의 4번째($2^2$) 부모는, 나의 2번째($2^1$) 부모의 2번째($2^1$) 부모와 같습니다. 이를 일반화하면 다음과 같은 아름다운 점화식이 탄생합니다.
// LCA 희소 배열 점화식 (Java)
// 노드 v의 2^k 번째 부모 = (노드 v의 2^(k-1) 번째 부모)의 2^(k-1) 번째 부모
parent[k][v] = parent[k - 1][ parent[k - 1][v] ];
트리를 DFS나 BFS로 1회 순회하여 깊이(Depth)와 1번째 부모(parent[0][v])를 구해둔 뒤, 위 점화식을 2중 for문으로 돌려 테이블을 꽉 채웁니다. 트리의 최대 노드가 10만 개라면, 높이는 대략 $2^{17}$을 넘지 않으므로 k는 17까지만 구하면 충분합니다. 이 전처리 과정에는 O(N log N)의 시간이 소요됩니다.
3. O(log N) 속도의 LCA 탐색 시뮬레이션
이제 만반의 준비가 끝났습니다. 두 노드 A와 B의 LCA를 찾는 과정은 두 단계로 이루어집니다.
3-1. 1단계: 두 노드의 깊이(Depth) 똑같이 맞추기
A의 깊이가 15, B의 깊이가 4라고 해봅시다. A를 11칸 위로 끌어올려야 합니다. 11은 이진수로 1011(2)이므로, $8 + 2 + 1$로 쪼갤 수 있습니다. 즉, A를 8칸 점프시키고, 그다음 2칸 점프시키고, 마지막으로 1칸 점프시키면 단 3번의 연산만으로 A와 B의 깊이가 완벽하게 동일해집니다.
3-2. 2단계: 공통 조상을 향해 동시 점프하기
깊이가 같아진 A와 B가 여전히 서로 다른 노드라면, 이제 최상단 K(예: 17)부터 0까지 1씩 감소시키며 다음 로직을 수행합니다.
parent[k][A] != parent[k][B](부모가 다를 때): 공통 조상에 아직 도달하지 못했다는 뜻입니다. 주저 없이 A와 B를 동시에 $2^k$ 번째 부모로 크게 점프시킵니다.parent[k][A] == parent[k][B](부모가 같을 때): 공통 조상을 찾았거나, 공통 조상보다 더 높이 올라가 버린 상황입니다. 이때는 점프하지 않고 가만히 둡니다.
이 과정을 k가 0이 될 때까지 반복하면, A와 B는 기적처럼 LCA의 바로 직전 자식 노드에서 나란히 멈추게 됩니다. 최종적으로 parent[0][A]를 반환하면 그것이 바로 우리가 그토록 찾던 완벽한 최소 공통 조상입니다. 쿼리당 O(log N)의 시간만 소요되어, 10만 번의 쿼리도 1초 안에 가뿐히 처리해 냅니다.
1. LCA 심화 알고리즘은 치우친 트리 구조에서 공통 조상을 찾는 O(N)의 비효율을 O(log N)으로 극단적으로 단축하는 기법입니다.
2. 동적 계획법(DP)을 활용하여 노드의 $2^k$ 번째 부모를 기록하는 희소 배열(Sparse Table)을 전처리(O(N log N))하는 것이 핵심입니다.
3. 탐색 시 깊이 차이를 이진수 기반으로 점프하여 맞추고, 부모가 다를 때만 위로 도약하는 이진 리프팅(Binary Lifting) 방식을 통해 초고속으로 정답을 추출합니다.