같은 질문이 반복되면 답을 미리 만들어 둘 수 있습니다. 전처리는 미리 계산하는 비용을 내고 질의마다 드는 비용을 줄이는 거래입니다.
한 번과 십만 번은 다른 문제입니다
배열에서 인덱스 3부터 7까지의 합을 구합니다. 반복문 한 번이면 됩니다. 원소 다섯 개를 더하는 O(N) 작업입니다.
이 질문이 십만 번 들어오면 상황이 바뀝니다. 배열 크기가 십만이고 질의도 십만 개라면 곱해서 백억입니다. ep.01 크기가 접근법을 정한다의 기준선으로 보면 통과할 수 없는 규모입니다.
질의 하나하나는 최적이었는데 전체가 실패합니다. 문제의 단위가 질의 하나가 아니라 질의 묶음이었기 때문입니다. 같은 배열의 범위를 반복해서 묻는 이런 문제를 구간 질의(range query) 라고 합니다.
누적합은 뺄셈으로 답합니다
누적합(prefix sum) 은 배열을 한 번 훑으면서 처음부터 각 위치까지의 합을 미리 저장합니다. 배열이 3, 1, 4, 1, 5, 9, 2라면 누적합은 앞에 0을 하나 두고 차례로 더한 0, 3, 4, 8, 9, 14, 23, 25입니다.
| 인덱스 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|---|
| arr | 3 | 1 | 4 | 1 | 5 | 9 | 2 | - |
| prefix | 0 | 3 | 4 | 8 | 9 | 14 | 23 | 25 |
구간 [2, 4]의 합을 구한다고 해봅시다. 반복문은 4 + 1 + 5를 직접 더해 10을 얻고, 덧셈 횟수가 구간 길이만큼 듭니다. 누적합은 인덱스 5까지의 합 14에서 인덱스 2 앞까지의 합 4를 빼서 같은 10을 얻고, 구간이 아무리 길어도 뺄셈 한 번입니다.
// prefix[i] = arr[0] + arr[1] + ... + arr[i-1]
function buildPrefix(arr) {
const prefix = new Array(arr.length + 1).fill(0);
for (let i = 0; i < arr.length; i++) {
prefix[i + 1] = prefix[i] + arr[i];
}
return prefix;
}
// 구간 [l, r]의 합을 뺄셈 한 번으로
function rangeSum(prefix, l, r) {
return prefix[r + 1] - prefix[l];
}인덱스를 한 칸 밀어 prefix[0]을 0으로 두면 편합니다. 구간이 0부터 시작하는 경우를 따로 처리하지 않아도 됩니다.
전처리에 O(N)을 쓰고, 이후 질의는 뺄셈 한 번이므로 O(1)입니다. 질의가 Q개면 전체가 O(N + Q)로 떨어집니다. 백억이 이십만이 됩니다.
| 반복문 | 누적합 | |
|---|---|---|
| 전처리 | 없음 | O(N), 한 번 훑기 |
| 질의 한 번 | O(N), 구간 길이만큼 덧셈 | O(1), 뺄셈 한 번 |
| 질의 십만 번 (N이 십만) | 최대 백억 번 | 십만 + 십만 = 이십만 번 |
2차원에서도 같은 원리입니다
격자에서 직사각형 영역의 합을 구할 때도 같은 방식이 통합니다. 다만 뺄셈이 한 번으로 끝나지 않습니다.
왼쪽 위 모서리부터 각 지점까지의 합을 저장해두면, 원하는 직사각형은 큰 사각형에서 위쪽과 왼쪽을 빼고 두 번 빠진 부분을 다시 더해 얻습니다.
// sum[i][j] = (0,0)부터 (i-1,j-1)까지의 합
const area =
sum[r2 + 1][c2 + 1] -
sum[r1][c2 + 1] - // 위쪽 제거
sum[r2 + 1][c1] + // 왼쪽 제거
sum[r1][c1]; // 두 번 빠진 겹침 복구포함 배제(inclusion-exclusion) 라고 부르는 계산입니다. 차원이 늘어도 원리는 같습니다.
갱신이 끼어들면 무너집니다
누적합의 전제는 원본 배열이 바뀌지 않는다는 것입니다.
중간의 값 하나가 바뀌면 그 뒤의 누적합이 전부 어긋납니다. 다시 만들려면 O(N)입니다. 갱신이 자주 일어나면 전처리 비용을 매번 다시 내는 셈이라 이득이 사라집니다.
질의와 갱신이 섞여 들어오는 상황이 실제로는 더 흔합니다. 값을 고치면서 통계를 계속 조회하는 화면이 그렇습니다.
세그먼트 트리는 구간을 나눠 갖습니다
세그먼트 트리(segment tree) 는 배열을 절반씩 쪼개면서 각 노드가 담당 구간의 합을 들고 있는 이진 트리입니다.
루트는 전체 구간을, 그 자식들은 왼쪽 절반과 오른쪽 절반을, 잎은 원소 하나를 맡습니다.
질의가 들어오면 루트에서 내려가면서 노드마다 세 가지 중 하나를 판정합니다.
- 완전히 포함: 노드의 담당 구간이 질문 구간 안에 다 들어가면 그 노드의 합을 그대로 쓰고 더 내려가지 않습니다
- 전혀 안 겹침: 담당 구간이 질문 구간 밖이면 무시합니다
- 걸침: 일부만 겹치면 양쪽 자식으로 나눠 내려가서 같은 판정을 반복합니다
배열 1, 2, 3, 4, 5에서 구간 [1, 3]의 합을 묻는 경우를 따라가면 이렇습니다. 루트 [0, 4]는 걸치므로 자식 [0, 2]와 [3, 4]로 내려갑니다. [0, 2]도 걸쳐서 [0, 1]과 [2, 2]로 나뉘고, [2, 2]는 완전히 포함되어 값 3을 그대로 씁니다. [0, 1]은 또 걸쳐서 [0, 0]과 [1, 1]로 나뉘는데, [0, 0]은 겹치지 않아 무시하고 [1, 1]은 포함되어 값 2를 씁니다. 오른쪽 [3, 4]는 [3, 3]과 [4, 4]로 나뉘어 [3, 3]의 4를 쓰고 [4, 4]는 무시합니다. 값을 실제로 가져온 노드는 [1, 1], [2, 2], [3, 3] 셋이고 합은 2 + 3 + 4 = 9입니다.
이 가지치기 덕분에 방문하는 노드가 O(log N)개로 제한됩니다.
갱신은 반대 방향입니다. 값이 바뀐 잎에서 루트까지 올라가면서 조상 노드들의 합을 다시 계산합니다. 경로 길이가 트리 높이이므로 역시 O(log N)입니다.
class SegmentTree {
#n;
#tree;
constructor(arr) {
this.#n = arr.length;
this.#tree = new Array(this.#n * 2).fill(0);
// 뒤쪽 절반에 원본을 두고 앞으로 접어 올린다
for (let i = 0; i < this.#n; i++) this.#tree[this.#n + i] = arr[i];
for (let i = this.#n - 1; i > 0; i--) {
this.#tree[i] = this.#tree[i * 2] + this.#tree[i * 2 + 1];
}
}
update(index, value) {
let i = index + this.#n;
this.#tree[i] = value;
while (i > 1) {
i >>= 1;
this.#tree[i] = this.#tree[i * 2] + this.#tree[i * 2 + 1];
}
}
// 구간 [l, r] 합
query(l, r) {
let result = 0;
let lo = l + this.#n;
let hi = r + this.#n + 1;
while (lo < hi) {
if (lo & 1) result += this.#tree[lo++];
if (hi & 1) result += this.#tree[--hi];
lo >>= 1;
hi >>= 1;
}
return result;
}
}합 대신 최솟값이나 최댓값을 넣어도 그대로 작동합니다. 두 자식의 결과를 하나로 합치는 연산이 결합법칙을 만족하면 됩니다.
무엇을 고를 것인가
| 상황 | 선택 | 전처리 | 질의 | 갱신 |
|---|---|---|---|---|
| 질의 한두 번 | 그냥 반복문 | 없음 | O(N) | 즉시 |
| 질의 많고 갱신 없음 | 누적합 | O(N) | O(1) | O(N) |
| 질의와 갱신이 섞임 | 세그먼트 트리 | O(N) | O(log N) | O(log N) |
세그먼트 트리가 항상 유리한 건 아닙니다. 갱신이 없다면 누적합의 O(1) 질의가 더 빠르고 구현도 짧습니다. 구조가 복잡할수록 좋다는 판단은 여기서 통하지 않습니다.
자료구조 시리즈를 마치며
여기까지가 데이터를 담고 정리하는 쪽입니다. 배열과 해시가 위치를 어떻게 찾는지, 정렬이 무엇을 보장하는지, 트리의 모양이 성능을 어떻게 결정하는지, 그리고 반복되는 질문에 전처리로 답하는 방법을 봤습니다.
담는 방식이 정해지면, 그 안에서 무엇을 어떻게 찾을지를 다음에 다룹니다.
참고 자료
- Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.). MIT Press.
- Halim, S., & Halim, F. (2013). Competitive Programming 3. Lulu.
다음 편 예고
2부 「이름과 비용: 알고리즘」이 시작됩니다. 모든 경우를 확인하는 방법이 기준선이고, 나머지 모든 알고리즘은 그 기준선을 어떤 근거로 줄였는지에 대한 답입니다.