알고리즘 - 누적합(Prefix Sum)

개념

말 그대로 구간의 누적의 합을 구하는 알고리즘이다. 배열에 값을 저장하고 하나씩 더해가는 방식은 O(n^2)의 시간 복잡도를 갖는다. 하지만 누적합 알고리즘을 사용한다면 O(n)으로 시간복잡도를 줄일 수 있다. 보통 누적합은 부분 합을 구하기 위해서 사용하는데 만약 a부터 b까지의 합을 구한다고 하면 먼저 누적합을 만들고, b번째 요소에서 a-1번째 요소를 빼주면 구할 수 있다.

사용 하면 좋은 경우

1. 리스트에 일정 구간의 값의 합을 구할 때
2. 리스트에 일정 구간에 값을 넣어야 할 경우(시작과 끝 부분에 값 넣어놓고 누적합)

사용 방법

1. 구간의 합 구하기

import itertools

a = [3,2,1,6,8,4]
result = list(itertools.accumulate(a))

print(result)

🖨️ [3, 5, 6, 12, 20, 24]

1. 부분 합 구하기

import itertools

a = [3,2,1,6,8,4]
start = 3
end = 5
acc = list(itertools.accumulate(a))

result = acc[end] - acc[start-1]

🖨️ 18

누적합을 우선 구한 후 마지막 부분의 누적합 값에서 시작부분 전의 누적합을 빼서 부분 합을 구할 수 있다,

시간 복잡도

• O(N)