[구간 합] 접두사 합

구간 합의 시간복잡도는 O(NM)이다. N,M의 데이터가 커지면 시간복잡도가 증가하게 되어 문제가 발생한다.

 

이럴 경우 구간 합 혹은 누적 합 계산을 빠르게 하기 위해 접두사 합을 이용하면 된다.

 

접두사 합은 리스트의 맨 앞부터 특정 위치까지의 합을 미리 구해놓은 것이다.

 

아래를 코드를 실행시키면

sum value = [0, 10, 30, 60, 100, 150] 이 되며

sum_value[right] - sum_value[left-1] 을 해주면 빠르게 구할 수 있다.

 

n = int(input())

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])

 

 

1. 관련 문제

 

11659번 구간 합 구하기 4 O (실버3) 

 

import sys

input = sys.stdin.readline

n,m = map(int, input().rstrip().split()) #n수의 개수 m 횟수

num = list(map(int, input().rstrip().split()))

value = 0
prefix_sum = [0]

for i in num:
  value += i
  prefix_sum.append(value)


for i in range(m):
  left, right = map(int, input().rstrip().split())
  print(prefix_sum[right] - prefix_sum[left-1])

11660번 구간 합 구하기5