누적 합과 구간 합(Prefix Sum) + 백준 11659, 11660: 구간 합 구하기

개요

누적 합 알고리즘을 이해하고 이를 사용해서 구간 합 문제를 시간초과 없이 해결해보자.
 

• 첫번째 요소는 무조건 0으로 시작합니다. (ex. prefixSum(0, 0), arr[0][0])
• prefixSum(i): arr[0]~arr[i] 누적합
• rangeSum(i, j): arr[i]~arr[j] 구간합, 2차원 배열의 경우 rangeSum(i1, j1, i2, j2)

 

---

누적 합/구간 합 이해하기

1차원 배열 누적 합/구간 합

구간 합

다음과 같은 배열이 존재할 때 arr[3]부터 arr[5]까지의 합을 구해보자.

rangeSum(3, 5)는 prefixSum(5)에서 prefixSum(2)을 뺀 값과 같다.

rangeSum(i, j) = prefixSum(j) - prefixSum(i-1)

 
따라서, 구간합을 빠르게 계산하기 위해서는 각 인덱스까지 누적합을 미리 알고 있는 것이 좋다.
 
 
 

누적 합

rangeSum(3)을 구한다고 가정해보자.

 
rangeSum(3)은 arr[0]+arr[1]+arr[2]+arr[3], 즉 바로 직전 인덱스까지의 누적합(rangeSum(2))에 현재 인덱스 값(arr[3])을 더한 것과 같다.
 

prefixSum(i) = prefixSum(i-1) + arr(i)

 
 
이제 누적합 배열 sum을 구현해보자.

누적합을 구하려는 인덱스가 i라면 sum[i] = sum[i-1] + arr[i] 가 된다.
 
 
 

누적 합으로 구간 합 계산하기

1. DP 방식을 사용해 인덱스 0부터 순차적으로 누적합을 계산한다.
2. prefixSum을 활용하여 구간합을 계산한다.

// js

let arr = [1, 2, 3, 4, 5, 6, 7];
let prefixSum = Array(arr.length).fill(0);

prefixSum[0] = arr[0];

for (let i = 1; i < arr.length; i++) {
  prefixSum[i] = prefixSum[i - 1] + arr[i];
}

/** 누적합으로 구간합 계산하기 */
let [start, end] = [3, 5];  // arr[3]~arr[5]

let rangeSum = prefixSum[end] - prefixSum[start - 1];
console.log(rangeSum);  // 15

 
 
 

---

2차원 배열 누적 합/구간 합

2차원 배열도 1차원 배열과 동일하다.
arr(0, 0)부터 각 요소까지의 누적합을 계산한 뒤, 그 누적 합을 이용해 간단하게 구간합을 구할 수 있다.
 

누적 합

예시1. 2x2 배열의 누적합

• prefixSum(0, 0) = arr[0][0] = 1
• prefixSum(0, 1) = arr[0][0] + arr[0][1] = 1+2 = 3
• prefixSum(1, 0) = arr[0][0] + arr[1][0] = 1+3 = 4
• prefixSum(1, 1) = arr[1][1] + prefixSum(0, 1) + prefixSum(1, 0) - prefixSum(0, 0) = 4+3+4-1 = 10

prefixSum(0, 0)는 두 번 더해졌기 때문에 빼주는 것이다.
 

prefixSum(i, j)  = arr[i][j] + prefixSum(i, j-1) + prefixSum(i-1, j) - prefixSum(i-1, j-1)

 
 
 

예시2. 4x4 배열의 prefixSum(2, 2)

prefixSum(2, 2)
= arr[2][2] + prefixSum(2, 1) + prefixSum(1, 2) - prefixSum(1, 1)
= 5 + (1+2+2+3+3+4) + (1+2+3+2+3+4) - (1+2+2+3)
= 5+15+15-8
= 27
 
마찬가지로 현재 요소 기준으로 이전 열까지의 누적합과 상단 행까지의 누적합을 더한 뒤, 중복으로 더해지는 부분을 빼주면 된다.
 
 
 

구간 합

누적 합을 사용해서 구간합 rangeSum(1, 1, 2, 3)을 구해보자

rangeSum(1, 1, 2, 3)
= prefixSum(2, 3) - prefixSum(2, 0) - prefixSum(0, 3) + prefixSum(0, 0)
= (1+2+3+4+2+3+4+5+3+4+5+6) - (1+2+3) - (1+2+3+4) + 1
= 42-6-10+1
= 27
 
현재 요소까지의 누적합에서 이전 열까지의 누적합과 상단 행까지의 누적합을 뺀 뒤, 중복으로 뺀 부분을 더해주면 된다.
 

rangeSum(i1,j1,i2,j2)  = prefixSum(i2, j2) - prefixSum(i2, j1-1) - prefixSum(i1-1, j2) + prefixSum(i1-1, j1-1)

 
 
 

누적 합으로 구간 합 계산하기

// js

let arr = [
  [1, 2, 3, 4],
  [2, 3, 4, 5],
  [3, 4, 5, 6],
  [4, 5, 6, 7],
];

let n = arr.length;

let prefixSum = Array.from({ length: n + 1 }, () => Array(n + 1).fill(0));

for (let i = 1; i <= n; i++) {
  for (let j = 1; j <= n; j++) {
    prefixSum[i][j] = arr[i - 1][j - 1] + prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1];
  }
}

console.log(prefixSum);
// [ -> 첫번째 행,열은 무시
//   [0, 0, 0, 0, 0],
//   [0, 1, 3, 6, 10],
//   [0, 3, 8, 15, 24],
//   [0, 6, 15, 27, 42],
//   [0, 10, 24, 42, 64]
// ]

/** 누적합으로 구간합 계산하기 */
let [i1, j1, i2, j2] = [2, 2, 3, 4]; // rangeSum(1, 1, 2, 3)

let rangeSum = prefixSum[i2][j2] - prefixSum[i1 - 1][j2] - prefixSum[i2][j1 - 1] + prefixSum[i1 - 1][j1 - 1];
 console.log(rangeSum); // 27

 
 
 

---

왜 누적 합 알고리즘을 사용할까?

구간합은 중복 for문을 사용하면 더 이해하기 쉽게 구현할 수 있다. 그럼에도 누적합 알고리즘을 사용하는 이유는 "시간 복잡도" 때문이다.
 
중첩 for문을 사용해서 구간합을 구하는 로직은 다음과 같다.

let rangeSum = 0;

/** 중첩 for문으로 구간합 계산하기 */
for (let i = i1; i <= i2; i++) {
  for (let j = j1; j <= j2; j++) {
    rangeSum += arr[i][j];
  }
}

 
중첩 for문을 사용하면 새로운 구간합을 구할 때마다 for문을 돌아야하기 때문에 O(n^2)의 시간이 걸린다. 반면, 누적합을 사용하면 사전 계산해놓은 값들을 바탕으로 O(1) 시간만에 계산할 수 있다.
 
따라서 시간 초과를 피하기위해서는 누적합 알고리즘을 사용하는 것이 효율적이다.
 
 
 

---

백준 문제 풀이 (javaScript)

🔗 백준 11659: 구간 합 구하기 4

algorithm/백준/실버/11659_구간합구하기4_241029.js at main · yyyejinnn/algorithm

 
 

🔗 백준 11660: 구간 합 구하기 5

처음에 중첩 반복문을 사용했다가 시간초과 났었다.

algorithm/백준/실버/11660_구간합구하기5_241028.js at main · yyyejinnn/algorithm