한 번 미리 계산해 수많은 구간 합을 즉시 구하는 패턴
같은 배열에서 구간 합 질문이 반복되면 매번 더하는 일을 없앨 수 있습니다. O(n)의 전처리 한 번으로 각 쿼리를 O(1)에 답하는 대표적인 시간-공간 교환입니다.
코드를 생각하지 말고, 아래 상황이 어떤 순서로 움직이는지만 따라가 보세요.
오늘 계량기 숫자에서 지난달 시작일 숫자를 빼면 그 기간에 쓴 전기를 알 수 있습니다.
매일 돈을 넣은 뒤 현재까지 총액을 적어두면 월요일부터 수요일까지 모은 돈은 수요일 누계에서 일요일 누계를 빼면 됩니다.
코딩 테스트의 장난감 예제를 넘어, 실제 시스템에서 같은 원리가 어디에 숨어 있는지 연결해 보세요.
날짜 범위별 요청 수·매출 합을 빠르게 계산합니다.
2차원 누적합으로 사각 영역의 픽셀 합을 구합니다.
여러 구간의 평균과 변화량을 반복 계산합니다.
매일의 사용량 누계로 임의 기간의 총사용량을 바로 계산합니다.
지역 격자의 누적 강수량으로 특정 사각 구역의 총량을 빠르게 구합니다.
prefix[i]를 앞에서 i개 원소의 합으로 정의합니다. 그러면 [left, right]의 합은 prefix[right + 1] - prefix[left]가 됩니다. 앞부분이 서로 상쇄되는 원리입니다.
| 연산 | Python 표현 | 시간 |
|---|---|---|
| 전처리 | prefix 만들기 | O(n) |
| 구간 합 | prefix[r+1]-prefix[l] | O(1) |
| 메모리 | n+1개 저장 | O(n) |
| 값 갱신 | 뒤 누적합 수정 | O(n) |
prefix = [0]prefix = [0, 2, 6, 7, 10]prefix[4] - prefix[1]10 - 2 = 8설명을 닫고 먼저 풀어본 뒤, 막히는 지점에서 어떤 연산이 필요한지 다시 떠올려 보세요.
Easy 연습 1 / 7
Python으로 풀기Easy 연습 2 / 7
Python으로 풀기Easy 연습 3 / 7
Python으로 풀기Easy 연습 4 / 7
Python으로 풀기Easy 연습 5 / 7
Python으로 풀기Easy 연습 6 / 7
Python으로 풀기Easy 연습 7 / 7
Python으로 풀기Medium 연습 1 / 3
Python으로 풀기Medium 연습 2 / 3
Python으로 풀기Medium 연습 3 / 3
Python으로 풀기