[내가 보려고 적는 파이썬] 구간 합 계산

구간 합 계산

연속적으로 나열된 N개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 구하는 문제를 말한다. 이러한 문제는 여러 개의 쿼리로 구성되는 문제 형태로 출제된다. 쿼리는 [Left, Right] 형태로 구성되며 이는 구간을 뜻한다.

매번 구간 합을 계산한다면 해당 알고리즘은 O(NM)의 시간 복잡도를 가진다.(M개의 쿼리를 처음부터 끝까지 하라는 경우)
이러한 경우에, N과 M의 범위가 커진다면 문제를 해결할 수 없다.

접두사 합(Prefix Sum)

그렇다면 여러 번 사용될 만한 정보는 미리 구해 저장해두는건 어떤가? 확인해보면 쿼리는 M개지만 N개의 수는 한 번 주어지고 변경되지 않는다. 그러므로 접두사 합을 사용한다. N개의 수의 위치 각각에 대하여 접두사 합을 미리 구해두면 된다. 해당 알고리즘은 다음과 같다.

1. N개의 수에 대하여 접두사 합(Prefix Sum)을 계산하여 배열 P에 저장한다.
2. 매 M개의 쿼리 정보 [L, R]을 확인할 때, 구간 합은 P[R] - P[L-1]이다.

# 데이터의 개수 N과 전체 데이터 선언
n = 5
data = [10, 20, 30, 40, 50]

# 접두사 합(Prefix Sum) 배열 계산
sum_value = 0
prefix_sum = [0]
for i in data:
    sum_value += i
    prefix_sum.append(sum_value)
    
# 구간 합 계산(세 번째 수부터 네 번째 수까지)
left = 3
right = 4
print(prefix_sum[right] - prefix_sum[left-1])