🔢LCA(최소 공통 조상) 알고리즘과 경로 쿼리 성능

관련글 :

트리 기본 전처리	https://waydd.tistory.com/24
서브트리 판별 (in/out만)	https://waydd.tistory.com/98
세그먼트 트리, 펜윅 트리	https://waydd.tistory.com/99
경로 쿼리	https://waydd.tistory.com/103

 

 

1. LCA (Lowest Common Ancestor, 최소 공통 조상) 알고리즘 이란?

 

최소 공통 조상이란, 두 노드의 공통 조상 중 가장 가까운 것 (가장 깊은 것)

→→ 즉, 트리에서 두 노드의 공통 조상 중 가장 깊은 노드를 찾는 알고리즘

• parent[u][k] = u의 2^k 번째 조상 (u와 v 사이의 공통 조상은 유일)
  → 트리는 사이클 없는 연결 그래프, 한 루트에서 시작해 자식 노드들이 분기되는 계층적 구조
  → 때문에 모든 노드는 단 하나의 부모만 가짐 (유일)  (루트 제외)
      = 트리 구조에서 루트에서 어떤 노드까지의 경로는 유일 (반대로 위로 올라가는 경로도)
  → 조상 또한 하나의 경로로 올라갈 수 있음 (조상 탐색이 확정적)
  → Binary Lifting 같은 알고리즘이 동작할 수 있는 전제
• 실질적인 코드 시간은 전처리 + 쿼리 누적 합
  → 전처리 시간이 아무리 길어도, 쿼리가 많으면 쿼리 시간이 병목이됨
  → 그래서 빠른 쿼리 알고리즘이 중요  ex) LCA의 Binary Lifting 등

※ 알고리즘 동작 원리 (개념적 흐름)
①  DFS 기반 전처리
  → 트리의 루트에서 DFS를 통해 각 노드의 부모와 깊이 정보를 기록
②  두 노드 깊이 맞추기
  → 두 노드의 깊이가 다르면, 더 깊은 노드를 위로 올려 깊이를 맞춤
③ 같은(공통) 조상까지 끌어올리기
  → 두 노드를 동시에 한 단계씩 위로 끌어올리며 공통 조상 찾기)
④ 위를 통해 최초로 만나는 노드가 LCA

 

- 공통 코드 (다른 목차에도 동일하게 쓰임)

import sys
sys.setrecursionlimit(10**6)

# 전역 변수 초기화
N = ...  # 노드 수, ex) len(tree_input)
tree = [[] for _ in range(N + 1)]  # 트리 입력 받았다침

 

 

- Naive 방식 (부모 배열 + DFS 깊이 비교)

• 부모(parent) 를 알아야 위로 올라갈 수 있기 때문에, 부모 배열 필요
  → depth[], parent[] 전처리 : O(N)
• 두 노드 깊이가 다를 수 있기 때문에 깊이 맞추고, 한 칸씩 올라가며 비교 (~루트까지)
  → 처음으로 같은 조상을 만나면 그게 바로 LCA
• 느리지만 구현은 간단
• 시간 복잡도 (쿼리 1회당) : O(N)
  → 총 Q개의 쿼리 시간 : O(Q × N)

# 기본 DFS + 부모 추적, 저장 (전처리)
parent = [0] * (N + 1)  # 부모 노드 저장
depth = [0] * (N + 1)   # 깊이 저장

def dfs(u, p):
    parent[u] = p
    depth[u] = depth[p] + 1
    for v in tree[u]:
        if v != p:
            dfs(v, u)

# Naive 방식 (쿼리 처리용)
def lca(u, v):
    # 깊이 맞추기
    while depth[u] > depth[v]:
        u = parent[u]
    while depth[v] > depth[u]:
        v = parent[v]
    
    # 같은 조상 만날 때까지 위로
    while u != v:
        u = parent[u]
        v = parent[v]
    
    return u

dfs(1, 0)  # 루트를 1로 두고 시작

# 예시 호출
print(lca(4, 5))

※ 깊이를 저장하는 또 다른 전처리 방식 
- 아래의 경우 더 명확한 책임 분리 (자식일 때만 깊이를 기록)
- 하지만 루트 깊이를 직접 제어해야함

def dfs(u, p):
    parent[u][0] = p
    for v in tree[u]:
        if v != p:
            depth[v] = depth[u] + 1
            dfs(v, u)

depth[1] = 0  # 루트 노드의 깊이는 0 (암묵적 생략 가능)
dfs(1, 0)  # 루트의 부모는 없음 (0 또는 -1)

 

 

2. Binary Lifting 방식 (DP 기반, 점프 기반 방식)

 

트리에서 한 노드의 2^k번째 조상을 빠르게 찾기 위해, 각 노드의 2^k번째 부모 정보를 미리 전처리하는 방식

• 2^k 번째 조상을 미리 저장 (전처리)
  → parent 초기값 -1, 초상이 없음을 명확하게 나타내기 위해 사용 (이 구조 덕분에 로그 단위 점프 가능)
  → DFS로 depth, parent[0] 계산 (각 노드 한번씩 방문) : O(N)
  → 점프 테이블(이진 조상 테이블) 채우기(바깥 루프 log N × 안쪽 루프 N) : O(N log N)
  ※ 점프 테이블은 필요한 2^k만큼의 거리만 점프 할 수 있게 만든 희소한 저장 방식이므로 희소 테이블(Sparse Table)
  
• 두 노드의 깊이를 맞춘 후, 한 번에 log₂ 단위로 조상 비교 (= 이진 점프)
• 큰 거리 부터 먼저 점프하기 위해 reversed 사용
• depth[u] - (1 << k) >= depth[v] : u가 v보다 높은 위치에 있을 때만 (u가 몇 칸 점프할 수 있는지 확인)
  → 1 << k : 2의 k승 ( 2^k ), 이진 점프 핵심 ( 위로 k만큼 점프 )
  → LCA 결과가 잘못되거나 parent_table[u][k]가 -1이 되어 IndexError 발생 가능성 있기 때문
• parent_table[u][k] != parent_table[v][k] : u 와 v가 2^k 위 조상에서 서로 다른 경로에 있음을 의미
  → 서로 다른 조상을 가지고 있다면 아직 공통 조상 아님, 즉 올려야 함
• 시간복잡도 (쿼리 1회당) : O(log N)  (조상 테이블 구성하는 전처리와는 다름)
  → 전처리는 모든 노드에 대한 조상 계산
  → 질의는 두 노드 사이만 탐색하므로 O(log N) 
  → LCA 쿼리가 많을 때 훨씬 빠름  (Naive 방식보다 빠름)
  → 총 Q개의 쿼리 시간 : O(Q × log N)
• 공간복잡도 : O(N log N)
  → parent[node][k] = node의 2^k 번째 조상
  → node: 1 ~ N까지의 노드 수 (총 N개)
  → k: 최대 log₂N까지 점프 (총 log N개)
• 매우 빠르고 코딩 테스트에서 자주 사용 ( 전처리 + 다수 쿼리 전제가 많음)

LOG = 21  # log2(N) 이상으로 설정
parent_table = [[-1] * LOG for _ in range(N + 1)]
depth = [0] * (N + 1)

# 전처리 (DFS + 부모 정보 구성)
def dfs(node, parent):
    depth[node] = depth[parent] + 1
    parent_table[node][0] = parent
    for child in tree[node]:
        if child != parent:
            dfs(child, node)

# Binary Lifting 전처리 (점프 테이블 채우기)
for k in range(1, LOG):
    for node in range(1, N + 1):
        if parent_table[node][k - 1] != -1:
            parent_table[node][k] = parent_table[parent_table[node][k - 1]][k - 1]

# LCA 쿼리 함수
def lca_mid(u, v):
    if depth[u] < depth[v]:
        u, v = v, u

    # 깊이 맞추기
    for k in reversed(range(LOG)):
        if depth[u] - (1 << k) >= depth[v]:
            u = parent_table[u][k]

    if u == v:
        return u

    # 공통 조상 찾기 (부모가 -1인지 체크 후 비교)
    for k in reversed(range(LOG)):
        if parent_table[u][k] != -1 and parent_table[u][k] != parent_table[v][k]:
            u = parent_table[u][k]
            v = parent_table[v][k]

    return parent_table[u][0]
    
# 루트 설정 (depth[0] = 0 으로 가정)
dfs(1, 0)

※ 점프 테이블 채우기
- 중간 변수로 분리해서 접근 하면 예외 체크가 명확

for k in range(1, LOG):
    for node in range(1, N + 1):
        prev = parent_table[node][k - 1]
        if prev != -1:
            parent_table[node][k] = parent_table[prev][k - 1]​

※ LCA 함수 (안전성 중시형)
- parent_table[u][k] != -1 : u에게 2^k번째 조상이 존재할 때만
  → IndexError 방지
- parent_table[u][k] != -1 : u의 2^k번째 조상이 존재하는가?
  → 존재하지 않는데 접근하면 IndexError 또는 논리적 오류 발생 (우선 필수)
- ① depth[u] - (1 << k) >= depth[v] , ② depth[parents[u][k]] >= depth[v] 비교
  → ① u의 현재 깊이에서 2^k 만큼 올라갔을 때, v보다 깊거나 같은가 (이론적 깊이 차이 기반)
  → ② u에서 2^k 조상으로 올라간 노드의 실제 깊이 비교 (실제 부모 테이블 값 기반)
  → 논리상 같은 의도지만, ①이 단순 정수 계산 이므로 안전

def lca_safe(u, v):
    if depth[u] < depth[v]:
        u, v = v, u

    # 깊이 맞추기
    for k in reversed(range(LOG)):
        if parent_table[u][k] != -1 and depth[u] - (1 << k) >= depth[v]:
        # if parent_table[u][k] != -1 and depth[parent_table[u][k]] >= depth[v]:
            u = parent_table[u][k]

    if u == v:
        return u

    # 공통 조상 찾기
    for k in reversed(range(LOG)):
        if parent_table[u][k] != -1 and parent_table[u][k] != parent_table[v][k]:
            u = parent_table[u][k]
            v = parent_table[v][k]

    return parent_table[u][0]​

※ LCA 함수 (reversed 사용 X + 예외 검사 없음, 간결)

def lca(u, v):
    if depth[u] < depth[v]:
        u, v = v, u

    # 깊이 맞추기
    for k in range(LOG - 1, -1, -1):
        if depth[u] - (1 << k) >= depth[v]:
            u = parent_table[u][k]
    if u == v:
        return u

    # 공통 조상 찾기
    for k in range(LOG - 1, -1, -1):
        if parent_table[u][k] != parent_table[v][k]:
            u = parent_table[u][k]
            v = parent_table[v][k]
    return parent_table[u][0]​

 

 

3. Euler Tour + RMQ 기반 방식 설명 (순서 기반 방식)

 

트리에서 두 노드의 공통 조상 중 가장 깊은 노드를 빠르게 찾는 방식 (전처리 처리 + 쿼리 처리)

→ RMQ (Range Minimum Query)로 Euler Tour 중 첫 번째 등장 위치 사이 구간의 최소 깊이 노드를 찾으면 LCA가 됨

• Euler Tour(Type3) 로 트리를 배열 처럼 다룸 (전처리)
  → DFS 수행 ( Euler Tour, depth[] 구성 ) : O(N)
  → depth[i] 는 euler[i] 의 깊이, 즉 DFS 순서 저장 + 최소 깊이 찾기
• 각 노드가 Euler Tour 에 처음 등장한 위치, first_visit 배열 구성 (전처리) : O(N)
• RMQ(Sparse Table, Segment Tree 등) 구축 (전처리) : O(N log N)
• 전처리 시간복잡도 : O(N) + O(N) + O(N log N) = O(N log N)  (가장 큰 항만 남김)
• 쿼리는 O(1) 또는 O(log N) (RMQ 자료구조에 따라 다름 = 어떻게 범위 내 최소값을 계산하느냐)

 

- 전역 + Euler Tour 배열 만들기 (공통)

# 트리 구성, 노드 수 생략
euler = []
depth = []
first_visit = [0] * (N + 1)

def dfs(node, parent, d):
    first_visit[node] = len(euler)
    euler.append(node)  # 들어올 때 기록
    depth.append(d)
    for child in tree[node]:
        if child != parent:
            dfs(child, node, d + 1)
            euler.append(node)   # 자식에서 돌아올 때도 기록
            depth.append(d)

dfs(1, 0, 0)

 

 

- RMQ : Sparse Table(희소 테이블) 기반

• 전처리 O(N log N) (구간 수 = N × log N)
  → Sparse Table : 모든 구간 길이별로 미리 저장 ( 길이가 2^k인 모든 구간의 최소값 )
• qurey : 쿼리 빠름 (O(1))
  → 범위를 덮을 수 있는 가장 큰 2^k 길이를 찾아 두 구간만 비교해서 결과를 바로 반환

import math

L = len(depth)
K = math.floor(math.log2(L)) + 1
st = [[0] * L for _ in range(K)]  # 인덱스 저장용

# 초기화 (0단계)
for i in range(L):
    st[0][i] = i  # index 저장 (depth 배열의 인덱스)

# Sparse Table 구성
for k in range(1, K):
    for i in range(L - (1 << k) + 1):
        left = st[k - 1][i]
        right = st[k - 1][i + (1 << (k - 1))]
        st[k][i] = left if depth[left] < depth[right] else right

# RMQ 함수
def query(l, r):
    if l > r:
        l, r = r, l
    k = (r - l + 1).bit_length() - 1
    left = st[k][l]
    right = st[k][r - (1 << k) + 1]
    return euler[left if depth[left] < depth[right] else right]

# 예시
print("LCA(4,5):", query(first_visit[4], first_visit[5]))

 

 

- RMQ : Segment Tree 기반

• build (전처리) : O(N)
  → 리프 노드 값 : i 인덱스 (Eular Tour의 인덱스)
  → depth[i] 배열을 기준 자식들 중 깊이가 더 작은 인덱스 로 노드 병합(두 자식 노드 조합해서 부모에 저장)
       즉, 내부 노드 값 : 범위 최소값
• query : O(log N)
  → 오일러 투어에서 u, v의 등장 구간 [i, j] (폐구간) 를 찾고
  → 트리의 루트부터 시작해서 l과 r이 속한 구간들을 분할 
  → 그 구간에서 왼쪽/오른쪽 자식으로 내려가면서 탐색 depth[]가 가장 작은 인덱스 k 를 RMQ(구간 최소값)로 찾음
  → euler[] 배열에서 최소 깊이를 가진 인덱스에 해당하는 노드 반환
• res = -1 : 결과 인덱스 (아직 아무것도 안봄)

class SegmentTree:
    def __init__(self, depth):
        self.N = len(depth)
        self.size = 1
        while self.size < self.N:
            self.size *= 2
        self.tree = [0] * (2 * self.size)
        self.depth = depth
        self.build()  # 자동 빌드

    def build(self):
        # 리프 노드
        for i in range(self.N):
            self.tree[self.size + i] = i
        for i in range(self.size - 1, 0, -1):
            left = self.tree[i * 2]
            right = self.tree[i * 2 + 1]
            self.tree[i] = left if self.depth[left] < self.depth[right] else right

    def query(self, l, r):
        l += self.size
        r += self.size
        res = -1
        while l <= r:
            if l % 2 == 1:
                if res == -1 or self.depth[self.tree[l]] < self.depth[res]:
                    res = self.tree[l]
                l += 1
            if r % 2 == 0:
                if res == -1 or self.depth[self.tree[r]] < self.depth[res]:
                    res = self.tree[r]
                r -= 1
            l //= 2
            r //= 2
        return euler[res]

# Segment Tree 사용 예시
seg = SegmentTree(depth)
print("LCA(4,5):", seg.query(first_visit[4], first_visit[5]))

 

 

4. 쿼리에서의 사용

 

LCA 방식은 서브트리 포함 여부처럼 단발성 판단엔 쓸 수 있으나,

서브트리 노드 수처럼 반복 누적이 필요한 작업엔 전처리 기반 DFS 방식이 훨씬 효율적

→ 이진 점프를 기반으로 한 전처리 + 쿼리 최적화 방식( LCA + 누적합 + 깊이 등의 조합 )

 

- 서브트리 쿼리

• 서브트리 포함 판별 : LCA(u, v) == u로 판단 가능
  → 시간복잡도 : O(log N) (비교적 비효율)
  → LCA 방식도 실용성은 있지만, DFS in/out 방식이 더 빠르고 직관적 (O(1)) (단 한번만 판단)
• 서브트리 내 노드 개수 : u의 서브트리에 v가 포함되는지 확인하기 위해 LCA(u, v) == u 인지를 매번 검사해야 함
  → 시간 복잡도 : O(N log N) (비효율)
  → 매번 LCA 쿼리 (O(log N))를 수십~수백 번 반복해야 함

 

- 경로 쿼리 최적화

• 루트 ~ u 까지 경로/가중치 합(path_sum) : 누적합 + LCA ( Binary Lifting )
  → O(log N)
• u ~ v 간 간선 수 또는 거리 (경로 길이) : 깊이 정보 + LCA ( Binary Lifting )
  → O(log N)
• u ~ v 간의 노드 수 (경로 노드 개수) : 깊이 정보 + LCA ( Binary Lifting )
  →  O(1)
• 갱신이 필요한 경우는 HLD + 세그먼트 트리 사용
• 시간 복잡도(전처리) : O(N log N) (DFS + Binary Lifting)
  시간 복잡도(쿼리) : O(log N) (LCA 한 번 + 수식)
  공간 복잡도 : O(N log N) (부모 테이블 저장 등)   

 

 

5. 기타 방식 간단 소개

 

- Heavy-Light Decomposition (HLD)

• 트리에서 두 정점 간 경로 쿼리 (합, 최댓값 등) 를 빠르게 처리하기 위해 트리를 경로 단위로 나누는 기법 ( 체인 분할 )
  → 경로 쿼리를 log N으로 쪼개 처리
• 트리를 DFS로 순회하며 서브트리 크기 계산 & Heavy 자식 결정 (전처리) 
  → 자식 노드 중 서브트리 크기가 가장 큰 쪽을 Heavy edge, 나머지를 Light edge로 지정
• 다시 DFS 로 체인 분할 및 체인 번호 할당 (전처리 2)
  → Heavy edge를 따라가며 하나의 체인(chain)을 형성, 연결 (하나의 체인은 세그먼트 트리로 관리, 인덱스 매핑)
  → 루트 노드는 항상 자기 자식이 속한 체인의 시작점이며, 모든 노드는 어떤 체인에 속하게 됨
  → Light edge를 만나면 새로운 체인을 시작 (체인 간 이동은 Light edge를 통해 이뤄짐)
• 두 정점 u, v의 체인이 다를 경우,
  더 아래에 있는 체인의 루트 쪽으로 한 칸씩 올라오며 비교, 반복하면 두 정점이 같은 체인에 위치
• 두 정점이 같은 체인에 있을 경우, 깊이가 더 얕은 정점이 바로 LCA가 됨
• parent 를 -1 로 초기화 하는 이유 : 노드의 부모가 아직 설정되지 않음을 명시적으로 의미,
  heavy 를 -1 로 초기화하는 이유 : 노드의 heavy 자식이 존재하지 않음
  → 미정 상태 명확히 구분해서 존재 여부를 간단히 확인하기 위해
• 세그먼트 트리나 펜윅 트리와 같이 결합하면, 트리 경로에 대한 합, 최댓값, 업데이트 등을 O(log N)경로
  → 갱신/쿼리 모두 가능
  → 구현 복잡도는 높지만, 경로 쿼리가 빈번한 경우 유일한 해법

size = [0] * (N + 1)              # 서브트리 크기
depth = [0] * (N + 1)           # 노드 깊이
parent = [-1] * (N + 1)         # 부모 노드
heavy = [-1] * (N + 1)         # 가장 무거운 자식
in_time = [0] * (N + 1)        # 세그먼트 트리용 노드 인덱스
out_time = [0] * (N + 1)      # 나중에 필요할 수 있음
top = [0] * (N + 1)               # 체인의 시작점 (chain head)
seq = 0                               # 현재 시간 또는 인덱스 번호

# 서브트리 크기 + heavy 자식 결정
def dfs_size(u, p):
    global size, depth, parent, heavy
    size[u] = 1
    parent[u] = p
    max_sub = 0
    for v in tree[u]:
        if v == p:
            continue
        depth[v] = depth[u] + 1
        dfs_size(v, u)
        size[u] += size[v]
        if size[v] > max_sub:
            max_sub = size[v]
            heavy[u] = v

# 체인 분해 + 인덱싱
def dfs_decompose(u, h):
    global seq
    top[u] = h
    in_time[u] = seq
    seq += 1

    if heavy[u] != -1:
        dfs_decompose(heavy[u], h)  # 같은 체인 유지

    for v in tree[u]:
        if v != parent[u] and v != heavy[u]:
            dfs_decompose(v, v)  # 새로운 체인 시작

 # 루트는 1번 노드로 가정
dfs_size(1, -1)
dfs_decompose(1, 1)  #  (루트 노드, 1번 체인의 시작 = 루트노드) 부터 시작

 

print("in_time:", in_time[1:])   # 1번 노드부터 출력
print("top:", top[1:])
print("heavy:", heavy[1:])
print("depth:", depth[1:])

- Centroid Decomposition 활용

• 직접적으로 LCA 최적화된 방식은 아니지만 유도 가능
• 트리에서 중심 정점(Centroid)을 찾아 트리를 분할 (전처리)
  → 트리의 서브트리를 반복적으로 반으로 나누는 방식
• 각 정점의 경로를 Centroid 트리 상에서 추적
  → 각 정점에서 위로 올라가며 Centroid 조상들을 기록, 이 중 공통으로 등장하는 조상 중 가장 낮은 레벨의 정점
• Centroid Tree는 원래 트리와 구조가 다름, Centroid 상에서의 LCA ≠ 원래 트리에서의 LCA