[Algorithm] 누적합

1. 누적합이란?

1. 개념

• 요소들의 누적된 합의 의미로 어떠한 배열을 기반으로 앞에서부터 요소들의 누적된 합을 저장해 새로이 배열을 만들어서 이를 활용
• 앞에서부터 누적된 합을 구하는 prefixSum과 뒤에서부터 누적된 합을 구하는 suffixSum이 있다.

2. 방법

• 편안하게 구현하기 위해 index를 0번째 부터가 아니라 1번째부터 담는다.
• 아래의 그림과 같은 방식으로 구현하면 된다.
  

3. 누적합 예시 문제

• 백준 2559. 수열 문제가 대표적인 누적합 문제다.
  2559번:수열
• 이 문제의 입력값 조건을 보면 N이 2이상 100,000 이하의 범위를 가졌고, K는 1과 N의 사이의 정수라는 조건이 있다. 이 문제를 아무 생각 없이 아래의 코드와 같이 접근을 하면, 최대 시간 복잡도가 100,000 * 100,000 라는 큰 수가 될수 있다.

int main(){
    cin >> n >> k;
    for(int i = 0; i < n; i++){
        cin >> input[i];
    }
    for(int i = 0; i < n; i++){
        for(int j = i; j < i + k; j++){
            sum += input[i];
        }
    }
}

• 이러한 상황에서 우리는 누적합을 이용함으로써 런타임 아웃을 해결 할 수 있다.
• 입력 예시를 계산해보면 k만큼 연속된 날짜의 합을 구하는것이기 때문에, 아래의 그림과 같은 상황인 것을 알 수 있다.
  
• 정답 코드

#include <bits/stdc++.h>
using namespace std;
int n , k;
int psum[100004];
int input[100004];
int ret = INT_MIN;
int main(){
    cin >> n >> k;
    for(int i = 1; i < n + 1; i++){
        cin >> input[i];
    }
    for(int i = 1; i < n + 1; i++){
        psum[i] = psum[i - 1] + input[i];
    }
    for(int i = k; i < n + 1; i++){
        ret = max(ret, psum[i] - psum[i - k]);
    }
    cout << ret << '\n';
    return 0;
}

---

참조

누적합