[c++] 가장 가까운 공통 조상(Lowest Common Ancestor)

12 Dec 2023

가장 가까운 공통 조상(Lowest Common Ancestor, LCA)은 이진 트리에서 두 노드의 가장 가까운 공통 조상을 찾는 알고리즘입니다.

Algorithm

Depth-First Search (DFS) : 루트부터 잎 노드까지 이동하며 노드의 부모 정보와 각 노드의 깊이를 저장합니다.
Sparse Table : 이진 트리에서 LCA를 빠르게 찾기 위해 희소 테이블을 만듭니다.
LCA Query : 희소 테이블을 사용하여 두 노드의 가장 가까운 공통 조상을 찾습니다.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 10005;
const int LOGN = 15; // log2(MAXN)

int n, timer;
vector<int> adj[MAXN]; // adjacency list
int parent[MAXN][LOGN]; // parent[i][j]는 i의 2^j번째 조상을 나타냄
int depth[MAXN]; // 각 노드의 깊이

void dfs(int v, int par, int d) {
    depth[v] = d;
    parent[v][0] = par;
    for (int i = 0; i < adj[v].size(); i++) {
        int u = adj[v][i];
        if (u != par)
            dfs(u, v, d+1);
    }
}

void buildSparseTable() {
    for (int j = 1; j < LOGN; j++) {
        for (int i = 1; i <= n; i++) {
            if (parent[i][j-1] != -1)
                parent[i][j] = parent[parent[i][j-1]][j-1];
        }
    }
}

int lca(int u, int v) {
    if (depth[u] < depth[v])
        swap(u, v);

    int diff = depth[u] - depth[v];
    for (int i = 0; i < LOGN; i++) {
        if (diff & (1 << i))
            u = parent[u][i];
    }

    if (u == v)
        return u;

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

시간 복잡도 및 공간 복잡도

DFS : O(N)
희소 테이블 구축 : O(NlogN)
LCA 쿼리 : O(logN)
공간 복잡도 : O(NlogN)

이 알고리즘은 효율적으로 LCA를 찾을 수 있는데, 트리의 노드 수(N)에 대해 O(NlogN)의 공간과 시간 복잡도가 소요됩니다.

결론

가장 가까운 공통 조상 알고리즘은 이진 트리에서 두 노드의 LCA를 효율적으로 찾는 알고리즘입니다. 이를 위해 DFS와 희소 테이블을 사용하여 쿼리 시간을 최적화하고, O(logN) 시간 안에 LCA를 찾을 수 있습니다.

더 자세한 내용은 다음을 참고하세요.