[C++/Algorithm] 누적합

누적합? (prefix sum)

누적합이란 요소들의 누적된 합의 의미로 어떠한 배열을 기반으로 앞에서부터 요소들의 누적된 합을 저장해 새로이 배열을 만들어서 이를 활용하는 것을 말합니다.

 

이는 앞에서부터 더하는 prefix sum과 뒤에서부터 더하는 suffix sum이 있지만 코딩테스트에는 prefix sum만 나오니 prefix sum만을 배우면 됩니다.

 

 

예시문제

승철이는 뇌를 잃어버렸다. 학교에 갔더니 선생님이 자연수로 이루어진 N개의 카드를 주며 M개의 질문을 던진다. 그 질문은 나열한 카드 중 A번째부터 B번째까지의 합을 구하는 것이다. 뇌를 잃어버렸기 때문에 승철이는 이 문제를 풀 수 없다. 문제를 풀 수 있는 프로그램을 작성해 보자.


입력
수의 개수 N, 합을 구해야 하는 횟수 M, 그 이후 N개의 수가 주어진다. 수는 100 이하의 자연수,  그 이후 M개의 줄에는 합을 구해야 하는 구간 A, B가 주어진다.

출력
M개의 줄에 A부터 B까지의 합을 구하라

범위
1 <= N <= 100,000
1 <= M <= 100,000

 

단순히 문제를 보고 일일이 더해서 구하는 알고리즘을 생각해서 코드를 짜보았다.

#include <bits/stdc++.h>
using namespace std;

int a[100004], b, c, psum[100004], n , m;

int main () {
    cin >> n >> m;

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

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

    return 0;
    
}

 

이렇게 되면 n, m의 범위가 10 만씩 이므로 시간복잡도 100억이 돼서 안된다.

 

이럴 때 쓰는 게 누적합이라는 것이다. 

 

#include <bits/stdc++.h>
using namespace std;

int a[100004], b, c, psum[100004], n , m;

int main () {
    cin >> n >> m;

    for (int i = 1; i <= n; i++) { // 요소 i를 1부터 시작하게 하는게 키포인트
        cin >> a[i];
        psum[i] = psum[i-1] + a[i];   
    }

    for (int i = 0; i < m; i++) {
        cin >> b >> c;
        cout << psum[c] - psum[b-1];
    }
    
    return 0; 
}

 

이 배열이 정적배열이라서 가능한 것이고 시간복잡도는 10만 * 1이 되어서 훨씬 간결하고 빠르게 작동이 된다.