Ch.2 배열과 문자열
Prefix Sum — 구간 합을 O(1)에 구하기
1부터 100까지의 합을 매번 다 더해야 할까?
누적 합계를 미리 계산해두면 어떤 구간의 합이든 뺄셈 한 번이면 됩니다.
구간 합을 매번 O(n)으로 구하면 쿼리가 많을 때 너무 느리다!
Prefix Sum 배열을 한 번 만들면 모든 구간 합을 O(1)에 구할 수 있습니다!
핵심 개념
Prefix Sum
배열의 첫 번째 원소부터 i번째까지의 누적 합
Range Sum
배열의 특정 구간 [i, j]의 합
핵심 내용
가우스의 비밀처럼 미리 계산한 누적 합으로 구간 합을 O(1)에!
prefix[0] = 0으로 시작하면 경계 조건이 깔끔해집니다
def build_prefix_sum(arr):
n = len(arr)
prefix = [0] * (n + 1) # prefix[0] = 0 (더미)
for i in range(n):
prefix[i + 1] = prefix[i] + arr[i]
return prefix
def range_sum(prefix, i, j):
"""arr[i] + arr[i+1] + ... + arr[j] 를 O(1)에 반환"""
return prefix[j + 1] - prefix[i]
# 예시
arr = [2, 4, 1, 3, 5]
prefix = build_prefix_sum(arr)
print(prefix) # [0, 2, 6, 7, 10, 15]
print(range_sum(prefix, 1, 3)) # 4+1+3 = 8구간 합 = prefix[j+1] - prefix[i] 뺄셈 한 번이면 끝!
예시: arr = [2, 4, 1, 3, 5], prefix = [0, 2, 6, 7, 10, 15] sum(1, 3) = prefix[4] - prefix[1] = 10 - 2 = 8 ← (4+1+3) sum(0, 4) = prefix[5] - prefix[0] = 15 - 0 = 15 ← (전체합) sum(2, 2) = prefix[3] - prefix[2] = 7 - 6 = 1 ← (단일 원소)
면접 포인트: 전처리 O(n), 쿼리 O(1), 총 Q개 쿼리 → O(n + Q)
Prefix Sum + 해시맵을 결합하면 합이 K인 부분 배열 개수도 O(n)!
def subarray_sum(nums, k):
count = 0
prefix = 0
prefix_count = {0: 1} # prefix=0이 1번 등장
for num in nums:
prefix += num
# prefix - k가 이전에 나왔다면 → 합이 k인 구간 존재
if prefix - k in prefix_count:
count += prefix_count[prefix - k]
prefix_count[prefix] = prefix_count.get(prefix, 0) + 1
return count
print(subarray_sum([1, 1, 1], 2)) # 2 ([1,1] 두 번)Prefix Sum 배열을 한 번 구축한 뒤 구간 합 쿼리의 시간복잡도는?
arr = [2, 4, 1, 3, 5]일 때 prefix 배열은?
구간 합 공식: sum(i, j) = prefix[j + 1] - prefix[____]
구간 합 공식: sum(i, j) = prefix[j + 1] - prefix[____]
Prefix Sum 마스터
핵심 용어
prefix[i]
arr[0] + arr[1] + ... + arr[i]
구간 합 공식
sum(i, j) = prefix[j] - prefix[i-1]
전처리 O(n)
한 번 만들면 모든 쿼리 O(1)
정리 노트
Prefix Sum — 구간 합 O(1)
핵심 공식
- prefix[i]
- arr[0] + ... + arr[i-1] (prefix[0] = 0)
- 구간 합
- sum(i, j) = prefix[j+1] - prefix[i] → O(1)
- 전처리
- O(n) 한 번으로 모든 쿼리 O(1) 가능
응용 문제
- Range Sum Query
- 기본 Prefix Sum
- Subarray Sum = K
- Prefix Sum + 해시맵 → O(n)
면접 키워드: 'Prefix Sum으로 전처리 O(n), 쿼리 O(1)'
시각 자료
핵심 정리
- 1Prefix Sum: 누적 합 배열로 구간 합 O(1)
- 2prefix[0] = 0 더미로 경계 조건 깔끔
- 3Subarray Sum = K: prefix + 해시맵 콤보
- 4전처리 O(n), 쿼리 O(1), Q개 쿼리 → O(n + Q)
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작