[java] 최소 공통 조상 알고리즘의 성능 분석
소개
최소 공통 조상(LCA, Lowest Common Ancestor) 알고리즘은 트리 구조에서 두 노드의 가장 가까운 공통 조상을 찾는 알고리즘입니다. 이 알고리즘은 많은 문제들에서 활용되며, 특히 그래프나 트리에서 쿼리 작업을 효율적으로 수행해야 할 때 유용합니다.
알고리즘 동작 원리
LCA 알고리즘의 핵심 아이디어는 다음과 같습니다.
- 트리를 사전탐색(preorder)으로 탐색하여 각 노드의 깊이(depth)를 저장합니다.
- 각 노드의 조상을 미리 계산하여 저장합니다.
- 주어진 두 노드의 깊이를 비교하여 더 깊이 있는 노드를 더 깊이 있는 노드와 같은 깊이로 올립니다.
- 두 노드의 깊이가 같은 경우, 조상을 비교하여 공통 조상을 찾습니다.
성능 분석
LCA 알고리즘의 성능은 주로 트리의 깊이와 쿼리 작업의 수에 의해 결정됩니다. 따라서 트리가 균형 잡혀 있는 경우(즉, 트리의 깊이가 짧은 경우)와 쿼리 작업의 수가 작은 경우에는 평균 시간 복잡도가 O(log N)입니다. 하지만 트리가 비균형한 경우(즉, 트리의 깊이가 긴 경우)에는 최악의 경우 시간 복잡도가 O(N)까지 증가할 수 있습니다.
예제 코드
// 트리 노드 클래스
class Node {
int value;
Node parent;
ArrayList<Node> children;
}
// LCA 알고리즘 구현
class LCAAlgorithm {
Node[] nodes;
int[] depth;
// 트리 초기화
void initTree(int numNodes, int[][] edges) {
nodes = new Node[numNodes];
depth = new int[numNodes];
for (int i = 0; i < numNodes; i++) {
nodes[i] = new Node();
nodes[i].value = i;
nodes[i].children = new ArrayList<>();
}
for (int[] edge : edges) {
Node parent = nodes[edge[0]];
Node child = nodes[edge[1]];
child.parent = parent;
parent.children.add(child);
}
}
// 사전탐색으로 노드 깊이 계산
void calculateDepth(Node node, int currDepth) {
depth[node.value] = currDepth;
for (Node child : node.children) {
calculateDepth(child, currDepth + 1);
}
}
// 두 노드의 LCA 찾기
Node findLCA(Node node1, Node node2) {
while (node1 != null && node2 != null && node1 != node2) {
if (depth[node1.value] > depth[node2.value]) {
node1 = node1.parent;
} else if (depth[node2.value] > depth[node1.value]) {
node2 = node2.parent;
} else {
node1 = node1.parent;
node2 = node2.parent;
}
}
return node1;
}
}
// 예제 사용
class Main {
public static void main(String[] args) {
int numNodes = 7;
int[][] edges = {{0, 1}, {0, 2}, {1, 3}, {1, 4}, {2, 5}, {2, 6}};
LCAAlgorithm lca = new LCAAlgorithm();
lca.initTree(numNodes, edges);
lca.calculateDepth(lca.nodes[0], 0);
Node node1 = lca.nodes[4];
Node node2 = lca.nodes[6];
Node lcaNode = lca.findLCA(node1, node2);
System.out.println("LCA of " + node1.value + " and " + node2.value + " is " + lcaNode.value);
}
}
결론
최소 공통 조상(LCA) 알고리즘은 트리 구조에서 특정 두 노드의 공통 조상을 효율적으로 찾는 알고리즘입니다. 성능은 트리의 깊이와 쿼리 작업의 수에 따라 달라지며, 평균 시간 복잡도는 O(log N)입니다. 이 알고리즘을 통해 다양한 문제들을 효율적으로 해결할 수 있습니다.