🧮 알고리즘 : 누적합 (Prefix sum)

! TIME LIMIT EXCEEDED !

알고리즘 문제를 풀다보면 단순히 반복 수행하면 시간 초과에 걸리게 되는 유형의 문제가 많이 나타납니다. 요구하는 결과를 찾는 로직을 열심히 구현한 뒤에 "오 드디어 구해진다!" 하고 제출했는데, **시간 초과**라고 뜨면 굉장히 머리가 아파지죠.

오늘은 부분합, 구간합 문제에 주로 사용되는 **누적합(Prefix sum)**에 대해 알아보도록 하겠습니다.

❔ 부분합, 구간합 ${(Partial\ Sum)}$

먼저 간단하게 부분합과 구간합에 대해 알아봅시다.

• 부분합 0 ~ n: 수열(배열)의 $0$번째부터 $n-1$번째까지의 합입니다.

  • 수학식 : $S_n = a_1 + a_2 + a_3 + \dotsc + a_n$
  • 프로그래밍식 : S(n) = a[0] + a[1] + a[2] + ... + a[n-1]

• 구간합 a ~ b : 수열(배열)의 $a$번째부터 $b$번째까지의 합입니다.

  • 수학식 : $S_{(a,b)} = a_a + a_{a+1} + \dotsc + \dot + a_{b-2} + a_{b-1} + a_b$
  • 프로그래밍식 : S(a, b) = a[a] + a[a+1] + ... + a[b-1] + a[b]

❔ 누적합 $(Prefix\ Sum)$

자연수가 나열된 1차원 수열 $(array)$이 있을 때
이 수열에 대한 누적합 $(prefix\ sum)$

누적합은 나열된 수(수열)의 누적된 합 자체 혹은 그것을 담은 수열을 의미합니다. 또한, 누적합의 각 요소는 수열의 $n$번째까지 요소의 합이기 때문에 수열의 부분합이라고 할 수 있습니다.

자 그럼 누적합은 어떤 경우에 사용하기 위해서 만들어진 걸까요? 누적합 방식은 아래 유형의 문제 해결에 주로 사용됩니다.

• 구간합 / 부분합 ${(Partial\ Sum)}$
• 카운팅 정렬 $(Counting Sort)$

이제 1차원 수열과 2차원 수열로 나누어 예시를 보며 어떻게 만들고 사용하는지 배워봅시다.

🧪 1차원 배열에서의 누적합

1차원 배열의 누적합을 만드는 방법은 아주 간단합니다.

1. 같은 크기의 배열을 만듭니다.
2. 해당 인덱스까지의 총합을 담습니다.

자바스크립트에선 아래와 같이 작성할 수 있습니다.

function prefixSums(arr) {
  const len = arr.length;
  const prefixSums = [];
  let sum = 0;
 
  for (let i = 0; i < len; ++i) {
    sum += arr[i];
    prefixSums[i] = sum;
  }
 
  return prefixSums;
}

만약 sum변수를 만들지 않고 싶다면 아래와 같이 작성할 수 있습니다.

function prefixSums(arr) {
  const len = arr.length;
  const prefixSums = [arr[0]];
 
  for (let i = 1; i < len; ++i) {
    prefixSums[i] = prefixSums[i - 1] + arr[i];
  }
 
  return prefixSums;
}

🥇 문제 풀이에 사용해보기

백준의 대표적인 구간합 문제인 백준 11659 : 구간 합 구하기 4입니다.

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

5 3
5 4 3 2 1
1 3
2 4
5 5

12
9
1

🚀 누적합의 목적

자 그럼 누적합은 어떤 경우에 사용하기 위해서 만들어진 걸까요? 알고리즘 문제를 예시로 들면 아래 유형의 문제에 주로 사용됩니다.

• 구간합 / 부분합 ${(Partial\ Sum)}$
• 카운팅 정렬 $(Counting Sort)$

백준의 대표적인 구간합 문제인 백준 11659 : 구간 합 구하기 4를 예시로 풀어보도록 하겠습니다.

참고 문헌

• wikipedia.org/wiki/Prefix_sum