[백준] 11659 구간 합 구하기 4 (실버3) / 누적합 prefix sum

문제요약

나의 코드 및 설명

import sys

n, m = map(int, input().split())
num_list = list(map(int, sys.stdin.readline().split())) # [5 4 3 2 1]

#인덱스 혼동되지 않기 위해 n+1 길이의 합을 저장할 리스트 생성
prefix_sum = [0 for _ in range(n+1)] #[0,0,0,0,0,0]

#리스트에 누적된 합을 저장하는 소스 코드
for i in range(n): 
    prefix_sum[i+1] = prefix_sum[i] + num_list[i]

for _ in range(m):
    start, end = map(int, sys.stdin.readline().split())
    #누적된 합이 저장된 리스트의 (end 인덱스에 해당하는 값) - (start-1 인덱스에 해당하는 값)
    #                   = 구하려는 구간의 누적 합
    print(prefix_sum[end] - prefix_sum[start-1])

피드백

누적 합(prefix sum) 알고리즘을 통해 구간 합을 빠르게 구할 수 있다. 리스트에서 구간의 합을 구할 때 리스트와 구간의 크기가 모두 크다면, 리스트 구간에서 원소를 일일이 훑으며 더하는 것은 시간복잡도가 O(N^2)에 가깝게 되므로 성능이 매우 좋지 않다. 따라서 먼저, 입력 받은 숫자 리스트를 활용하여 누적 합 리스트를 생성하고, 구하려는 구간 start, end에 해당하는 두 원소의 차를 구해 그 구간의 합을 구하는 방식을 사용한다.