C++ 누적합

알고리즘 문제를 풀다보면 종종 for 문 대신 '누적합'을 사용해야하는 문제가 나온다

 

누적합이란?

- 요소들이 누적된 합으로, 어떤 배열을 기반으로 요소들의 누적된 합을 저장해 새로 배열을 만들어 이를 활용하는 방법

- 앞에서 더하는 prefix sum (주로 코딩테스트에서는 prefix sum만 나옴!!)

- 뒤에서 더하는 suffix sum

 

 

prefix sum 만들 때 주의해야 할 점

- 0번째 요소는 비워두고 1번째 요소부터 사용하자

psum[1] -> 0, 1

psum[2] -> 0,1,2

psum[3] -> 0, 1,2,3

psum[4] -> 0,1,2,3,4

 

누적합을 코드로 구현해보자!

for(int i = 1; i <= n; i++) {
	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] << '\n';
}

 

 

백준 누적합 연습 문제 2559. 수열

2559번: 수열

누적합 문제를 for 문을 이용해서 풀면?

#include <bits/stdc++.h>

using namespace std;


int main() {
  int n, k, m;
  cin >> n >> k;
  string s;
  vector<int> numbers;
  for (int l = 0; l < n; l++) {
    cin >> m;
    numbers.push_back(m);
  }
  int max = -9999999;
  for (int i = 0; i <= numbers.size() - k; i++) {
    int sum = 0;
    for (int j = i; j < i + k; j++) {
      sum += numbers[j];
    }
    if (sum >= max) {
      max = sum;
    }
  }
  cout << max;
  return 0;
}

N 이 2 ~ 100,000 이하 이므로, 위의 코드로 구현하게되면 빅오가 N^2 가 되는데 

10000000000 로 시간 초과가 발생하게 된다

 

누적합을 이용해서 푼다면?

#include <bits/stdc++.h>

using namespace std;

int main() {
  int n, k, m;
  cin >> n >> k;
  string s;
  int num[100004];
  int psum[100004];
  for (int i = 1; i <= n; i++) {
    cin >> num[i];
    psum[i] = psum[i-1] + num[i];
  }
  int maximum[100004];
  int largest = -1000000;
  for (int i = k; i <= n; i++) {
      largest = max(largest, psum[i]-psum[i-k]);
  }
  cout << largest << '\n';
  return 0;
}

N 보다 큰 배열 maximum을 만들어 놓고,

n 만큼 for 문을 돌며, 미리 저장해논 누적합을 통해 연속된 수의 합을 구한다

빅오 N 으로 축소되어 시간 초과를 해결할 수 있다!

 

 

 

백준 더 많은 누적합 문제

문제 - 1 페이지