[알고리즘] 구간 합 (Prefix Sum)

1. 구간 합 VS 부분 합

- Prefix sum(구간 합) : 구간 합이란 수들의 나열에서 특정 구간의 합을 의미한다. 구간 합 알고리즘은 보통 1차원배열에서 i~k 인덱스 사이의 값들의 합을 구하는데 사용한다.

 

- Partial sum(부분 합) : 부분 합이란 구간 합과 달리 처음부터 특정인덱스까지의 합을 의미한다. 즉 0~k 인덱스 사이의 값들의 합을 의미한다.

 

2. 구간 합 알고리즘

•  반복문을 사용하여 i~k사이의 값을 더하는 알고리즘의 시간복잡도는 O(n)이다.
•  이 같은 알고리즘을 사용할 경우 n의 값이 클 경우 이를 정해진 시간 내에 해결할 수 없다.
•  하지만 구간 합 알고리즘을 사용하여 구간합을 구하는 경우 O(1)의 성능을 갖는다.
•  구간 합 알고리즘은 현재 진행단계까지의 인덱스까지 값의 합을 저장하는 sum[]배열을 사용한다.
•  j번째 바로 앞까지의 총합에 arr[j] 값을 더하면 j번째까지의 총합을 의미하므로 sum[j] = sum[j-1] + arr[j] 로 표현할 수 있다.

 

3. 구현

 

다음은 백준 11659번 문제 구간합 구하기4 의 풀이이다.

 

-구간합 구하기 4

11659번: 구간 합 구하기 4

- 문제 : 첫째 줄에 수의 개수 N (1 ≤ N ≤ 100,000), 합을 구해야 하는 횟수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

- 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

 

 

* 풀이

다음과 같은 문제에서 처음 입력받은 N개의 숫자에 대하여 미리 구간합 (sum[i+1] = sum[i] + num)을 구함으로 인해

M번의 연산에서 이전에 sum[i] 에 저장되어 있는 0~i번째 수까지의 구간 합을 사용함으로써 문제를 정해진 시간 내에 풀 수 있다.

 

다음과 같은 문제를 미리 구간합을 구하지 않고 합을 구할 때 마다 반복문 내에서 index까지의 합을 구하여 중첩 반복문을 사용하여 풀 경우 M(연산횟수) 에 따라 전체 시간이 증가하게 되어 시간 복잡도가 O(M*N*N)으로 주어진 시간을 초과하게 된다.

 

#include <iostream>
#define MAX 100000

int sum[MAX];

int main(void)

	int N, M;
	cin >> N >> M;
	for (int i = 0; i < N; i++)
		{
			int num;
			cin >> num;
			sum[i+1] = sum[i] + num;
		}

	for (int i = 0; i < M; i++)
	{
		int x, y;
		cin >> x >> y;
		cout << sum[y] - sum[x-1] << endl;
	}
	return 0;
}