[Algorythm] 누적합

 

 1. 누적합

  누적합은 리스트의 각 원소에 대해 누적합을 가진 리스트를 별도로 생성해 구간합을 미리 구해두는 방법. 원소/혹은 구간 누적합을 범위 누적합에서 빼주면 되기 때문에, 특정 구간 누적합을 구하기 쉽다. 과정은 아래와 같다.

1. 누적합 저장 리스트 만들기
2. 인덱스 구간에 따른 누적합을 저장 리스트에 추가

#1 합의 리스트
arr = [1, 2, 3, 4, 5, 6, 7]

sum_arr = []
total = 0
for a in arr:
    total += a
    sum_arr.append(total)

print(sum_arr) # [1, 3, 6, 10, 15, 21, 28]


#2 accumulate 함수
from itertools import accumulate
arr = [1, 2, 3, 4, 5, 6, 7]

sum_arr = list(accumulate(arr))

print(sum_arr) # [1, 3, 6, 10, 15, 21, 28]


#3 
arr = [1, 2, 3, 4, 5, 6, 7]
N = len(arr)
sum_arr = [0] * N
for i in range(N):
    sum_arr[i] = sum_arr[i - 1] + arr[i]

print(sum_arr) # [1, 3, 6, 10, 15, 21, 28]

 

누적합 리스트 sum_arr의 인덱스를 0이 아닌 1부터 시작하게 만들면 편하다.

1. 범위를 구할 때 매번 1씩 빼지 않아도 됨
2. 첫 번째 값부터 누적합을 구할 때 마지막 값(-1 위치)을 보는 것을 신경쓰지 않아도 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

참고문헌

https://wikidocs.net/206294