본문 바로가기
CS/알고리즘

[Algorithm/알고리즘] LCA - 최소 공통 조상 알고리즘 이해하기

MayQ 2025. 5. 21. 22:38
반응형

소개

안녕하세요, 여러분! 오늘은 최소 공통 조상(LCA, Least Common Ancestor) 알고리에 대해 알아보겠습니다. 이 글은 트리 구조에 대해 궁금해하는 분들이나 알고리즘의 중요한 개념을 이해하려는 분들을 위해 작성되었습니다. LCA의 개념을 단계별로 설명하고 예제도 제공하여 명확히 이해할 수 있도록 도와드리겠습니다.

LCA란 무엇인가요?

트리 구조에서 두 노드의 최소 공통 조상(LCA)은 두 노드의 가장 가까운 공통 조상 노드입니다. 두 노드를 바라볼 때 가장 가까운 "부모" 노드라고 생각할 수 있습니다.

간단한 가계도를 예로 들어 보겠습니다:

      1
     / \
    2   3
   / \
  4   5

이 트리에서:

  • 노드 4와 5의 LCA는 2입니다 (2가 공통 부모이기 때문입니다).
  • 노드 4와 3의 LCA는 1입니다 (1은 루트이자 4와 3의 유일한 공통 조상입니다).

LCA가 왜 중요한가요?

LCA는 많은 트리 관련 알고리즘 문제에서 중요한 개념입니다. 이는 네트워크 라우팅, 계산 생물학, 조직도 등 다양한 분야에서 효율적으로 노드 간의 관계를 찾는 데 사용됩니다.

LCA를 찾는 방법

LCA를 찾기 위한 여러 가지 방법이 있습니다. 몇 가지 주요 방법을 자세히 알아보겠습니다.

1. Binary Lifting

Binary Lifting은 로그 시간에 LCA를 찾을 수 있는 효율적인 방법입니다. 이는 트리를 미리 처리하여 테이블을 만들어 두 노드의 LCA를 빠르게 찾을 수 있도록 합니다.

Binary Lifting 단계:

  1. 전처리:
    • 각 노드의 2^i번째 조상을 나타내는 테이블을 만듭니다.
    • 깊이 우선 탐색(DFS)을 통해 이 테이블을 채웁니다.
  2. 쿼리:
    • 두 노드의 깊이를 맞추고, 두 노드를 트리 위로 이동시키면서 공통 조상을 찾습니다.

아래는 Binary Lifting의 간단한 예제 코드입니다:

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []
        self.parent = None

# 깊이 우선 탐색(DFS)을 사용하여 각 노드의 부모와 깊이를 설정합니다.
def dfs(node, parent, depth):
    node.parent = parent  # 현재 노드의 부모를 설정합니다.
    depth[node.value] = depth[parent.value] + 1 if parent else 0  # 부모의 깊이에 1을 더하여 현재 노드의 깊이를 설정합니다.
    for child in node.children:  # 각 자식 노드에 대해
        dfs(child, node, depth)  # 재귀적으로 DFS를 수행합니다.

# Binary Lifting 전처리 작업을 수행하여 'up' 테이블을 채웁니다.
def binary_lifting_preprocess(root, n):
    MAX_LOG = 20  # 트리의 최대 깊이에 따라 조정 (여기서는 최대 20단계로 가정)
    up = [[-1] * MAX_LOG for _ in range(n)]  # 'up' 테이블을 초기화합니다.
    depth = [-1] * n  # 깊이를 저장할 리스트를 초기화합니다.

    # 각 노드의 2^i번째 조상을 채우기 위해 재귀적으로 DFS를 수행합니다.
    def dfs_lift(node, parent):
        up[node.value][0] = parent.value if parent else -1  # 2^0번째 조상을 설정합니다.
        for i in range(1, MAX_LOG):  # 2^i번째 조상을 설정하기 위해
            if up[node.value][i-1] != -1:  # 2^(i-1)번째 조상이 존재하면
                up[node.value][i] = up[up[node.value][i-1]][i-1]  # 2^i번째 조상을 설정합니다.
            else:
                break  # 더 이상 조상이 없으면 중단합니다.
        for child in node.children:  # 각 자식 노드에 대해
            if child != parent:  # 자식 노드가 부모가 아니면
                dfs_lift(child, node)  # 재귀적으로 DFS를 수행합니다.

    dfs(root, None, depth)  # 깊이를 채우기 위한 DFS
    dfs_lift(root, None)    # Binary Lifting 테이블을 채우기 위한 DFS
    return up, depth  # 'up' 테이블과 깊이 리스트를 반환합니다.

# 두 노드의 LCA를 찾는 함수입니다.
def lca_binary_lifting(u, v, up, depth):
    if depth[u.value] < depth[v.value]:  # v의 깊이가 더 깊으면
        u, v = v, u  # u와 v를 교환합니다.

    MAX_LOG = len(up[0])
    diff = depth[u.value] - depth[v.value]  # 두 노드의 깊이 차이를 계산합니다.

    # 두 노드의 깊이를 맞춥니다.
    for i in range(MAX_LOG):
        if (diff >> i) & 1:  # 깊이 차이의 i번째 비트가 1이면
            u = u.parent  # u를 위로 이동시킵니다.

    if u == v:  # 깊이를 맞춘 후 두 노드가 같으면
        return u  # u를 반환합니다.

    # 공통 조상을 찾습니다.
    for i in range(MAX_LOG - 1, -1, -1):  # 높은 차수부터 낮은 차수로 내려가면서
        if up[u.value][i] != up[v.value][i]:  # 두 노드의 2^i번째 조상이 다르면
            u = u.parent  # u를 위로 이동시킵니다.
            v = v.parent  # v를 위로 이동시킵니다.

    return u.parent  # 공통 조상을 반환합니다.

# 예제 트리 생성
root = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)
root.children = [node2, node3]
node2.children = [node4, node5]

# 트리 전처리
up, depth = binary_lifting_preprocess(root, 6)

# LCA 찾기
result = lca_binary_lifting(node4, node5, up, depth)
print(f'{node4.value}와 {node5.value}의 LCA는 {result.value}입니다.')  # 출력: 4와 5의 LCA는 2입니다.

2. Euler Tour + RMQ (Range Minimum Query)

이 방법은 트리의 오일러 투어를 만든 후, 범위 최소 쿼리(RMQ)를 사용하여 LCA를 찾는 방식입니다. 오일러 투어는 트리를 순회하여 각 노드를 여러 번 방문하는 방법입니다.

Euler Tour + RMQ 단계:

  1. 오일러 투어:
    • 깊이 우선 탐색(DFS)을 수행하여 오일러 투어를 생성합니다.
    • 각 노드의 첫 번째 발생 위치를 기록합니다.
  2. 범위 최소 쿼리:
    • 세그먼트 트리와 같은 데이터 구조를 사용하여 오일러 투어를 전처리합니다.
    • 주어진 쿼리에 대해 RMQ를 사용하여 LCA를 찾습니다.

아래는 예제입니다:

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []

# 오일러 투어를 수행하여 각 노드의 첫 번째 발생 위치와 깊이를 기록합니다.
def euler_tour(node, depth, first_occurrence, euler, heights, d):
    first_occurrence[node.value] = len(euler)  # 현재 노드의 첫 번째 발생 위치를 기록합니다.
    euler.append(node.value)  # 오일러 투어에 현재 노드를 추가합니다.
    heights.append(d)  # 현재 노드의 깊이를 기록합니다.
    for child in node.children:  # 각 자식 노드에 대해
        euler_tour(child, depth, first_occurrence, euler, heights, d + 1)  # 재귀적으로 DFS를 수행합니다.
        euler.append(node.value)  # 자식 노드를 방문한 후 다시 현재 노드를 추가합니다.
        heights.append(d)  # 현재 노드의 깊이를 다시 기록합니다.

# 세그먼트 트리를 빌드합니다.
def build_segment_tree(heights):
    n = len(heights)  # 높이 배열의 길이를 가져옵니다.
    seg_tree = [0] * (2 * n)  # 세그먼트 트리 배열을 초기화합니다.
    for i in range(n):  # 높이 배열의 각 요소에 대해
        seg_tree[n + i] = (heights[i], i)  # 세그먼트 트리의 리프 노드를 설정합니다.
    for i in range(n - 1, 0, -1):  # 세그먼트 트리의 내부 노드를 설정합니다.
        seg_tree[i] = min(seg_tree[i * 2], seg_tree[i * 2 + 1])  # 자식 노드의 최소 값을 부모 노드에 설정합니다.
    return seg_tree  # 빌드된 세그먼트 트리를 반환합니다.

# 범위 최소 쿼리를 수행하여 두 인덱스 사이의 최소 값을 찾습니다.
def range_minimum_query(l, r, seg_tree, n):
    l += n  # l을 세그먼트 트리의 리프 노드 인덱스로 변환합니다.
    r += n  # r을 세그먼트 트리의 리프 노드 인덱스로 변환합니다.
    res = (float('inf'), -1)  # 초기 최소 값을 설정합니다.
    while l < r:  # l이 r보다 작은 동안
        if l % 2:  # l이 홀수이면
            res = min(res, seg_tree[l])  # 현재 l의 값을 결과에 반영합니다.
            l += 1  # l을 오른쪽으로 이동합니다.
        if r % 2:  # r이 홀수이면
            r -= 1  # r을 왼쪽으로 이동합니다.
            res = min(res, seg_tree[r])  # 현재 r의 값을 결과에 반영합니다.
        l //= 2  # l을 부모 노드로 이동합니다.
        r //= 2  # r을 부모 노드로 이동합니다.
    return res  # 최소 값을 반환합니다.

# 오일러 투어와 세그먼트 트리를 사용하여 LCA를 찾습니다.
def lca_euler_tour(root, node1, node2):
    n = 2 * len(first_occurrence) - 1  # 오일러 투어의 길이를 계산합니다.
    euler = []  # 오일러 투어를 저장할 리스트를 초기화합니다.
    heights = []  # 각 노드의 깊이를 저장할 리스트를 초기화합니다.
    first_occurrence = [-1] * (n // 2 + 1)  # 각 노드의 첫 번째 발생 위치를 저장할 리스트를 초기화합니다.
    euler_tour(root, 0, first_occurrence, euler, heights, 0)  # 오일러 투어를 수행합니다.
    seg_tree = build_segment_tree(heights)  # 세그먼트 트리를 빌드합니다.
    l, r = first_occurrence[node1.value], first_occurrence[node2.value]  # 두 노드의 첫 번째 발생 위치를 가져옵니다.
    if l > r:  # l이 r보다 크면
        l, r = r, l  # l과 r을 교환합니다.
    _, idx = range_minimum_query(l, r + 1, seg_tree, n)  # 범위 최소 쿼리를 수행합니다.
    return euler[idx]  # 최소 값의 인덱스를 반환합니다.

# 예제 트리 생성
root = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)
root.children = [node2, node3]
node2.children = [node4, node5]

# 오일러 투어 + RMQ를 사용하여 LCA 찾기
result = lca_euler_tour(root, node4, node5)
print(f'{node4.value}와 {node5.value}의 LCA는 {result}입니다.')  # 출력: 4와 5의 LCA는 2입니다.

3. Tarjan's Offline Algorithm

Tarjan의 알고리즘은 유니온-파인드 구조를 사용하여 여러 LCA 쿼리를 한 번에 처리하는 오프라인 알고리즘입니다.

Tarjan의 알고리즘 단계:

  1. DFS 순회:
    • 트리를 DFS로 순회하면서 각 쿼리를 처리합니다.
    • 유니온-파인드 구조를 사용하여 연결된 컴포넌트를 추적합니다.
  2. 유니온-파인드 연산:
    • 유니온-파인드는 집합의 병합과 각 집합의 루트 대표를 찾는 작업을 동적으로 관리합니다.

아래는 예제입니다:

class TreeNode:
    def __init__(self, value):
        self.value = value
        self.children = []
        self.parent = None

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # 각 노드의 부모를 초기화합니다.
        self.rank = [0] * n  # 각 노드의 랭크를 초기화합니다.
        self.ancestor = list(range(n))  # 각 노드의 조상을 초기화합니다.

    # 유니온-파인드의 find 연산을 수행합니다.
    def find(self, u):
        if self.parent[u] != u:  # 현재 노드가 루트가 아니면
            self.parent[u] = self.find(self.parent[u])  # 재귀적으로 루트를 찾습니다.
        return self.parent[u]  # 루트를 반환합니다.

    # 유니온-파인드의 union 연산을 수행합니다.
    def union(self, u, v):
        root_u = self.find(u)  # u의 루트를 찾습니다.
        root_v = self.find(v)  # v의 루트를 찾습니다.
        if root_u != root_v:  # 두 노드의 루트가 다르면
            if self.rank[root_u] > self.rank[root_v]:  # u의 랭크가 더 크면
                self.parent[root_v] = root_u  # v의 부모를 u로 설정합니다.
            else:  # v의 랭크가 더 크거나 같으면
                self.parent[root_u] = root_v  # u의 부모를 v로 설정합니다.
                if self.rank[root_u] == self.rank[root_v]:  # 랭크가 같으면
                    self.rank[root_v] += 1  # v의 랭크를 증가시킵니다.

# Tarjan 알고리즘을 사용하여 LCA를 찾습니다.
def tarjan_lca(node, queries, uf, results, visited):
    for child in node.children:  # 각 자식 노드에 대해
        tarjan_lca(child, queries, uf, results, visited)  # 재귀적으로 DFS를 수행합니다.
        uf.union(node.value, child.value)  # 현재 노드와 자식 노드를 병합합니다.
        uf.ancestor[uf.find(node.value)] = node.value  # 현재 노드의 조상을 설정합니다.
    visited[node.value] = True  # 현재 노드를 방문했다고 표시합니다.
    if node.value in queries:  # 현재 노드에 쿼리가 있으면
        for other in queries[node.value]:  # 각 쿼리에 대해
            if visited[other]:  # 쿼리의 다른 노드를 방문했으면
                results[(node.value, other)] = uf.ancestor[uf.find(other)]  # 결과를 설정합니다.
                results[(other, node.value)] = uf.ancestor[uf.find(other)]  # 쿼리의 반대 방향도 설정합니다.

# 예제 트리 생성
root = TreeNode(1)
node2 = TreeNode(2)
node3 = TreeNode(3)
node4 = TreeNode(4)
node5 = TreeNode(5)
root.children = [node2, node3]
node2.children = [node4, node5]

# 쿼리 설정
queries = {4: [5], 5: [4]}  # 예를 들어, 4와 5의 LCA를 알고 싶다고 가정합니다.
results = {}  # 결과를 저장할 딕셔너리를 초기화합니다.
visited = [False] * 6  # 각 노드의 방문 여부를 저장할 리스트를 초기화합니다.
uf = UnionFind(6)  # 유니온-파인드 구조를 초기화합니다.

# Tarjan 알고리즘으로 LCA 찾기
tarjan_lca(root, queries, uf, results, visited)

# 결과 출력
for key, value in results.items():
    print(f'{key[0]}와 {key[1]}의 LCA는 {value}입니다.')  # 출력: 4와 5의 LCA는 2입니다.

마무리

이번 포스트에서는 트리 구조에서 두 노드의 최소 공통 조상(LCA)을 찾는 다양한 방법에 대해 알아보았습니다. Binary Lifting, Euler Tour + RMQ, Tarjan의 알고리즘 등 각 방법의 장점과 사용 사례를 이해하고, 실제 코드 예제를 통해 직접 구현해 보았습니다. 이러한 방법들을 이해하고 적용하면 트리 구조를 다루는 알고리즘 문제를 더욱 효율적으로 해결할 수 있습니다.

반응형

'CS > 알고리즘' 카테고리의 다른 글

[Algorithm/알고리즘] Greedy - 그리디 알고리즘(탐욕법) 이해하기  (0) 2025.05.21
[Algorithm/알고리즘] Trie - 트라이 자료구조 이해하기  (1) 2025.05.21
[Algorithm/알고리즘] DFS - 깊이 우선 탐색 알고리즘 이해하기  (0) 2025.05.21
[Algorithm/알고리즘] Backtracking - 백트래킹 알고리즘 이해하기  (0) 2025.05.21
[Algorithm/알고리즘] BFS - 너비 우선 탐색 알고리즘  (0) 2025.05.21

'CS/알고리즘' Related Articles

티스토리툴바