누적 합(Prefix sum)

n크기의 배열 arr이 주어지고 k번째 항목까지의 합을 구하는 코드는 아래와 같이 간단히 구현할 수 있다.

sum = 0
for i in range(1, k+1):
    sum += arr[i]
print(sum)

i번째 항목까지의 합을 구하는 코드는 1부터 k번째까지의 항목을 탐색하며 한 번씩 합 연산을 실시하므로 시간 복잡도가 O(N)이다. 나쁘지 않은데?

 

그런데 배열 길이가 10^6, 테스트 케이스가 10³개가 된다면 어떨까. 

10986번: 나머지 합

죽음 뿐...

 

따라서 시간 복잡도를 개선할 수 있는 알고리즘을 찾아봐야 한다.

 

1. 알고리즘

누적 합은 이전 값을 그대로 사용해 다음 값을 얻을 수 있으므로 동적 계획법으로 접근이 가능하다. arr 배열의 i번째 항목 까지의 누적 합을 S[i]라고 한다면, S[10]을 구했을 때 S[11]을 구하려면 꼭 arr[1]부터 출발할 필요 없이 S[10]에 arr[11]을 더해주기만 하면 되는 것이다. 따라서 S[i]를 아래 코드처럼 구하면 모든 시도를 수행할 필요 없이 O(N)의 시간 복잡도로 한 번 연산을 실시해 O(1) 내에 모든 누적 합을 빠르게 구할 수 있다.

S = [0]*(len(arr)+1)
for i in range(1, len(arr)):
    S[i] = S[i-1] + arr[i]
print(S[int(input())])

 구간 합을 구하는 것도 가능하다. p부터 q번째 항목의 합은 S[q] - S[p-1]로 구할 수 있다. 이제 테스트 케이스의 수에 따라 M번의 연산을 수행한다면 O(M)이 된다.

 

2. 연습문제

11659번: 구간 합 구하기 4