누적합이란 무엇인가?

누적합을 알기 전...

 

이 알고리즘을 접하기 전에는 for문을 통해 리스트를 순회하며 전부 하나하나씩 더하거나,

파이썬 내장함수인 sum을 이용해 합을 구하고는 했다.

 

하지만 이런 방식은 시간 복잡도상 치명적인 결함을 가지고 있다. 

 

일단 for문으로 리스트를 일정 구간만큼 순회해야하는 시간복잡도 O(N)

그리고 순회해서 일정 구간에대한 연산 M번. (sum또한 같은 시간복잡도를 지닌다)

 

총 시간복잡도는 O(NM)이 되게 되는데, 만약  전체를 더해야한다면 , M은 N이 되고 최악의 경우 O(N^2)의 시간복잡도를 지닌다.

 

누적합이란 무엇인가?

 

하지만 만약 배열의 특정 구간을 더해야 한다면, 그 배열의 데이터가 변하지 않는 이상,  특정구간까지의 합은 변할 가능성은 없다.

 

즉 [0]~[1] 의 합은 쭉 그 값일거고, [0]~[10]의 합도 쭉 그값일 거다.

이 아이디어로 0부터 그 위치의 값까지 합을 데이터로 저장한 리스트를 하나 만든다.

 

이 아이디어는 특정 구간의 합을 구하는데 결정적인데, 만약 빨간색구간만큼의 합을 구하고 싶다고 하자.

그러면 검은색 구간에서 파랑색의 값만큼을 빼면 된다.

즉 배열상 검은색 끝에 위치한 누적합 리스트 값에서 하늘색 끝에 위치한 리스트 값을 빼면 연산한번으로 빨간색 구간만큼의 합을 구할 수 있다.

 

결론

 

특정구간을 순회해 연산할 필요 없이, 이미 연산해놓은 값을 토대로, 다시 뺼셈 연산만 하면 되기 떄문에 시간 복잡도가 획기적으로 줄어들게 된다.