LCA 에 관하여

최소 공통 조상(LCA, Lowest Common Ancestor) 이란 트리에서 두 노드의 가장 가까운 공통 조상을 의미합니다. 이는 트리 구조에서 두 노드 간의 관계를 파악하거나 최단 거리 등을 찾을 때 유용하게 사용됩니다.

---

1. 최소 공통 조상의 필요성

• 트리에서 두 노드 간의 관계 파악
• 효율적인 최단 경로 탐색

---

2. LCA 알고리즘의 종류

LCA를 구현하는 대표적인 방법은 다음과 같습니다.

1. 단순 탐색

• 시간 복잡도: O(N)
• 가장 간단한 방법으로, 루트에서부터 탐색하여 두 노드의 공통 조상을 찾습니다.

2. 이진 트리에서의 재귀적 탐색

• 시간 복잡도: O(N)
• 트리를 한 번 순회하면서 두 노드의 공통 조상을 찾습니다.

3. Sparse Table (희소 테이블)

• 시간 복잡도: 전처리 O(NlogN), 쿼리 O(logN)
• 희소 테이블을 활용해 빠르게 최소 공통 조상을 찾습니다.

---

3. LCA 구현(Java) - Sparse Table

import java.util.*;

public class LCA {
    private int[][] parent;
    private int[] depth;
    private ArrayList<Integer>[] tree;
    private int LOG;

    public LCA(int n) {
        LOG = (int) Math.ceil(Math.log(n) / Math.log(2));
        parent = new int[n + 1][LOG + 1];
        depth = new int[n + 1];
        tree = new ArrayList[n + 1];
        for (int i = 0; i <= n; i++) {
            tree[i] = new ArrayList<>();
        }
    }

    public void addEdge(int u, int v) {
        tree[u].add(v);
        tree[v].add(u);
    }

    public void preprocess(int node, int par) {
        depth[node] = depth[par] + 1;
        parent[node][0] = par;

        for (int i = 1; i <= LOG; i++) {
            parent[node][i] = parent[parent[node][i - 1]][i - 1];
        }

        for (int child : tree[node]) {
            if (child != par) {
                preprocess(child, node);
            }
        }
    }

    public int query(int u, int v) {
        if (depth[u] < depth[v]) {
            int temp = u;
            u = v;
            v = temp;
        }

        for (int i = LOG; i >= 0; i--) {
            if (depth[u] - (1 << i) >= depth[v]) {
                u = parent[u][i];
            }
        }

        if (u == v) return u;

        for (int i = LOG; i >= 0; i--) {
            if (parent[u][i] != parent[v][i]) {
                u = parent[u][i];
                v = parent[v][i];
            }
        }

        return parent[u][0];
    }
}

사용 예시

public class Main {
    public static void main(String[] args) {
        int n = 7; // 노드 개수
        LCA lca = new LCA(n);

        lca.addEdge(1, 2);
        lca.addEdge(1, 3);
        lca.addEdge(2, 4);
        lca.addEdge(2, 5);
        lca.addEdge(3, 6);
        lca.addEdge(3, 7);

        lca.preprocess(1, 0); // 1번 노드를 루트로 설정

        System.out.println(lca.query(4, 5)); // 출력: 2
        System.out.println(lca.query(4, 6)); // 출력: 1
        System.out.println(lca.query(3, 4)); // 출력: 1
        System.out.println(lca.query(2, 4)); // 출력: 2
    }
}

---

4. 마무리

최소 공통 조상 알고리즘은 다음과 같은 분야에서 활용됩니다.

• 그래프 및 트리 구조에서 최단 거리 계산
• 계층적 데이터에서 공통 조상 탐색
• 효율적인 경로 탐색 문제