[파이썬] 구간 합(Interval Sum)

[구간 합 문제란 ?]

연속적으로 나열된 N개의 수가 있을 때 특정 구간의 모든 수를 합한 값을 계산하는 문제이다.

 

예를 들어 5개의 데이터로 구성된 수열 {10, 20, 30, 40, 50}이 있다고 가정하고, 

 

두번째 수부터 네번째 수까지의 합은 20 + 30 + 40 = 90 이다.

 

구간 합 문제를 빠르게 계산하기 위해 접두사 합(Prefix Sum)을 활용한 알고리즘을 사용할 수 있다.

 

 

[접두사 합이란 ?]

배열의 맨 앞부터 특정 위치까지의 합을 미리 구해 놓은 것이다. 즉, 접두사 합을 활용한 알고리즘 동작과정은 다음과 같다.

 

1. N개의 수 위치 각각에 대하여 접두사 합을 계산하여 P에 저장한다.

 

2. 매 M개의 쿼리 정보를 확인할 때 구간 합은 P[Right] - P[Left - 1] 이다.

 

 

[구간 합 예제]

#데이터의 개수 N과 데이터 입력
n = 5
data = [10, 20, 30, 40, 50]

# 접두사 합 배열 계산
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])

 

---

출처

이것이 코딩 테스트다 with 파이썬 - 나동빈 저