[Python] 5. 구간 합 계산

1. 구간 합

연속적으로 나열된 N개의 수가 있을 때, 특정 구간의 모든 수를 합한 값

각 쿼리에 대해 구간 합을 빠르게 계산하기 위해서는 N개의 수의 위치 각각에 대하여 접두사 합(Prefix Sum)을 미리 구해 놓으면 된다. (접두사 합 : 리스트 맨 앞부터 특정 위치까지의 합을 구해놓은 것을 의미)

예를 들어 5개의 데이터 구성된 수열 {10, 20, 30, 40, 50}이 있다고 가정해보자. 여기서 2번째 수부터 4번째 수까지의 합은 20 + 30 + 40으로 90이 될 것이다. 구간 합 계산 문제는 여러 개의 쿼리(Query)로 구성되는 문제 형태로 출제되는 경우가 많다.

M개의 쿼리가 존재한다고 가정해보면, 각 쿼리는 Right, Left로 구성되며, 이는 [Left, Right]의 구간을 의미한다. 결과적으로 쿼리가 주어졌을 때, 모든 쿼리에 대하여 구간의 합을 출력하는 문제가 전형적인 구간 합 계산문제이다.

만약 M개의 쿼리 각각, 매번 구간 합을 계산한다면 이 알고리즘은 O(NM)의 시간 복잡도를 가진다. 왜냐하면, M개의 쿼리가 수행될 때마다 전체 리스트의 구간 합을 모두 계산하라고 요구(첫 번째 수부터 N번째 수까지) 할 수 있기 때문이다.

알고리즘이 O(NM) 시간 복잡도를 가지게 되면 데이터 개수가 매우 많을 때 시간초과로 문제를 해결 할 수 없을 것이다.

 

구간 합 빠르게 계산하기 알고리즘

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

위 알고리즘대로 매 쿼리가 들어왔을 때, P[R] - P[L-1]을 계산하면 바로 구간 합을 구할 수 있게 된다. 따라서 매 쿼리당 계산 시간은 O(1)이 되고, 결과적으로 N개의 데이터와 M개의 쿼리가 있을 때, 전체 구간 합을 구하는 작업은 O(N + M)의 사간 복잡도를 가진다. 

쿼리 3개가 있다고 했을 때의 구간 합을 구하는 과정은 다음과 같다. 

1. 첫 번째 쿼리는 첫 번째 수부터 세 번째 수까지의 구간 합을 물어보는 [1, 3]이라면, P[3] - P[0]이 된다. 
2. 두 번째 쿼리는 두 번째 수부터 다섯 번째 수까지의 구간 합을 물어보는 [2, 5]라면, P[5] - P[1]이 된다.
3. 세 번째 쿼리는 세 번째 수부터 네 번째 수까지의 구간 합을 물어보는 [3, 4]라면, P[4] - P[2]가 된다. 

# 전체 데이터 선언
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])

#70

 

 

https://developersj.tistory.com/104

백준 11659번 : 구간 합 구하기 4

 

 

 

'이것이 코딩테스트다'를 읽고 공부한 내용을 바탕으로 작성하였습니다.