[ Algorithm ] 누적합 알고리즘

누적합 알고리즘

누적합 알고리즘은 어원 그대로 특정 값을 누적해서 더해줄때 사용되는 알고리즘이다.

코딩테스트에서 구간의 합을 구하는 문제에서 주로 사용된다.

 

누적합 알고리즘 동작방식

• 접두사 합(Prefix Sum): 배열 가장 앞부터 특정하는 위치까지 각 누적합을 미리 구해놓은 것이다.
• 접두사 합을 활용하여 알고리즘을 을 아래와 같이 만들 수 있다.
  위치 각각에 대한 접두사 합을 계산하여 P에 저장한다.
  매번 특정 수 만큼의 쿼리정보를 확인할때 구간 합은 P[right] - P[left - 1] 이다.

 

• 주어진 배열

Index	1	2	3	4	5	6	7	8
Value	3	2	4	1	2	2	1	5

 

• 접두사 합 배열

Index	0	1	2	3	4	5	6	7	8
Value	0	3	5	9	10	12	14	15	20

 

이에 [주어진 배열]에서 각 인덱스별로 누적합을 구한 것이 [접두사 합 배열 (p)]이다.

누적합 알고리즘에서 주어지는 공식 P[right] - P[left - 1] 를 생각했을때 아래의 예시를 확인해보자.

 

[주어진 배열]에서 1부터 3번째 인덱스가 가진 value의 누적합을 구해야 하는 문제이다.

[1, 3] => p[3] - p[0] = 9

< [주어진 배열]을 확인하면 3 + 2 + 4 이기 때문에 결과는 9가 되는 것을 확인 할 수 있다. >

 

[주어진 배열]에서 1부터 3번째 인덱스가 가진 value의 누적합을 구해야 하는 문제이다.

[3, 5] => p[5] - p[2] = 7

< [주어진 배열]을 확인하면 4 + 1 + 2 이기 때문에 결과는 7이 되는 것을 확인 할 수 있다. >

 

누적합 알고리즘을 활용한 예시문제

• 데이터의 개수 N이 8로 주어진다.
• 찾고자 하는 데이터 4번째 부터 8번째의 값의 누적합을 구해야 한다. (left = 4, right = 8)

let n = 8;
let arr = [3, 2, 4, 1, 2, 2, 1, 5];

// 접두사 합 배열
let sumValue = 0;
let prefixSum = [0];

for (let i of arr) {
  sumValue += i;
  prefixSum.push(sumValue);
}

// 네 번째 수부터 여덟 번째 수까지
let left = 4;
let right = 8;

console.log(prefixSum[right] - prefixSum[left - 1]);

 

마치며...

누적합 알고리즘은 내가 생각했던 것 보다 훨씬 효율적으로 특정 범위의 누적합을 구하는 방식이었던 것 같다. 알고리즘을 공부하면서 컴퓨터 공학과 수학은 뗄레야 뗄 수가 없는 관계인 것을 다시금 느꼈다.