[Algorithm] 누적 합

만약 배열 [1, 2, 3, 4, 5, 6]에서 인덱스 3번째 원소 ~ 5번째 원소까지의 합을 구하려면 어떻게 해야할까?

2가지 방법이 있다.

1. 완전 탐색으로 for 문 돌리기

배열에 포함된 원소의 수가 N개일 때의 시간 복잡도는 O(N)이다.

int answer = 0;

for (int i = 3; i < 6; i++) {
	answer += arr[i];
}

 

2. psum 사용하기

psum을 사용하면 시간 복잡도를 O(1)로 줄일 수 있다.

psum은 원본 배열의 원소들의 누적합을 구한 배열이다.

 

i = 0일 때, psum[i] = arr[i]으로, psum[0] = arr[0]이다.

i = 1일 때에는 psum[1] = arr[0] + arr[1] = psum[0] + arr[1]이고,

i = 2일 때에는 psum[2] = arr[0] + arr[1] + arr[2] = psum[1] + arr[2]이고,

i = 3일 때에는 psum[3] = arr[0] + arr[1] + arr[2] + arr[3] = psum[2] + arr[3]이므로,

 

최종적으로 psum[i] = psum[i - 1] + arr[i] (i ≥ 1)라는 식을 얻게 된다.

 

 

그럼 arr[3]에서 arr[5]까지의 누적합을 구하려면 어떻게 하면 될까?

위와 같은 과정에 의해서 나온 식을 일반화하면 배열 arr의 어떤 구간 i, j (i ≤ j)의 합은

arr[i] + arr[i + 1] + … + arr[j - 1] + arr[j] = psum[j] - arr[i - 1]과 같다.

 

이 때 만약 i가 0일 경우 psum[i - 1]은 잘못된 인덱스 접근이므로,

i가 0일 때는 psum[i - 1]은 0이라고 따로 처리를 꼭 해줘야한다.

 

Swift 코드

func partialSum(_ psum: [Int], i: Int, j: Int) -> Int {
    if (i == 0) { return psum[j] }
    return psum[j] - psum[i - 1]
}

var arr = [1, 2, 3, 4, 5, 6]
var psum: [Int] = []

var sum = 0
for number in arr {
    sum += number
    psum.append(sum)
}

print(psum) // [1, 3, 6, 10, 15, 21]

let partialSumResult = partialSum(psum, i: 3, j: 5) // 4 + 5 + 6 = 15
print(partialSumResult) // 15

 

C++ 코드

int partial_sum(int* psum, int i, int j) {
     if (i == 0) return psum[j];
     return psum[j] - psum[i - 1];
}

 

 

관련 문제들

백준 11441번 풀이

백준 2167번 풀이

백준 11659번 풀이