앞서 우리는 배열의 특정 구간에 대한 쿼리(합, 최댓값, 최솟값)를 빠르게 처리하기 위해 '세그먼트 트리(Segment Tree)'라는 훌륭한 자료구조를 배웠습니다. 세그먼트 트리는 데이터가 수시로 변경(Update)되는 상황에서도 O(log N)의 속도를 보장하는 전천후 무기입니다. 하지만 실무 시스템이나 코딩 테스트 문제 중에는 "배열의 데이터는 처음 주어진 상태에서 단 한 번도 변하지 않는데(Static), 특정 구간의 최솟값을 묻는 쿼리만 수백만 번 쏟아지는 상황"이 존재합니다. 이때 세그먼트 트리보다 구현이 훨씬 간결하면서도, 쿼리 처리 속도를 O(log N)에서 경이로운 O(1) 상수 시간으로 단축시켜 버리는 궁극의 최적화 기법이 있습니다. 바로 동적 계획법(DP)의 원리를 배열 구간 쿼리에 접목시킨 '희소 배열(Sparse Table, 스파스 테이블)'입니다. 오늘 이 글에서는 구간 최솟값 쿼리(RMQ, Range Minimum Query)의 제왕, 희소 배열의 마법 같은 원리를 완벽하게 해부해 보겠습니다.
1. 희소 배열(Sparse Table)이란 무엇인가?
[Image of Sparse Table data structure construction showing array intervals of power of 2 sizes]
희소 배열은 주로 데이터의 변경이 없는 정적인 배열에서 구간의 최솟값(Min), 최댓값(Max), 최대공약수(GCD) 등을 가장 빠르게 구하기 위해 사용하는 2차원 배열 기반의 자료구조입니다.
1-1. 전제 조건: 불변하는 데이터와 멱등성(Idempotence)
희소 배열을 사용하려면 두 가지 중요한 조건이 충족되어야 합니다.
- 정적 데이터(Static Data): 쿼리를 처리하는 도중에 원본 배열의 값이 수정(Update)되어서는 안 됩니다. 값이 변하면 테이블 전체를 다시 만들어야 하므로 O(N log N)의 비용이 발생해 세그먼트 트리보다 비효율적이 됩니다.
- 멱등성(Idempotence) 연산: 희소 배열이 O(1)의 마법을 부리기 위해서는 연산이 멱등성을 띄어야 합니다. 멱등성이란 '같은 구간을 여러 번 중복해서 연산해도 결과가 변하지 않는 성질'을 말합니다. 예를 들어
MIN(3, 3) = 3이므로 구간이 겹쳐도 최솟값은 변하지 않지만,SUM(3, 3) = 6이 되어 합계(Sum) 연산은 중복 시 결과가 훼손됩니다. 따라서 희소 배열은 구간 합을 구할 때는 O(1)이 아닌 O(log N)이 걸리며, 주로 구간 최솟값/최댓값을 구할 때 진정한 위력을 발휘합니다.
2. 희소 배열의 구축: $2^K$ 길이의 마법 (전처리 과정)
희소 배열의 핵심 아이디어는 "임의의 모든 구간 길이는 2의 거듭제곱(1, 2, 4, 8, 16...) 길이의 구간들로 쪼개어 조합할 수 있다"는 수학적 사실에서 출발합니다.
2-1. 2차원 DP 테이블의 설계
우리는 table[i][j]라는 2차원 배열을 만듭니다. 이 배열이 품고 있는 의미는 "배열의 i번째 인덱스부터 시작하여, 길이가 $2^j$인 구간 내에서의 최솟값"입니다.
table[i][0]: i부터 길이가 $2^0$ (즉, 1)인 구간의 최솟값. 자기 자신입니다.table[i][1]: i부터 길이가 $2^1$ (즉, 2)인 구간의 최솟값.table[i][2]: i부터 길이가 $2^2$ (즉, 4)인 구간의 최솟값.
2-2. 점화식 도출 (O(N log N))
길이가 8인 구간의 최솟값은 어떻게 구할까요? 굳이 8개를 다 비교할 필요가 없습니다. "앞에서부터 4개의 최솟값"과 "그다음 이어지는 4개의 최솟값" 두 개만 비교하면 끝납니다. 이를 바탕으로 아주 아름다운 DP 점화식이 탄생합니다.
// 길이가 2^j 인 구간의 최솟값은, 길이가 2^(j-1) 인 두 구간의 최솟값 중 더 작은 값
table[i][j] = Math.min(table[i][j - 1], table[i + (1 << (j - 1))][j - 1]);
이 점화식을 사용하여 루프를 돌리면 데이터 $N$개에 대해 최대 $\log N$번의 열(Column)만 채우면 되므로, 전처리 과정(Preprocessing)의 시간 복잡도는 O(N log N)이 됩니다.
3. 쿼리 처리의 마법: 완벽한 O(1) 속도
[Image of RMQ Range Minimum Query using Sparse Table overlapping two power of 2 intervals]
이제 누군가가 "인덱스 L부터 R까지 구간의 최솟값을 구하라"는 쿼리를 던졌습니다. 구간의 길이는 len = R - L + 1입니다. 우리는 세그먼트 트리처럼 분할 정복을 하며 트리를 타고 내려갈 필요가 없습니다.
3-1. 두 개의 거대한 덩어리로 덮어버리기
구간 길이 len보다 작거나 같은 가장 큰 2의 거듭제곱 수($2^k$)를 찾습니다. 예를 들어 길이가 13이라면, 13보다 작거나 같은 가장 큰 2의 거듭제곱은 8($2^3$)입니다. 따라서 k = 3이 됩니다.
이제 우리는 미리 계산해 둔 희소 배열에서 딱 두 개의 값만 가져와서 비교하면 됩니다.
- 시작점 L부터 길이가 8인 구간의 최솟값:
table[L][3] - 끝점 R에서 끝나는 길이가 8인 구간의 최솟값:
table[R - 8 + 1][3]
이 두 구간은 가운데 부분이 필연적으로 겹치게(Overlap) 됩니다. 하지만 앞서 말씀드렸듯이 최솟값(Min) 연산은 아무리 겹쳐서 중복 비교를 하더라도 결괏값에 전혀 영향을 주지 않습니다(멱등성). 따라서 단 한 번의 비교 연산(O(1))만으로 100만 개든 1,000만 개든 상관없이 특정 구간의 최솟값을 즉시 도출해 낼 수 있습니다. 이 기법은 이전 시간에 다루었던 트리 탐색의 최소 공통 조상(LCA) 알고리즘을 최적화할 때도 내부적으로 동일하게 쓰이는 초고급 테크닉입니다.
1. 희소 배열(Sparse Table)은 값이 변하지 않는 정적 배열에서 구간 쿼리를 초고속으로 처리하기 위한 2차원 DP 기반 자료구조입니다.
2. 데이터의 길이를 2의 거듭제곱 크기로 쪼개어 미리 저장하는 전처리 과정을 거치며, 이때 O(N log N)의 시간과 공간이 소요됩니다.
3. 구간이 겹쳐도 상관없는 최솟값(Min)이나 최대공약수(GCD) 쿼리에 적용 시, 세그먼트 트리보다 빠른 O(1)의 상수 시간만에 정답을 반환합니다.