핵심 개념
이 글에서는 루트가 있는 트리에서 두 노드의 LCA(Lowest Common Ancestor, 최소 공통 조상)를 찾는 문제를 RMQ(Range Minimum Query, 구간 최솟값 쿼리) 문제로 변환하여 해결하는 방법을 소개합니다.
LCA란?
루트가 있는 트리 T에서 두 노드 a와 b의 최소 공통 조상(LCA)은 a와 b를 모두 자손으로 가지면서 루트로부터 가장 멀리 떨어진 노드를 의미합니다.
예를 들어 아래 그림에서 노드 D와 노드 I의 LCA는 노드 B입니다.
LCA 문제를 해결하는 방법은 매우 다양하며, 각 방식은 시간 복잡도와 공간 복잡도 측면에서 차이가 있습니다.
RMQ란?
RMQ(Range Minimum Query)는 배열에 적용되어, 지정된 두 인덱스 사이에서 최솟값을 가지는 원소의 위치를 찾는 기법입니다. RMQ 역시 여러 가지 방법으로 해결할 수 있으며, 이 글에서는 세그먼트 트리(Segment Tree) 기반 접근법을 설명합니다. 세그먼트 트리의 경우 전처리(preprocessing)에 O(n)의 시간이 걸리고, 구간 최솟값 쿼리 하나를 처리하는 데 O(log n)의 시간이 소요됩니다. 세그먼트 트리를 저장하는 데 필요한 추가 공간은 O(n)입니다.
LCA 문제를 RMQ로 변환하기
이 아이디어는 루트에서 시작해 트리를 오일러 투어(Euler Tour, '펜을 들지 않고 방문하는 방식')로 순회하는 것에서 출발합니다. 이는 전위 순회(preorder traversal)의 성격을 지닌 DFS(깊이 우선 탐색) 기반 순회입니다.
핵심 관찰: 위 그림에서 노드 D와 노드 I의 LCA는 노드 B인데, 이는 DFS 순회 과정에서 D와 I를 방문하는 사이에 만나는 모든 노드 중 루트에 가장 가까운 노드라는 의미입니다. 이 관찰이 바로 변환(reduction)의 핵심입니다. 다시 말해, 우리가 찾으려는 노드는 오일러 투어에서 a와 b의 연속된 등장 위치 사이에 있는 노드들 중 레벨(depth)이 최소이며 해당 레벨에서 유일한 노드입니다.
구현을 위해서는 세 개의 배열이 필요합니다.
트리 T의 오일러 투어 순서대로 방문한 노드들
오일러 투어에서 각 노드가 방문된 시점의 레벨
오일러 투어에서 각 노드가 처음 등장하는 인덱스(아무 등장 위치든 유효하지만, 편의상 첫 번째 등장 위치를 추적)
알고리즘 단계
트리에 대해 오일러 투어를 수행하고, euler 배열과 level 배열, first occurrence 배열을 채웁니다.
first occurrence 배열을 이용해 두 노드에 해당하는 인덱스를 구합니다. 이 인덱스들이 level 배열에서 RMQ 알고리즘에 전달될 쿼리 구간의 양 끝이 됩니다.
RMQ 알고리즘이 해당 구간 내 최소 레벨의 인덱스를 반환하면, 그 값을 euler 배열에 적용해 LCA를 결정합니다.
예제 코드
/* 이 C++ 프로그램은 문제를 RMQ로 변환하여 u와 v의 LCA를 찾습니다 */
#include<bits/stdc++.h>
#define V 9 // 입력 트리의 노드 수
int euler1[2*V - 1]; // 오일러 투어 순서를 저장하는 배열
int level1[2*V - 1]; // 투어 순서에서 노드들의 레벨을 저장하는 배열
int firstOccurrence1[V+1]; // 투어에서 노드가 처음 등장하는 인덱스
int ind; // euler 및 level 배열을 채우기 위한 인덱스 변수
// 이진 트리 노드 구조체
struct Node1{
int key;
struct Node1 *left, *right;
};
// 주어진 키 값으로 새로운 이진 트리 노드를 생성하는 유틸리티 함수
Node1 * newNode1(int k){
Node1 *temp = new Node1;
temp->key = k;
temp->left = temp->right = NULL;
return temp;
}
// x의 log 밑 2 값을 반환
int Log2(int x){
int ans = 0 ;
while (x>>=1) ans++;
return ans ;
}
/* 주어진 배열 인덱스 범위에서 최솟값을 재귀적으로 구하는 함수.
함수 매개변수는 다음과 같습니다.
st --> 세그먼트 트리에 대한 포인터
index --> 세그먼트 트리에서 현재 노드의 인덱스.
루트는 항상 인덱스 0에 있으므로 처음에는 0이 전달됩니다.
ss & se --> 현재 노드(st[index])가 나타내는 세그먼트의 시작/끝 인덱스
qs & qe --> 쿼리 범위의 시작/끝 인덱스
*/
int RMQUtil(int index1, int ss1, int se1, int qs1, int qe1, int *st1){
// 현재 노드의 세그먼트가 쿼리 범위에 완전히 포함되면 해당 세그먼트의 최솟값 반환
if (qs1 <= ss1 && qe1 >= se1)
return st1[index1];
// 현재 노드의 세그먼트가 쿼리 범위를 벗어난 경우
else if (se1 < qs1 || ss1 > qe1)
return -1;
// 현재 세그먼트가 쿼리 범위와 일부 겹치는 경우
int mid = (ss1 + se1)/2;
int q1 = RMQUtil(2*index1+1, ss1, mid, qs1, qe1, st1);
int q2 = RMQUtil(2*index1+2, mid+1, se1, qs1, qe1, st1);
if (q1==-1) return q2;
else if (q2==-1) return q1;
return (level1[q1] < level1[q2]) ? q1 : q2;
}
// qs(쿼리 시작)부터 qe(쿼리 끝)까지 범위 내 원소의 최솟값을 반환.
// 주로 RMQUtil()을 활용합니다.
int RMQ(int *st1, int n, int qs1, int qe1){
// 잘못된 입력 값 검사
if (qs1 < 0 || qe1 > n-1 || qs1 > qe1){
printf("Invalid Input");
return -1;
}
return RMQUtil(0, 0, n-1, qs1, qe1, st1);
}
// array[ss1..se1]에 대한 세그먼트 트리를 재귀적으로 구성하는 함수.
// si1은 세그먼트 트리 st에서 현재 노드의 인덱스입니다.
void constructSTUtil(int si1, int ss1, int se1, int arr1[], int *st1){
// 배열에 원소가 하나만 남으면 현재 노드에 저장하고 종료
if (ss1 == se1)st1[si1] = ss1;
else{
// 원소가 여러 개라면 좌우 하위 트리를 재귀적으로 처리하고,
// 두 값 중 최솟값을 현재 노드에 저장
int mid1 = (ss1 + se1)/2;
constructSTUtil(si1*2+1, ss1, mid1, arr1, st1);
constructSTUtil(si1*2+2, mid1+1, se1, arr1, st1);
if (arr1[st1[2*si1+1]] < arr1[st1[2*si1+2]])
st1[si1] = st1[2*si1+1];
else
st1[si1] = st1[2*si1+2];
}
}
/* 주어진 배열로부터 세그먼트 트리를 구성하는 함수.
세그먼트 트리 메모리를 할당하고 constructSTUtil()을 호출하여 할당된 메모리를 채웁니다 */
int *constructST(int arr1[], int n){
// 세그먼트 트리용 메모리 할당
// 세그먼트 트리의 높이
int x = Log2(n)+1;
// 세그먼트 트리의 최대 크기
int max_size = 2*(1<<x) - 1; // 2*pow(2,x) -1
int *st1 = new int[max_size];
// 할당된 메모리 st1을 채웁니다
constructSTUtil(0, 0, n-1, arr1, st1);
// 구성된 세그먼트 트리 반환
return st1;
}
// 트리 T의 오일러 투어 재귀 버전
void eulerTour(Node1 *root, int l){
/* 전달된 노드가 존재하는 경우 */
if (root){
euler1[ind] = root->key; // euler 배열에 삽입
level1[ind] = l; // level 배열에 l 삽입
ind++; // 인덱스 증가
/* 아직 방문하지 않았다면 첫 등장 위치 기록 */
if (firstOccurrence1[root->key] == -1)
firstOccurrence1[root->key] = ind-1;
/* 왼쪽 서브트리가 존재하면 순회하고,
돌아올 때 부모 노드의 euler와 level 배열을 다시 기록 */
if (root->left){
eulerTour(root->left, l+1);
euler1[ind]=root->key;
level1[ind] = l;
ind++;
}
/* 오른쪽 서브트리가 존재하면 순회하고,
돌아올 때 부모 노드의 euler와 level 배열을 다시 기록 */
if (root->right) {
eulerTour(root->right, l+1);
euler1[ind]=root->key;
level1[ind] = l;
ind++;
}
}
}
// 노드 n1, n2의 LCA 반환 (두 노드가 트리에 존재한다고 가정)
int findLCA(Node1 *root, int u1, int v1){
/* 모든 노드를 미방문 상태로 초기화.
참고: 노드 값이 1~9 사이이며 인덱스로 사용되므로
firstOccurrence 크기를 V+1로 설정 */
memset(firstOccurrence1, -1, sizeof(int)*(V+1));
/* euler 및 level 배열을 인덱스 0부터 채우기 시작 */
ind = 0;
/* 루트 노드를 레벨 0에서 오일러 투어 시작 */
eulerTour(root, 0);
/* level 배열에 대한 세그먼트 트리 구성 */
int *st1 = constructST(level1, 2*V-1);
/* 오일러 투어에서 v가 u보다 먼저 나오는 경우.
RMQ가 올바르게 동작하려면 첫 번째 매개변수 'u1'이
두 번째 매개변수 'v1'보다 작아야 함 */
if (firstOccurrence1[u1]>firstOccurrence1[v1])
std::swap(u1, v1);
// 쿼리 범위의 시작/끝 인덱스
int qs1 = firstOccurrence1[u1];
int qe1 = firstOccurrence1[v1];
// 투어에서 LCA의 인덱스를 구하는 쿼리 실행
int index1 = RMQ(st1, 2*V-1, qs1, qe1);
/* LCA 노드 반환 */
return euler1[index1];
}
// 위 함수들을 테스트하는 드라이버 프로그램
int main(){
// 다이어그램에 표시된 것과 같은 이진 트리 생성
Node1 * root = newNode1(1);
root->left = newNode1(2);
root->right = newNode1(3);
root->left->left = newNode1(4);
root->left->right = newNode1(5);
root->right->left = newNode1(6);
root->right->right = newNode1(7);
root->left->right->left = newNode1(8);
root->left->right->right = newNode1(9);
int u1 = 4, v1 = 9;
printf("The LCA of node %d and node %d is node %d.\n",
u1, v1, findLCA(root, u1, v1));
return 0;
}출력 결과
The LCA of node 4 and node 9 is node 2.