파이썬으로 구현하는 구간합과 누적합(Prefix sum)

구간합이란?

구간합이란, 나열된 숫자에서 특정 구간의 합을 말합니다.

 

만약 위의 arr에서 1~3번째 구간합을 구하고 싶다면, arr[1]+arr[2]+arr[3] = 4+3+2 = 9 입니다.

 

가장 기본적인 구간합 알고리즘을 생각해보면, 단순히  i~j번째까지의 값을 더하면 되고 이때 시간복잡도는 O(N)입니다.

하지만, 배열의 크기인 N이 매우 크고 구간합을 물어보는 쿼리가 N번이라면,

다음과 같이 O(N)*O(N) ≈  O(N^2)이라는 거듭제곱의 높은 시간복잡도를 가지는 알고리즘이 됩니다.

arr = list(map(int, input().split())) # 크기가 n개인 arr

for _ in range(N): # N 번의 쿼리 : O(N)
    i, j = map(int, input().split())
    sub_sum = sum(arr[i:j+1]) # i~j 번째의 구간합 : O(N)

 

 

 

누적합(Prefix sum)이란?

제곱의 시간복잡도를 가지는 구간합 문제를 누적합(Prefix sum)을 활용하면 O(N)으로 풀 수 있습니다.

먼저 누적합(Prefix sum)이란, 나열된 숫자의 누적된 합을 말합니다.

 

prefix_sum 배열을 활용하면, 다음과 같이 O(N) + O(N)*O(1) ≈ O(N) 선형 시간내에서 구간합을 구할 수 있습니다.

arr = list(map(int, input().split())) # 크기가 n개인 arr
prefix_sum = [0]

for i in range(len(arr)): # O(N)
    prefix_sum.append(prefix_sum[i]+arr[i])

for _ in range(N): # N 번의 쿼리 : O(N)
    i, j = map(int, input().split())
    sub_sum = prefix_sum[j] - prefix_sum[i-1] # i~j 번째의 구간합 : O(1)

 

 

다음 글에서는, O(N)보다 더 개선된 O(logN)으로 구간합을 구할 수 있는 세그먼트 트리에 대해서 알아보도록 하겠습니다.

https://codingsmu.tistory.com/176

파이썬으로 구현하는 세그먼트트리(Segment Tree)