누적합 ) 배열의 누적합을 처리하여 구간합을 알아내기

작성일 In Views: Disqus:

▪︎ 누적합 알고리즘

image.png

누적합 알고리즘은 이전 누적합에 대해 현재 인덱스의 값을 더하여 구하는 방법입니다. 기본적인 방식으로 합을 구하게 되면

1 / 1+2 / 1+2+3 / 1+2+3+4 / 1+2+3+4+5 의 방식대로 값을 구하게 되는데 이에 비해 훨씬 효율적이며 구간합을 구할 때 이중 순회를 거치지 않고 누적합을 저장한 데이터를 토대로 최종 인덱스와 시작 인덱스의 설정만으로 답을 찾아낼 수 있습니다. 적용 예시를 보면 쉽게 이해하실 수 있습니다.

▪︎ Example of Apply

image.png

image.png

위 문제는 배열의 13번째 누적합, 24번째 누적합, 5~5번째 누적합을 구하면되는 간단한 문제입니다. 그러나 저 세 케이스를 순회하면서 다시 for문을 통해 원소들을 합하게되면 O(N^2)의 시간복잡도로 최악의 경우 10^10의 시행횟수를 갖게되어 1초 (10^8) 시간제한을 통과할 수 없습니다. 이 때 누적합 알고리즘을 적용하여 주어진 배열의 누적합을 따로 데이터로 저장해놓고 단순 접근과 연산만으로 답을 찾아낼 수 있습니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const fs = require("fs");
const input = fs
  .readFileSync("dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .map((el) => el.split(" ").map((v) => +v));

const [N, M] = input[0];
const numbers = input[1];
const arr = input.slice(2);
const prefixSum = Array(N + 1).fill(0); // 문제에서 인덱스가 기준이 아닌 몇번 째인지로 판단하기 때문에 1부터 데이터를 저장
let answer = [];

// 누적합 데이터를 생성
for (let i = 0; i < N; i++) {
  prefixSum[i + 1] = prefixSum[i] + numbers[i];
}
// 누적합 데이터를 단순 연산하는 것 만으로 구간합 도출
for (let i = 0; i < arr.length; i++) {
  answer.push(prefixSum[arr[i][1]] - prefixSum[arr[i][0] - 1]);
}

console.log(answer.join("\n"));