[알고리즘] 누적합 알고리즘 - 파이썬

누적합 알고리즘(Prefix sum)

 

누적합 알고리즘(Prefix sum)은 특정 구간에서

중간의 합계나 평균을 자주 구해야하는 경우에 사용할 수 있는 알고리즘이다. 

단순히 반복문을 사용해서 알고리즘을 구현하게 된다면 시간이 많이 소요되고,

코딩 테스트에서 조건으로 주어지는 시간 제한을 지키지 못하는 경우가 생겨나게 된다. 

 

 

누적합 알고리즘은 이런 시간 초과를 해결하기 위해서 구간별로 누적합을 계산해,

그 누적합을 저장하는 배열을 하나 만드는 방식으로 사용된다. 

 

 

예를 들어 다음과 같은 배열이 주어졌다고 가정해보자.

arr = [1, 8, 7, 4, 3, 5]

 

위와 같은 배열이 있을때, 각 구간의 누적합을 저장하는 새로운 배열을 아래와 같이 만들어준다. 

(가장 첫번째 원소로는 값 '0'을 넣어주었다.)

prefix_sum= [0, 1, 9, 16, 20, 23, 28]

 

이렇게 새로운 배열을 만들어 놓고, 문제에서 요구하는 구간에 맞추어 누적합 배열에서 값을 꺼내면 된다. 

만약 문제에서 arr의 index 0부터 3까지의 합을 구하라고 한다면 

prefix_sum[3+1] 에서 prefix_sum[0] 을 빼준 값을 출력하면 된다.

또 만약 문제에서 index 2부터 4까지의 합을 구하라고 한다면 

prefix_sum[4+1] 에서 prefix_sum[2] 를 빼준 값을 출력하면 된다.