구간 합(Prefix Sum) 알고리즘

구간 합(Prefix Sum)이란?

만약 N개의 정수형 배열이 있다고 가정했을 때,

 

부분 합은 0 ~ (N - 1)까지의 합을 의미하는 것이고,

구간 합은 a ~ b (0 <= a < b < N)까지의 합을 의미하는 것이다.

 

구간 합(Prefix Sum)은 어디에 쓰일까?

아래와 같은 문제가 주어진다 생각해보자.

 

int arr[10] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} 배열이 있다.

이때 a에서 b의 구간 합을 요구하는 쿼리 최대 2천만 개가 들어온다.

이러한 문제에 대해 어떻게 해결할 것인가?

가장 쉬운 방법의 코드는 다음과 같다.

#include <vector>
using namespace std;

#define A 0
#define B 1
vector<int> process(vector<vector<int>>& v)
{
	int arr[10] = { 0, 1, 2, 3, 4, 5, 6, 8, 9 };
	vector<int> result;
	for (int i = 0; i < (int)v.size(); ++i)
	{
		int a = v[i][A], b = v[i][B];
		int sum = 0;
		for (int j = a; j <= b; ++j)
		{
			sum += arr[j];
		}
		result.push_back(sum);
	}

	return result;
}

이 방법은 직관적이면서 구현하기 쉽고 항상 정확하다. 하지만 효율성 면에서는 어떨까?

 

이 방법은 효율적이지 못하다. 최대 쿼리인 2천만 개를 처리 하는데 오랜 시간이 걸릴 것이다.

 

이 알고리즘은 이중 반복문을 사용하고 범위는 0 ~ 10까지 이므로 시간 복잡도는 O(N*10)이다. 그렇기 때문에 최대 쿼리인 2천만개를 처리하는 데에 걸리는 시간은 최악의 경우 (20,000,000 * 10) => 200,000,000 번의 연산이 필요하다. 2억번의 연산은 보통 1초를 넘기는 시간이 걸린다. 

 

만약 arr 범위의 제한이 없다면 O(N^2)이 걸리게 될것이다. 이 경우에는 데이터가 많아질수록 기하급수적으로 연산이 많아진다. 효율성 면에서 좋지 않으므로 다른 알고리즘 방법이 필요하다.

 

이때 사용할 알고리즘이 바로 구간 합(Prefix Sum) 알고리즘이다.

 

구간 합(Prefix Sum) 알고리즘

이 알고리즘은 위 코드에서 약간의 수정을 통해 완성시킬 수 있다.

#include <vector>
using namespace std;

#define A 0
#define B 1
vector<int> process(vector<vector<int>>& v)
{
	int arr[10] = { 0, 1, 2, 3, 4, 5, 6, 8, 9 };
	int sumArr[10] = { 0, };

	for (int i = 0; i < 10; ++i)
	{
		if (i == 0) sumArr[i] = arr[i];
		else sumArr[i] = sumArr[i - 1] + arr[i];
	}

	vector<int> result;
	for (int i = 0; i < (int)v.size(); ++i)
	{
		int a = v[i][A], b = v[i][B];
		int sum = sumArr[b] - sumArr[a - 1];
		result.push_back(sum);
	}

	return result;
}

 미리 각 위치까지의 숫자의 합을 담는 배열을 만든 후 b인덱스에서 (a - 1) 인덱스를 빼주면 그 구간의 합을 구할 수 있다. 

 

이 알고리즘을 통해 이중 반복문이었던 알고리즘을 단일 반복문으로 바꾸었다. 시간 복잡도는 O(N)으로 쿼리 2천만 개가 들어오더라도 20,000,000의 연산으로 알고리즘을 처리하므로 소요시간은 1초를 넘기지 않는다.

 

 

구간 합(Prefix Sum)알고리즘이 쓰이는 문제는 Codility에 몇 가지 존재한다. 그중 문제를 해설해놓은 몇 가지를 링크를 통해 올려본다.

MinAvgTwoSlice (Codility)

 

GenomicRangeQuery (Codility)

 

---

내용 일부분은 https://www.crocus.co.kr/843를 참고하여 작성하였습니다.