구간 합

알고리즘 공부를 공부할때마다 느끼는 것이 있다.

알고리즘 공부는 비단 프로그래밍 실력만을 상승시킬뿐만 아니라,

공부하는 사람의 사고까지도 효율적으로 흘러갈 수 있도록 변화시킨다는 것이다.

구간합이란, 연속으로 나열된 N개의 수가 있을 때, 특정 구간의 모든 수를 합한 값을 구하는 것을 의미한다.

배열 [10, 20, 30, 40, 50]이 있다고 하면, 두 번째 수부터 네 번째 수까지의 합은 20 + 30 + 40으로 90이 될 것이다.

보통 구간합 문제가 나오면, 여러 개(M개)의 쿼리를 주고 해결하라는 형식으로 출제된다.

만약, 이 방법을 숫자가 주어질때마다 해당 배열의 수를 뒤져가며 매번 더하게 된다면 시간 복잡도는 O(NM)이 될 것이다.

그런데, 접두사 합(prefix sum)이란 방식을 사용한다면 그 시간복잡도를 O(N+M)으로 줄일 수 있다.

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

앞서 언급한 배열 [10, 20, 30, 40, 50]이 있다면,

[0, 10, 30, 60, 100, 150]이라는 매 자릿수를 누적하여 더한 배열을 미리 구해놓는 것이다.

이렇게 한다면, 두 번째 수부터 네 번째 수 까지의 합은 100 - 10 = 90이 될 것이다.

 

이 방법은, 메모리를 희생하여 시간을 줄이는 방법으로 이해된다.

 

n,m = map(int,input().split())
lst = list(map(int,input().split()))
sum_value = 0
prefix_sum = [0]
for i in lst:
    sum_value += i
    prefix_sum.append(sum_value)
for _ in range(m):
    left, right = map(int,input().split())
    print(prefix_sum[right] - prefix_sum[left-1])

 

백준 11659번으로, 해당 예시를 사용하기에 적절한 문항이다.

left에 0이 들어갔을 시에 index error를 방지하기 위해, 접두사 합 배열의 길이를 n+1로 설정하되

index 0번 값은 0으로 정해놓았다.