Note
구간 합을 빠르게 구하는 알고리즘인 Prefix Sum(누적 합)에 대해 알아봅니다.
구간 합이란?
구간 합은 배열에서 i번째 원소부터 j번째 원소까지의 합을 의미합니다.
예를 들어 배열 [5, 4, 3, 2, 1]에서:
- 1번째부터 3번째까지의 구간 합:
5 + 4 + 3 = 12 - 2번째부터 4번째까지의 구간 합:
4 + 3 + 2 = 9
문제 상황
만약 구간 합을 여러 번 구해야 한다면 어떻게 해야 할까요?
단순한 방법: 매번 구간 합을 구할 때마다 해당 구간의 모든 원소를 더하기
- 시간 복잡도: O(N) (각 쿼리마다)
- M번의 쿼리가 있다면: O(N × M)
이 방법은 쿼리 횟수가 많아질수록 비효율적입니다.
Prefix Sum 알고리즘
Prefix Sum(누적 합) 알고리즘은 미리 계산된 누적 합 배열을 활용하여 구간 합을 O(1) 시간에 구할 수 있게 해주는 기법입니다.
핵심 아이디어
배열 arr[1...N]이 주어졌을 때, 누적 합 배열 Sum[i]를 다음과 같이 정의합니다:
Sum[i] = arr[1] + arr[2] + ... + arr[i]
즉, Sum[i]는 1번째부터 i번째까지의 합입니다.
이렇게 하면 i번째부터 j번째까지의 구간 합은 다음과 같이 구할 수 있습니다:
구간 합 = Sum[j] - Sum[i-1]
왜 이렇게 되는가?
예를 들어 배열이 [5, 4, 3, 2, 1]이고, 2번째부터 4번째까지의 합을 구하고 싶다면:
Sum[4] = 5 + 4 + 3 + 2 = 14(1번째부터 4번째까지의 합)Sum[1] = 5(1번째부터 1번째까지의 합)Sum[4] - Sum[1] = 14 - 5 = 9(2번째부터 4번째까지의 합)
이렇게 Sum[j] - Sum[i-1]로 구간 합을 빠르게 계산할 수 있습니다.
시각적 설명
원본 배열: [5, 4, 3, 2, 1]
인덱스: 1 2 3 4 5
누적 합 배열: [5, 9, 12, 14, 15]
인덱스: 1 2 3 4 5
2번째부터 4번째까지의 합을 구하려면:
Sum[4] - Sum[1] = 14 - 5 = 9
기본 구현
#include <iostream>
using namespace std;
int main()
{
int N;
cin >> N;
int arr[100001];
int Sum[100001] = {};
// 누적 합 배열 생성
for (int i = 1; i <= N; i++)
{
cin >> arr[i];
Sum[i] = Sum[i - 1] + arr[i];
}
// 구간 합 계산 예시
int start, end;
cin >> start >> end;
// 구간 합 = Sum[end] - Sum[start-1]
cout << Sum[end] - Sum[start-1] << "\n";
return 0;
}구현 포인트
- 누적 합 배열 생성: 입력을 받으면서 동시에
Sum[i] = Sum[i-1] + arr[i]로 누적 합을 계산합니다. - 구간 합 계산: 각 쿼리마다
Sum[end] - Sum[start-1]을 계산하여 구간 합을 구합니다. - 인덱스 주의:
Sum[0] = 0으로 초기화하여start = 1일 때도 올바르게 동작하도록 합니다.
시간 복잡도 분석
- 누적 합 배열 생성: O(N) - 한 번만 수행
- 각 쿼리 처리: O(1) - 단순 뺄셈 연산
- 전체 시간 복잡도: O(N + M) (M은 쿼리 개수)
기존의 단순한 방법(O(N × M))과 비교하면, 쿼리 횟수가 많을수록 성능 차이가 극명하게 나타납니다.
활용 예시
구간 합 알고리즘은 다음과 같은 상황에서 유용합니다:
- 구간 합을 여러 번 구해야 하는 경우
- 구간 평균 계산 (구간 합을 구간 길이로 나누기)
- 2차원 배열의 부분 합 계산 (2D Prefix Sum)
- 슬라이딩 윈도우와 함께 사용
- 배열의 특정 구간에 대한 통계 계산
이 알고리즘은 간단하면서도 강력한 최적화 기법으로, 많은 알고리즘 문제에서 활용됩니다.
관련 문제
- BOJ 11659: 구간 합 구하기 4 - 기본 구간 합 문제