[Algorithm] 누적 합(Prefix sum) 알고리즘 개념 및 코드

 

 

 

누적 합

Prefix sum

이번 포스팅에선 누적 합 알고리즘을 살펴보겠다.

꽤 간단하지만 알고리즘이지만, 의외로 모르는 사람이 꽤 있다.

Let's Go

 

 

 

 

 

다음과 같은 문제가 있다. 

 

n_list = [n for n in range(1, 100)]


50번째부터 - 80번째까지의 수를 더한 값을 리턴하라.

 

 

 

 

 

누적 합 알고리즘을 사용하지 않는다면?

---

 

단순히 리스트를 50번째부터 80번째까지 뽑아서 계산하는 방식을 가장 먼저 떠올릴 것이다.

 

 

코드로 표현하면 다음과 같다. 

 

sum(n_list[49:79])

 

 

겉으론 문제가 없어 보이지만, 누적 합을 구하라는 요청이 많아지면 상황이 달라진다.

 

 

import time

n_list = [n for n in range(1, 10000)]


start = time.time()
for i in range(1, 1000):
  sum(n_list[i:i+1000])

print(f'소요 시간: {round(time.time() - start, 5)}초')


소요 시간: 0.01816초

 

 

1000개의 누적 합 요청이 들어올 경우, 1000번의 계산을 새롭게 해야 한다.

매번 (1) 리스트를 뽑고 (2) 그 수들을 합해야 하는 과정을 반복한다는 뜻이다. 

자칫 시간 복잡도가 O(n^2)가 되어버릴 수 있기에 해결책이 필요하다. 

 

 

 

 

 

누적 합 알고리즘을 사용한다면?

---

누적 합 알고리즘은 '그럴거면 누적 합을 미리 구해놓고 활용해라'라는 신념을 가진다.

 

 

 

코드로 표현하면 다음과 같다.

 

import itertools

result = list(itertools.accumulate(n_list))
result[79] - result[48]

 

 

성능을 확인해보자.

 

 

import itertools

result = list(itertools.accumulate(n_list))

start = time.time()
for i in range(1, 1000):
  if i-2 < 0:
    a = 0
  else:
    a = i-2 
  result[i + 999] - result[a]

print(f'소요 시간: {round(time.time() - start, 5)}초')


소요 시간: 0.00047초

 

 

성능이 확실하게 향상된 것을 확인할 수 있다. 

이제 문제를 풀어보자.

 

 

https://www.acmicpc.net/step/48

누적 합 단계