누적합 알고리즘 (Prefix sum)

개요

알고리즘 문제를 해결하다 보면 종종 "시간 초과"라는 난관을 마주치게 됩니다. 결과는 잘 도출하지만 실행 속도에 문제가 있다고 하면 굉장히 머리가 아파지죠. 이러한 상황은 주로 단순 반복문으로 해결하려 할 때 자주 발생합니다.

오늘은 알고리즘 중 "구간의 합을 구하는 문제"의 효율성 테스트를 통과하기 위해 필요한 누적합($Prefix\ sum$) 알고리즘에 대해 정리해보도록 하겠습니다.

적용 대상

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

부분합과 구간합: 기초 개념 $(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 + 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

참고 문헌

• wikipedia.org/wiki/Prefix_sum