[10주 완성 C++ 코딩테스트] 누적합, Prefix Sum

* 누적합: 어떤 배열의 앞 요소부터 누적된 합을 저장한 배열.

               앞에서부터 더하는 prefix sum과 뒤에서 부터 더하는 suffix sum 이 있다.

               배열의 값이 변하지 않는 정적 변수에만 사용할 수 있다.

 

* 누적합이 필요한 예시문제

문제 승철이는 뇌를 잃어버렸다. 학교에 갔더니 선생님이 자연수로 이루어진 N개의 카드를 주며 M개의 질문을 던진다. 그 질문은 나열한 카드 중 A번째부터 B번째까지의 합을 구하는 것이다. 뇌를 잃어버렸기 때문에 승철이는 이 문제를 풀 수가 없다. 문제를 풀 수 있는 프로그램을 작성해보자. 입력 수의 개수N, 합을 구해야 하는 횟수 M, 그 이후 N개의 수가 주어진다. 수는 100이하의 자연수. 그 이후 M개의 줄에는 합을 구해야 하는 구간 A, B가 주어진다. 출력 M개의 줄에 A부터 B까지의 합을 구하라. 범위 1 <= N <= 100,000 1 <= M <= 100,000 1 <= A <= B <= N 예제입력 8 3 1 2 3 4 5 6 7 8 1 4 1 5 3 5 예제출력 10 15 12

위 문제를 단순 2중 for문으로 풀면 문제의 최대 범위 100,000 * 100,000 번으로 10,000,000,000번(100억번) 의 수가 나와서 시간복잡도의 범위를 넘어선다.

 

따라서 다른 알고리즘을 생각해야 한다는 것을 알 수 있다. 이렇게 배열이 주어지고 그 배열의 연속된 합을 누적해서 갖고 있는 형태가 필요할 때 '누적합' 알고리즘을 사용한다.

 

//그냥 2중 반복문으로 풀었을 때

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

int main() {
	int n, m, a, b;
	cin >> n >> m;

	vector<int> v(n+1);
	for (int i = 1; i <= n; i++){
		cin >> v[i];
	}

	for (int i = 0; i < m; i++) {
		int sum = 0;
		cin >> a >> b;
		for (int j = a; j <= b; j++) {
			sum += v[j];
		}
		cout << sum << '\n';
	}
	return 0;
}

 

//누적합 알고리즘을 이용한 경우

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

int main() {
	int n, m, a, b;
	cin >> n >> m;

	vector<int> v(n+1);
	for (int i = 1; i <= n; i++){
		cin >> v[i];
		v[i] += v[i - 1];
	}

	for (int i = 0; i < m; i++) {
		cin >> a >> b;
		cout << v[b] - v[a - 1] << '\n';
	}
	return 0;
}

 

 

누적합을 이용하면 시간복잡도가 O(n)으로 줄어든다.