[컴퓨터 알고리즘] 누적합 알고리즘 (Prefix Sum)

보통 코딩 테스트에 등장하는 대부분의 누적합 알고리즘은 앞에서부터 더하는 Prefix Sum을

생각하면 된다.

 

이미지 출처 : https://sskl660.tistory.com/77

 

위의 사진처럼, 앞에서의 값과 현재의 값을 더해나가면서 누적합 Matrix 안의 원소를 결정하는 방법이다.

 

일반적으로 배열에 저장된 원소들의 값들을 꺼내서 일일이 더해가는 방식은 최악의 경우 O(N^2)의 시간 복잡도가 걸린다. 허나 이 누적합 방식을 사용하면 O(N)의 시간 복잡도 안에 해결할 수 있음이 보장된다.

 

쉽게 말해, M개의 구간을 가지는 N개의 구간 합을 계산하려면 O(MN)이 걸리는 것이 자명하다.

 

허나 기존의 구간합을 이용하여 다음의 구간합을 구할 수 있다면, O(N+M)의 시간 복잡도로 해결할 수 있음을 생각해보면 이해가 된다.

 

아래는 위 누적합 알고리즘을 사용하여 해결한 백준 문제 포스팅이다.

백준 11660 - 구간 합 구하기 5 [C/C++] — 예비 대학원생의 Computer Science 저장소 (tistory.com)

백준 11660 - 구간 합 구하기 5 [C/C++]