최소 공통 조상 (LCA)

최소 공통 조상(LCA, Lowest Common Ancestor)은 트리에서 두 정점이 위로 올라가다 처음 만나는 부모 정점을 찾는 알고리즘입니다.

한눈에 보기

족보를 떠올리면 쉽습니다. 나와 사촌동생의 "가장 가까운 공통 조상"은 할아버지입니다. 나와 친동생이라면 부모님이 되고요. 이렇게 두 사람의 조상 줄기가 처음 합쳐지는 지점이 LCA입니다.

→ 두 정점이 만나는 최초 부모 정점을 찾는 것!

아래 그림에서 화살표는 자식에서 부모 쪽을 가리킵니다. x와 y에서 각각 위로 올라가면 초록색 정점들을 함께 지나는데(공통 조상), 그중 가장 아래에 있는 진한 초록색 정점이 LCA입니다.

그림 출처: Wikimedia Commons (CC BY-SA 4.0, Qwertyus)

트리가 아래와 같이 주어졌다고 해 보겠습니다. (1이 맨 위 루트)

• 1
  • 2
    • 4
    • 5
  • 3
    • 6
    • 7

질문	위로 올라가는 길	LCA
4와 5의 LCA는?	4 → 2, 5 → 2	첫 부모 정점은 2
4와 6의 LCA는?	4 → 2 → 1, 6 → 3 → 1	첫 부모 정점은 루트인 1
2와 5의 LCA는?	5 → 2 (2는 자기 자신)	2

마지막 줄처럼 한 정점이 다른 정점의 조상이면, 그 정점 자신이 LCA입니다. (자기 자신도 자기의 조상으로 봅니다.)

어떻게 찾나요?

각 정점의 depth(깊이) 와 parent(부모) 를 저장해 두는 방식입니다.

depth는 루트에서 몇 칸 내려왔는지입니다. 위 트리의 depth는 아래와 같습니다.

depth	정점
0	1 (루트 정점)
1	2, 3
2	4, 5, 6, 7

parent는 정점마다 가지는 부모 정점입니다. 루트는 부모가 없기 때문에 0으로 적습니다.

정점	1	2	3	4	5	6	7
parent	0	1	1	2	2	3	3

코드에서 parent[정점 번호]로 바로 꺼내 쓰려면 0번 칸을 비워 두고 parent = [0, 0, 1, 1, 2, 2, 3, 3]처럼 저장합니다. depth와 parent는 루트에서 BFS나 DFS로 한 번 내려가면서 채울 수 있습니다.

동작 과정

이 두 배열을 활용하면 두 정점 a, b가 주어졌을 때 LCA를 찾을 수 있습니다. 아래를 반복합니다.

1. a와 b가 같은 정점이면, 그 정점이 LCA입니다. (종료)
2. depth가 같으면, 두 정점을 모두 자신의 parent로 한 칸 올립니다.
3. depth가 다르면, 더 깊은 정점만 자신의 parent로 한 칸 올립니다. (depth가 줄어듦)

한 줄로 보면: 깊이 맞추기 → 같이 한 칸씩 올라가기 → 만나는 순간이 LCA.

예시 1) 4와 6의 LCA

단계	a	b	depth(a), depth(b)	한 일
시작	4	6	2, 2	깊이가 같고 정점은 다름 → 둘 다 부모로
1	2	3	1, 1	깊이가 같고 정점은 다름 → 둘 다 부모로
2	1	1	0, 0	같은 정점 → LCA = 1

예시 2) 5와 2의 LCA

단계	a	b	depth(a), depth(b)	한 일
시작	5	2	2, 1	5가 더 깊음 → 5만 부모로
1	2	2	1, 1	같은 정점 → LCA = 2

예시 2에서 "두 정점의 parent가 같은지"만 비교하면, 2와 2의 parent인 1을 답으로 내는 실수를 합니다. 그래서 정점 자체가 같은지부터 확인해야 합니다.

Python 코드

from collections import deque


def build_tree(n, edges, root=1):
    # 1. 연결 정보(인접 리스트) 만들기
    graph = [[] for _ in range(n + 1)]
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)

    # 2. 루트에서 BFS로 내려가며 depth와 parent 채우기
    depth = [0] * (n + 1)
    parent = [0] * (n + 1)           # 루트는 부모가 없으므로 0
    visited = [False] * (n + 1)
    visited[root] = True
    queue = deque([root])
    while queue:
        cur = queue.popleft()
        for nxt in graph[cur]:
            if not visited[nxt]:
                visited[nxt] = True
                depth[nxt] = depth[cur] + 1
                parent[nxt] = cur
                queue.append(nxt)
    return depth, parent


def lca(a, b, depth, parent):
    while True:
        # 3. 같은 정점이 되면 그 정점이 LCA
        if a == b:
            return a
        # 4. 깊이가 같으면 둘 다 한 칸씩 위로
        if depth[a] == depth[b]:
            a, b = parent[a], parent[b]
        # 5. 깊이가 다르면 더 깊은 쪽만 한 칸 위로
        elif depth[a] > depth[b]:
            a = parent[a]
        else:
            b = parent[b]


edges = [(1, 2), (1, 3), (2, 4), (2, 5), (3, 6), (3, 7)]
depth, parent = build_tree(7, edges)
print(depth[1:])                 # 출력: [0, 1, 1, 2, 2, 2, 2]
print(parent[1:])                # 출력: [0, 1, 1, 2, 2, 3, 3]
print(lca(4, 5, depth, parent))  # 출력: 2
print(lca(4, 6, depth, parent))  # 출력: 1
print(lca(2, 4, depth, parent))  # 출력: 2

1. 간선 목록을 "정점마다 이웃 목록"으로 바꿉니다. 트리의 간선은 방향이 없으니 양쪽에 넣습니다.
2. 루트에서 BFS로 내려가며, 처음 만난 이웃의 depth는 "내 depth + 1", parent는 "나"로 적습니다.
3. 두 정점이 같아지면 그곳이 처음 만나는 지점, 곧 LCA입니다. 이 확인을 가장 먼저 해야 한 정점이 다른 정점의 조상인 경우도 맞게 처리됩니다.
4. 깊이가 같은데 정점이 다르면, 아직 만나지 못한 것이므로 둘 다 한 칸 올라갑니다.
5. 깊이가 다르면 깊은 쪽만 올려서 먼저 높이를 맞춥니다.

더 빠르게: 2의 거듭제곱 칸씩 점프하기

위 방법은 한 칸씩 올라가므로, 트리가 한 줄로 길게 늘어져 있으면 질문 한 번에 최대 N번 올라갑니다. 질문이 많을 때는 "2칸 위, 4칸 위, 8칸 위 조상"을 미리 표로 만들어 두고 크게 점프하는 방법(희소 배열, Binary Lifting)을 씁니다. 원문에는 없는 보충 내용입니다.

def build_table(n, parent):
    # 1. LOG = 2^LOG >= n 이 되는 가장 작은 지수
    LOG = max(1, n.bit_length())
    # 2. up[k][v] = v에서 2^k칸 위 조상 (없으면 0)
    up = [parent[:]]
    for k in range(1, LOG):
        prev = up[k - 1]
        up.append([prev[prev[v]] for v in range(n + 1)])
    return up


def lca_fast(a, b, depth, up):
    # 3. a를 더 깊은 쪽으로 맞추기
    if depth[a] < depth[b]:
        a, b = b, a
    # 4. 깊이 차이를 2진수로 쪼개 한 번에 점프
    diff = depth[a] - depth[b]
    k = 0
    while diff:
        if diff & 1:
            a = up[k][a]
        diff >>= 1
        k += 1
    if a == b:
        return a
    # 5. 조상이 달라지는 동안 큰 점프부터 같이 올라가기
    for k in range(len(up) - 1, -1, -1):
        if up[k][a] != up[k][b]:
            a, b = up[k][a], up[k][b]
    return up[0][a]


depth = [0, 0, 1, 1, 2, 2, 2, 2]
parent = [0, 0, 1, 1, 2, 2, 3, 3]
up = build_table(7, parent)
print(lca_fast(4, 5, depth, up))  # 출력: 2
print(lca_fast(4, 6, depth, up))  # 출력: 1
print(lca_fast(7, 3, depth, up))  # 출력: 3

1. 깊이는 N보다 작으니, 2의 거듭제곱 점프는 N의 비트 수만큼만 준비하면 충분합니다.
2. "2^k칸 위" = "2^(k-1)칸 위에서 다시 2^(k-1)칸 위"라는 성질로 표를 채웁니다. 루트 위는 0이고, 0의 부모도 0이라 표 밖으로 나가지 않습니다.
3. 항상 a가 더 깊도록 자리를 바꿔 둡니다.
4. 깊이 차이가 5(2진수 101)라면 1칸, 4칸 점프 두 번으로 높이를 맞춥니다.
5. 큰 점프부터 시도해서, 점프한 곳이 서로 다를 때만 실제로 올라갑니다. 끝나면 두 정점은 LCA 바로 아래에 있으므로 한 칸 위가 답입니다.

시간복잡도와 공간복잡도

N은 정점 수, h는 트리 높이입니다.

방법	준비(전처리)	질문 1번: 최선	질문 1번: 평균	질문 1번: 최악	공간
한 칸씩 올라가기	O(N)	O(1)	O(h)	O(N)	O(N)
2의 거듭제곱 점프	O(N log N)	O(1)	O(log N)	O(log N)	O(N log N)

• 한 칸씩 올라가는 방법은 올라가는 횟수가 트리 높이만큼입니다. 트리가 한 줄로 늘어지면 높이가 N이 되어 최악 O(N)입니다.
• 점프 방법은 표를 만드는 데 시간과 메모리를 더 쓰는 대신, 질문마다 log N번만 점프합니다. 시간복잡도 표기가 낯설다면 시간 복잡도 글을 먼저 보세요.

활용 예

트리 문제에서 공통 조상을 찾아야 하는 문제나, 정점과 정점 사이의 이동거리 또는 방문경로를 구해야 할 경우 사용하면 됩니다.

• 두 정점 사이 거리: depth[a] + depth[b] - 2 * depth[LCA]. 예) 4와 6은 2 + 2 - 2 × 0 = 4칸 (4 → 2 → 1 → 3 → 6).
• 두 정점 사이 경로: a에서 LCA까지 올라간 길 + LCA에서 b까지 내려가는 길.

Git의 merge-base

Git에서 두 브랜치를 합칠 때(merge), 먼저 두 브랜치가 갈라지기 직전의 공통 커밋(merge-base)을 찾습니다. 그 지점과 비교해야 "각자 무엇을 바꿨는지" 알 수 있기 때문입니다. 이것이 바로 LCA입니다.

다만 커밋 그래프는 부모가 여러 개일 수 있는 DAG라서 트리보다 조금 복잡합니다. 그래도 "양쪽 조상 줄기가 처음 만나는 곳"이라는 생각은 같습니다. 커밋과 부모 구조는 Mini Git 구조에서 볼 수 있습니다.

정리

개념	비전공자 버전 요약
LCA	두 사람의 족보를 거슬러 올라가 처음 겹치는 조상
depth / parent	"루트에서 몇 칸 아래인지"와 "바로 위 부모가 누구인지" 메모
기본 방법	깊이를 맞춘 뒤 같이 한 칸씩 올라가다 만나면 그곳이 답
점프 방법	2, 4, 8칸 위 조상을 미리 적어 두고 크게 뛰어 올라가기
merge-base	Git 두 브랜치가 갈라지기 직전의 공통 커밋