[구간 합] 빠르고 정확한 합계 계산

구간 합(Prefix Sum) 

간 합(Prefix Sum)은 배열이나 수열에서 특정 구간의 합을 빠르게 계산하기 위한 기법입니다. 특히 여러 번 구간 합을 요청받는 문제에서 큰 성능 차이를 만들어내는 핵심 테크닉입니다.

이 글에서는 구간 합의 기본 개념부터 구현 방법, 그리고 주요 언어별 코드 예제를 제공하여 여러분이 실전 문제에 바로 적용할 수 있도록 돕겠습니다.

 

---

1.  구간 합(Prefix Sum)이란?

구간 합은 배열의 특정 구간 [i, j]의 합을 빠르게 구하기 위해 사전에 합을 저장해두는 기법입니다. 일반적인 방법으로 매번 i부터 j까지 합을 구하면 O(N)이 걸리지만, 구간 합 배열을 이용하면 O(1)만에 답을 구할 수 있습니다.

기본 아이디어

• 원본 배열 arr이 있을 때, prefix_sum[i] 는 arr[0] 부터 arr[i] 까지의 합을 의미합니다.
• 특정 구간 [i, j]의 합은 다음과 같이 계산할 수 있습니다.

$$ \text{sum}(i,j)= \text{prefix_sum}[j]− \text{prefix_sum}[i−1]$$

(단, i = 0인 경우에는 그냥 prefix_sum[j] 를 사용합니다.)

 

---

2.  구간 합 배열 만들기

알고리즘 단계

1. prefix_sum[0] = arr[0]
2. 이후 각 i 에 대해 prefix_sum[i] = prefix_sum[i-1] + arr[i]

✅ 사전 계산은 O(N) 시간이 걸리지만, 이후 모든 질의는 O(1) 로 처리할 수 있습니다.

 

---

3.  주요 언어별 예제 코드

a.  Python (파이썬)

def compute_prefix_sum(arr):
    prefix_sum = [0] * len(arr)
    prefix_sum[0] = arr[0]
    for i in range(1, len(arr)):
        prefix_sum[i] = prefix_sum[i-1] + arr[i]
    return prefix_sum

def range_sum(prefix_sum, i, j):
    if i == 0:
        return prefix_sum[j]
    else:
        return prefix_sum[j] - prefix_sum[i-1]

# 사용 예시
arr = [1, 2, 3, 4, 5]
prefix = compute_prefix_sum(arr)
print(range_sum(prefix, 1, 3))  # 2 + 3 + 4 = 9

b.  C++

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

vector<int> compute_prefix_sum(const vector<int>& arr) {
    vector<int> prefix_sum(arr.size());
    prefix_sum[0] = arr[0];
    for (size_t i = 1; i < arr.size(); i++) {
        prefix_sum[i] = prefix_sum[i-1] + arr[i];
    }
    return prefix_sum;
}

int range_sum(const vector<int>& prefix_sum, int i, int j) {
    if (i == 0) return prefix_sum[j];
    return prefix_sum[j] - prefix_sum[i-1];
}

int main() {
    vector<int> arr = {1, 2, 3, 4, 5};
    vector<int> prefix = compute_prefix_sum(arr);
    cout << range_sum(prefix, 1, 3) << endl; // 출력: 9
}

c.  Java (자바)

public class PrefixSumExample {
    public static int[] computePrefixSum(int[] arr) {
        int[] prefixSum = new int[arr.length];
        prefixSum[0] = arr[0];
        for (int i = 1; i < arr.length; i++) {
            prefixSum[i] = prefixSum[i-1] + arr[i];
        }
        return prefixSum;
    }

    public static int rangeSum(int[] prefixSum, int i, int j) {
        if (i == 0) return prefixSum[j];
        return prefixSum[j] - prefixSum[i-1];
    }

    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 4, 5};
        int[] prefix = computePrefixSum(arr);
        System.out.println(rangeSum(prefix, 1, 3)); // 출력: 9
    }
}

d.  JavaScript (자바스크립트)

function computePrefixSum(arr) {
    const prefixSum = Array(arr.length).fill(0);
    prefixSum[0] = arr[0];
    for (let i = 1; i < arr.length; i++) {
        prefixSum[i] = prefixSum[i-1] + arr[i];
    }
    return prefixSum;
}

function rangeSum(prefixSum, i, j) {
    if (i === 0) return prefixSum[j];
    return prefixSum[j] - prefixSum[i-1];
}

// 사용 예시
const arr = [1, 2, 3, 4, 5];
const prefix = computePrefixSum(arr);
console.log(rangeSum(prefix, 1, 3)); // 출력: 9

 

---

4.  구간 합의 장점과 한계

장점	한계
다수의 구간 합 요청을 매우 빠르게 처리 가능	배열 값이 자주 변경되면 다시 구해야 함
시간 복잡도 O(1)로 질의 처리	업데이트가 많으면 세그먼트 트리 등 다른 자료구조가 필요

 

---

5.  마무리

• 구간 합(Prefix Sum)은 다수의 구간 합 요청을 빠르게 처리하는 효율적인 알고리즘입니다.
• 사전 계산(O(N))을 통해 이후 질의를 O(1)로 처리할 수 있습니다.
• 배열 값이 변경되지 않는 경우에 특히 유용합니다.

함께 보면 좋은 자료

외부 사이트 :

• Wikipedia - Prefix sum

 

---