카테고리 없음

최소 공통 조상 LCA 알고리즘: 트리 노드 탐색 완벽 가이드

kguidebook0001 2026. 4. 10. 09:47

계층적인 데이터를 다루는 트리(Tree) 구조에서 두 노드의 관계를 파악하는 것은 알고리즘 설계의 매우 중요한 부분입니다. 특히 두 개의 노드가 계통도 상에서 처음으로 만나는 지점을 찾는 최소 공통 조상(Lowest Common Ancestor, LCA) 알고리즘은 가계도 분석, 네트워크 라우팅, 그리고 코딩 테스트의 고난도 문제에서 빈번하게 활용됩니다. 본 포스팅에서는 LCA의 기초적인 접근법부터 대규모 트리에서도 빠르게 동작하는 희소 테이블(Sparse Table) 최적화 기법까지 2,500자 이상의 상세한 해설로 정리해 보겠습니다.

1. 최소 공통 조상(LCA)의 정의와 기초적인 탐색 원리

LCA란 트리 구조 내에서 두 노드 $u$와 $v$가 공통으로 가지는 조상 노드들 중, 가장 깊은 곳(두 노드와 가장 가까운 곳)에 위치한 노드를 의미합니다. 가장 직관적인 해결 방법은 두 노드의 깊이(Depth)를 맞춘 뒤, 한 단계씩 부모 노드로 거슬러 올라가며 같은 노드에서 만나는지를 확인하는 것입니다. 이 방식은 구현이 단순하지만 트리의 높이가 $N$일 때 최악의 경우 $O(N)$의 시간이 소요되어 대규모 쿼리 처리에는 부적합합니다.

1-1. 기초 알고리즘의 단계별 프로세스

  1. DFS(깊이 우선 탐색)를 수행하여 모든 노드의 깊이와 직계 부모 노드 정보를 기록합니다.
  2. 찾고자 하는 두 노드 중 더 깊은 곳에 있는 노드를 부모 방향으로 이동시켜 두 노드의 깊이를 동일하게 맞춥니다.
  3. 두 노드가 같아질 때까지 동시에 한 칸씩 부모 노드로 이동합니다.
  4. 두 노드가 일치하는 지점이 바로 최소 공통 조상입니다.

2. 희소 테이블(Sparse Table)을 이용한 고속 LCA 최적화

기초적인 방식의 한계를 극복하기 위해 비트 연산과 희소 테이블(Sparse Table) 기법을 도입합니다. 이는 "한 칸씩" 올라가는 대신 "$2^k$ 칸씩" 점프하여 부모를 찾는 방식입니다. 이를 위해 각 노드에 대해 $2^0, 2^1, 2^2, \dots$ 번째 조상 정보를 미리 계산해두는 전처리가 필요합니다.

2-1. 이진 점프(Binary Lifting)의 마법

전처리를 통해 $O(N \log N)$의 시간에 조상 테이블을 완성하면, 어떤 두 노드의 LCA도 $O(\log N)$의 짧은 시간 내에 찾아낼 수 있습니다. 깊이 차이가 13이라면, $2^3(8) + 2^2(4) + 2^0(1)$의 세 번의 점프만으로 깊이를 맞출 수 있게 됩니다. 이러한 이진 점프 기술은 데이터가 방대해질수록 선형 탐색과 비교할 수 없는 압도적인 성능 차이를 만들어냅니다.

3. LCA 알고리즘의 복잡도와 실제 응용 분야

최적화된 LCA 알고리즘은 $N$개의 노드와 $M$개의 쿼리가 주어졌을 때 전체 $O((N+M) \log N)$의 복잡도를 가집니다. 이는 실시간 시스템에서도 충분히 수용 가능한 수준입니다.

실무 및 문제 해결에서의 활용

  • 트리에서의 거리 계산: 두 노드 $u, v$ 사이의 거리는 dist[u] + dist[v] - 2 * dist[LCA(u, v)] 공식을 통해 상수 시간에 구할 수 있습니다.
  • 족보 및 계통 분석: 생물학적 종의 진화 계통도나 기업의 조직도 내에서 공통 분모를 찾는 시스템에 필수적입니다.
  • 네트워크 브로드캐스팅: 효율적인 데이터 전송 경로 설정을 위해 공통 분기점을 파악할 때 활용됩니다.

# 최적화된 LCA (Sparse Table) 핵심 로직 예시
def get_lca(u, v):
    # v를 항상 더 깊은 노드로 설정
    if depth[u] > depth[v]:
        u, v = v, u
    
    # 1. 깊이 맞추기 (2^k 점프 활용)
    for i in range(MAX_LOG - 1, -1, -1):
        if depth[v] - depth[u] >= (1 << i):
            v = parent[v][i]
            
    if u == v:
        return u
        
    # 2. 공통 조상 바로 아래까지 점프
    for i in range(MAX_LOG - 1, -1, -1):
        if parent[u][i] != parent[v][i]:
            u = parent[u][i]
            v = parent[v][i]
            
    return parent[u][0]
[LCA 알고리즘 핵심 요약]
1. 정의: 트리 구조에서 두 노드가 만나는 가장 낮은 위치의 공통 부모를 찾는 기법입니다.
2. 최적화: 희소 테이블을 활용한 이진 점프를 통해 쿼리당 시간 복잡도를 $O(\log N)$으로 단축합니다.
3. 응용: 트리 내 거리 측정, 의존성 관계 분석, 계층적 데이터 그룹화 등에 필수적으로 쓰입니다.