[Do it! 알고리즘 코딩테스트 with Python] 구간합

[출처: 10주완성 C++ 코딩테스트 | 알고리즘 코딩테스트 | 1주차 시간복잡도, 빅오표기법, 공간복잡도, 누적합, 구현]

위와 같이 진행할 경우, N이 10만이라는 숫자가 주어질 때, 10만 * 10만 = 100억의 시간복잡도가 생긴다. 이것은 불가능할 확률이 높다는 뜻이니 다른 방법을 써야한다! 함께 누적합을 알아보자.

다음과 같이 1번 박스, 2번 박스, 3번 박스 이렇게 만들어 놓고, 원하는 값이 있을 때 만들어놓은 박스들을 이용해서 구하는 방법이다! 근데 또 1번 박스 따로, 2번 박스 따로, 이렇게 만드는 것은 쉽지 않다. 그러므로 이전에 만들어놓은 값에 그 해당 요소만 더해가는 방식으로 만들어준다.

 

psum[1]

psum[2] = psum[1] + a[2]

psum[3] = psum[2] + a[3]

....