[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() fo..

2022.05.04