내일배움캠프 89일차 - 자료구조 & 알고리즘 17주차 : 누적 합

누적 합(Prefix Sum)

365일동안 모인 매출을 하루 단위로 정리하였을 때,
3월 1일부터 8월 31일까지 매출 합은?

가장 단순한 방법 - 매번 다시 더한다
: 질문이 올 때마다 처음부터 끝까지 다시 더한다. (위 질문 기준 약 30×6＝180번의 연산)
→ 위 질문을 10만번 반복하면 약 1,800만 번의 연산.

범위만 다른 같은 질문이 많아지면, 매번 처음부터 다시 더하는 비용이 그대로 쌓인다.

누적 합 방식
: "3월 1일까지의 합", "8월 31일까지의 합" → 모두 "1일부터 X일까지의 누적 합" 을 쓰고 있다.
: 그렇다면 "1일부터 X일까지의 합"을 딱 한번 만들어 둔다면?

[A일 ~ B일] 매출 합 = (1일~B일 누적) - {1일~(A-1)일 누적}
→ 어떤 구간이든 단 한번의 뺄셈

투 포인터
: 양쪽 끝에서 가운데로

슬라이딩 윈도우
: 같은 쪽에서 갱신하며 미끄러트리며

누적합
: 한 번 전처리로 구간 합을 O(1)으로

※ 세 기법의 공통점은 "이미 계산한 것을 버리지 않는다."는 것이다.