누적합 문제 풀이 정리를 처음 배우면 공식은 단순한데, 왜 이렇게 자주 나오는지 감이 잘 안 잡힐 수 있습니다. 핵심은 수학 공식이 아니라, 같은 구간 합을 여러 번 다시 계산하면 너무 느려진다는 점입니다.
즉 누적합은 계산을 똑똑하게 한 번 미리 해두고, 질문이 들어올 때 빠르게 꺼내 쓰는 방법이라고 보면 이해가 쉽습니다. 이번 보강판에서는 1차원/2차원 감각과 시간초과가 나는 이유를 더 자세히 설명합니다.
왜 시간초과가 자주 날까
구간 합 문제를 순진하게 풀면 질문이 들어올 때마다 처음부터 끝까지 다시 더하게 됩니다. 질문 수가 많아지면 이 반복 작업이 그대로 시간초과로 이어집니다.
# 비효율적
for l, r in queries:
total = 0
for i in range(l, r + 1):
total += arr[i]문제는 한 번의 합이 아니라, 이런 합 계산이 여러 번 반복된다는 데 있습니다. 질의가 많을수록 같은 부분을 다시 더하는 비용이 기하급수적으로 아깝게 느껴집니다.
1차원 누적합은 어떻게 보나
prefix[i]를 0번부터 i번까지의 합이라고 정의하면, l부터 r까지의 구간 합은 prefix[r] – prefix[l-1] 형태로 바로 구할 수 있습니다.
prefix = [0] * (n + 1)
for i in range(1, n + 1):
prefix[i] = prefix[i-1] + arr[i-1]
# arr[l] ~ arr[r] (0-indexed)
range_sum = prefix[r+1] - prefix[l]
즉 핵심은 매번 합을 다시 구하지 않고, 이미 쌓아둔 합의 차이로 답을 꺼내는 것입니다. 이 감각이 잡히면 누적합은 공식이 아니라 “한 번 계산한 정보를 재사용하는 구조”로 보이기 시작합니다.
입문자가 자주 놓치는 점은 prefix 배열을 왜 n+1 길이로 잡는지입니다. 맨 앞에 0을 하나 두면 l이 0일 때도 예외 처리를 줄일 수 있어 코드가 훨씬 안정적입니다.
2차원 누적합은 왜 더 자주 헷갈릴까
2차원에서는 사각형 영역 합을 구해야 하므로 한 번 더 겹치는 부분을 빼고 더하는 감각이 필요합니다. 그래서 공식은 외워도 왜 그런지 이해가 안 되면 쉽게 잊어버립니다.
2차원 누적합은 위쪽, 왼쪽, 대각선 겹침을 함께 정리한다고 생각하면 조금 더 자연스럽습니다. 즉 “한 번 더해진 영역을 한 번 빼준다”는 포함-배제 감각이 핵심입니다.
자주 하는 실수
- 0-index와 1-index를 섞는다
- l이 0일 때 예외 처리를 놓친다
- 2차원 누적합에서 겹치는 영역을 한 번 더 빼야 한다는 점을 놓친다
- 사실은 슬라이딩 윈도우나 투 포인터가 더 맞는 문제를 누적합으로만 보려 한다
즉 누적합은 강한 도구이지만, “여러 번 반복되는 구간 합 질의”라는 신호가 있을 때 특히 잘 맞습니다. 반대로 구간 길이가 계속 움직이거나 실시간 갱신이 핵심인 문제라면 다른 접근이 더 맞을 수 있습니다.
누적합은 슬라이딩 윈도우나 투 포인터와도 비교해서 보면 더 잘 이해됩니다. 반복 구간 합이라는 신호가 분명하면 누적합이 잘 맞고, prefix sum 개념처럼 전처리 관점으로 보면 왜 시간초과를 줄이는지 감이 더 빨리 잡힙니다.
마무리
누적합 문제를 잘 푸는 핵심은 공식을 외우는 것보다, 반복되는 합 계산을 미리 저장된 정보의 차이로 바꾸는 발상입니다.
즉 구간 합 문제에서 중요한 것은 계산을 빨리 하는 손기술보다, 반복되는 일을 한 번의 전처리로 줄일 수 있는가를 먼저 보는 눈입니다.
