[알고리즘] 구간 합, 누적 합(Prefix Sum)

목차

• 누적 합이란?
• 언제 사용할까?
• 예시 및 코드

---

누적 합이란?

누적 합이란 수열 An에 대해서 각 인덱스까지의 구간의 합을 구하는 것을 누적 합이라고 합니다.

예를 들어 [1, 2, 3, 4, 5] 라는 배열이 있을 때, 각 구간까지의 합을 구하는 배열인 [ 1, 3, 6, 10, 15] 을 구한다고 가정해보면 아래와 같이 2가지로 구할 수 있습니다.

 

[ 첫번째 방법 ]
1
1+2
1+2+3
1+2+3+4
1+2+3+4+5
매번 현재 인덱스까지의 값을 반복하며 더해주기

[ 두번째 방법 ]
1
1+2
3+3
6+4
10+5
이전 인덱스까지의 누적합에 현재 값을 더해주기

 

 

어떤게 더 효율적일까요? 

배열의 갯수인 n을 늘려 [1, 2, ...,  99999, 10000]로 비교해보겠습니다.

 

[ 첫번째 방법 ]
1
1+2
1+2+3
...
1+2+...+9999
1+2+...+9999+10000
값을 구할때마다 n번 반복하니까 시간복잡도는 O(n^2) 가 되어 n이 큰 경우 사용할 수 없습니다.

[ 두번째 방법 ]
1
1+2
3+3
...
49985001+9999
49995000+10000
이전 인덱스까지의 합을 기억하고 있기 때문에 한번씩만 더해주면 되기에 시간복잡도는 O(N)이 됩니다.

 

 

언제 사용할까?

문제에서 Int 배열이 주어지고 어떠한 구간의 합을 구해야할 때 유용하게 사용할 수 있습니다.

 

 

예시 및 코드

위와 같은 배열이 주어지고 3번째 값부터 5번째 값까지의 구간 합을 구하는 예시를 들어보겠습니다.

 

우선 인덱스를 1부터 시작하도록 하기 위해 맨 처음에 0을 집어넣어 인덱스가 1부터 시작하도록 해줍니다.

 

누적 합을 저장할 배열을 만들고 값을 채워 줍니다.

 

 

3~5번 인덱스 값의 합은 1~5번 인덱스 값의 합 에서 필요없는 1~2번 인덱스값의 합을 빼주면 됩니다.

 

let input = [5, 3 , 11, 9, 12]

// 인덱스를 1부터 시작하도록 하기 위해
let array = [0] + input

// 누적 합
var prefixSum = Array.init(repeating: 0, count: array.count)
for i in 1..<array.count {
    prefixSum[i] = prefixSum[i-1] + array[i]
}

// 3~5번 인덱스 값의 합 = 1~5번 인덱스 값의 합 - 1~2번 인덱스 값의 합
let output = prefixSum[5] - prefixSum[2]

print(output) // 32