구간합
나열된 숫자에서 특정 구간의 합
일반적으로 리스트에서 특정 구간에 있는 데이터들의 합을 계산한다고 하는 것은 문제가 안되지만,
데이터의 크기가 매우 크고, 그 구간합을 구하는 코드가 반복된다면 약 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)
Python
복사
누적합
구간합의 문제를 누적합을 활용하면 O(N)으로 풀 수 있다.
누적합은 말 그대로 나열된 숫자의 누적된 합을 의미한다.
누적합 배열을 활용하면, 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)
Python
복사