누적 합 (Prefix Sum) 알고리즘
누적 합 (Prefix Sum) 알고리즘에 대해 정리한 페이지입니다.
누적 합 (Prefix Sum) 알고리즘
Tags
Algorithm
1. 개요
누적 합(Prefix Sum) 알고리즘에 대해 정리한 페이지입니다.
2. 누적 합 (Prefix Sum) 알고리즘
2.1. 개념
누적 합(Prefix Sum) 알고리즘은 배열의 구간 합(부분 합)을 빠르게 구할 수 있게 해주는 알고리즘 기법을 의미합니다.
다음과 같이 scores라는 1차원 정수 배열이 있을 때 첫 번째 원소부터 특정 index까지의 누적 합 배열 S이 있으면 다음과 같이 정의할 수 있습니다.
| index | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|
| scores | 100 | 97 | 86 | 79 | 66 | 52 | 49 | 42 | 31 |
| S | 100 | 197 | 283 | 362 | 428 | 480 | 529 | 571 | 602 |
javascript
1const scores = [100, 97, 86, 79, 66, 52, 49, 42, 31];
2
3const S = [100, 197, 283, 362, 428, 480, 529, 571, 602];2.2. 시간 복잡도 (Time Complexity)
일반적으로 단순히 배열을 순회하면서 합을 구하면 한 번 계산할 때마다 O(N)의 시간이 걸립니다.
하지만 누적 합 배열을 미리 계산해두면 구간 합을 O(1)의 시간에 구할 수 있습니다.
특히 누적 합 알고리즘은 구간 합을 여러 번 계산해야 할 때 효율적입니다.
예를 들어 구간 합을 M번 구하는 문제가 있을 때, 단순 덧셈 방식은 O(N * M)의 시간이 걸리지만,
누적 합 알고리즘을 사용하면 누적 합 배열을 미리 계산해 두는데 걸리는 O(N) 시간이 소모된 이후에는 구간 합을 계산하는데 걸리는 시간이 거의 없으며,
총 O(N + M)의 시간 복잡도를 갖습니다.
단순 덧셈 방식과 누적 합 사용 방식의 시간 복잡도를 비교하면 다음과 같습니다.
| 방법 | 구간 합 계산 시간 | 전체 사전 준비 시간 |
|---|---|---|
| 단순 덧셈 | O(N) | 없음 |
| 누적 합 사용 | O(1) | O(N) |
2.3. 구현
2.3.1. 1차원 배열에서의 누적 합
javascript
1const scores = [10, 20, 30, 40, 50];
2const S = Array(scores.length).fill(0);
3S[0] = scores[0];
4
5for (let i = 1; i < scores.length; i++) {
6 S[i] = S[i - 1] + scores[i];
7}
8
9console.log(S); // [10, 30, 60, 100, 150]
10
11/**
12 * scores[a]부터 scores[b]까지의 누적 합을 구하는 함수
13 * @param {number} a 시작 인덱스
14 * @param {number} b 끝 인덱스
15 * @returns scores[a]부터 scores[b]까지의 누적 합
16 */
17const rangeSum = (a, b) => {
18 if (a === 0) {
19 return S[b];
20 } else {
21 return S[b] - S[a - 1];
22 }
23};
24
25console.log(rangeSum(1, 3)); // 902.3.2. 2차원 배열에서의 누적 합
javascript
1const arr = [
2 [10, 20, 30, 30],
3 [20, 20, 40, 30],
4 [50, 30, 20, 50],
5 [40, 40, 40, 40],
6];
7
8const S = Array.from({ length: arr.length }, () =>
9 Array(arr[0].length).fill(0),
10);
11
12// 각 행에 대한 누적 합 계산
13for (let i = 0; i < arr.length; i++) {
14 S[i][0] = arr[i][0];
15
16 for (let j = 1; j < arr[i].length; j++) {
17 S[i][j] = S[i][j - 1] + arr[i][j];
18 }
19}
20
21for (let i = 1; i < arr.length; i++) {
22 for (let j = 0; j < arr[i].length; j++) {
23 S[i][j] += S[i - 1][j];
24 }
25}
26
27/*
28[
29 [ 10, 30, 60, 90 ],
30 [ 30, 70, 140, 200 ],
31 [ 80, 150, 240, 350 ],
32 [ 120, 230, 360, 510 ]
33]
34*/
35console.log(S);
36
37/**
38 * arr[startRow][startCol]과 arr[endRow][endCol]를 양 끝으로 갖는 부분 배열의 합을 구하는 함수
39 * @param {number} startRow
40 * @param {number} startCol
41 * @param {number} endRow
42 * @param {number} endCol
43 * @returns arr[startRow][startCol]과 arr[endRow][endCol]를 양 끝으로 갖는 부분 배열의 합
44 */
45const rangeSum = (startRow, startCol, endRow, endCol) => {
46 let result = S[endRow][endCol];
47
48 if (startRow > 0) {
49 result -= S[startRow - 1][endCol];
50 }
51
52 if (startCol > 0) {
53 result -= S[endRow][startCol - 1];
54 }
55
56 if (startRow > 0 && startCol > 0) {
57 result += S[startRow - 1][startCol - 1];
58 }
59
60 return result;
61};
62
63console.log(rangeSum(1, 1, 3, 3)); // 3103. Example
-
javascript
1const path = 2 process.platform === "linux" ? "/dev/stdin" : "./JavaScript/input.txt"; 3const input = require("fs").readFileSync(path).toString().split("\n"); 4 5// n: 수열의 길이, 10 <= n <= 100,000 6// s: 합, 0 <= s <= 100,000,000 7const [n, s] = input[0].split(" ").map(Number); 8const arr = input[1].split(" ").map(Number); 9const arrSum = Array(n).fill(0); 10 11arrSum[0] = arr[0]; 12for (let i = 1; i < n; i++) { 13 arrSum[i] = arr[i] + arrSum[i - 1]; 14} 15 16/** 17 * 시작 Index 부터 끝 Index 까지의 부분 합을 반환하는 함수 18 * @param {number} a 시작 Index 19 * @param {number} b 끝 Index 20 * @returns {number} 부분 합 21 */ 22const rangeSum = (a, b) => { 23 if (a === 0) { 24 return arrSum[b]; 25 } else { 26 return arrSum[b] - arrSum[a - 1]; 27 } 28}; 29 30let answer = Infinity; 31let a = 0; 32let b = 0; 33 34while (b < n) { 35 if (rangeSum(a, b) >= s) { 36 answer = Math.min(answer, b - a + 1); 37 a++; 38 } else { 39 b++; 40 } 41} 42 43console.log(`${answer === Infinity ? 0 : answer}`);