Technical Interview Master Plan [9] - Prefix Sum을 알아도 왜 구간 합 문제에서 자꾸 막히는가
Prefix Sum 알고리즘 전략에 대해 배워봅니다.
Prefix Sum
Prefix Sum이란?
Prefix Sum은 배열의 각 위치까지의 누적 합을 미리 계산해 두는 기법이다.
즉, 어떤 인덱스까지의 합을 반복해서 빠르게 구하고 싶을 때 사용한다.
예를 들어 하루 지출이 다음과 같다고 하자.
spendings = [10, 15, 20, 10, 5]이때 각 날짜까지의 누적 합은 다음과 같다.
prefix_sums = [10, 25, 45, 55, 60]의미는 다음과 같다.
prefix_sums[0] = 10
prefix_sums[1] = 10 + 15 = 25
prefix_sums[2] = 10 + 15 + 20 = 45
prefix_sums[3] = 55
prefix_sums[4] = 60즉, prefix_sums[i] 는 0번 인덱스부터 i번 인덱스까지의 합이다.
어떻게 만드는가?
현재 원소를 바로 이전까지의 누적 합에 더하면 된다.
첫 번째 값은 그대로 넣고
그 다음부터는
현재 누적합 = 이전 누적합 + 현재 원소
예시
시작:
10다음:
10 + 15 = 25다음:
25 + 20 = 45다음:
45 + 10 = 55다음:
55 + 5 = 60
그래서 결과는
[10, 25, 45, 55, 60]코드
def compute_prefix_sums(nums):
prefix_sum = [nums[0]]
for i in range(1, len(nums)):
prefix_sum.append(prefix_sum[-1] + nums[i])
return prefix_sum시간복잡도 / 공간복잡도
시간복잡도:
O(n)공간복잡도:
O(n)
배열을 한 번만 순회하면서 새 누적합 배열을 만들기 때문이다.
왜 중요한가?
Prefix Sum의 핵심 장점은 구간 합을 빠르게 구할 수 있다는 점이다.
예를 들어 left 부터 right 까지의 합은 다음처럼 구한다.
left == 0이면prefix[right]아니면
prefix[right] - prefix[left - 1]
즉, 한 번 누적합 배열을 만들어 두면
부분 배열의 합(subarray sum) 을 매우 빠르게 계산할 수 있다.
실생활 시나리오
누적합은 금융 데이터처럼 기간 합계를 자주 구해야 하는 상황에서 매우 유용하다.
예를 들어, 한 회사의 매출이 일별로 기록되어 있을 때,
5일차부터 20일차까지의 총매출을 빠르게 구하고 싶다면
매번 다시 더하지 말고 prefix sum을 이용하면 된다.
즉, 누적합은
일별 지출
누적 매출
월별 비용 합산
특정 기간 통계 계산
같은 문제를 빠르게 처리하게 해준다.
예제
Sum Between Range
정수 배열이 주어졌을 때, 두 인덱스 i, j 사이 구간의 합을 반환하는 함수를 구현하는 문제다.
예를 들어
nums = [3, -7, 6, 0, -2, 5]
였을 때,
sum_range(0, 3) = 3 + (-7) + 6 + 0 = 2
sum_range(2, 4) = 6 + 0 + (-2) = 4
sum_range(2, 2) = 6즉, 여러 번 구간 합을 빠르게 구하고 싶다.
Approach
우리는 sum_range(i, j) 라는 함수를 코딩해야 하며,
여기서 i 와 j 는 합을 구할 구간의 경계를 정의하는 인덱스들이다.
순진한 해법은 인덱스 i 부터 j 까지 배열 값을 반복적으로 더하는 것이며,
이 경우 sum_range 를 호출할 때마다 선형 시간이 든다.
sum_range 에 대한 어떤 호출이 일어나기 전에 입력 배열에 접근할 수 있으므로,
sum_range 의 효율성을 향상시키기 위해 어떤 전처리(preprocessing) 를 할 수 있을지 고려해야 한다.
이 문제는 부분 배열의 합(subarray sums) 을 다루므로,
prefix sums 가 이를 해결하는 데 어떻게 적용될 수 있을지 생각해 보면 도움이 될 수 있다.
아래 정수 배열과 그 prefix sums 를 보자.
nums = [ 3 -7 6 0 -2 5 ]
[ 0 1 2 3 4 5 ]
prefix_sum = [ 3 -4 2 2 0 5 ]
[ 0 1 2 3 4 5 ]
우리는 이미 prefix sum 배열이 어느 정도 유용하다는 점을 알고 있다.
인덱스 j 까지의 prefix sum 은 본질적으로 sum_range(0, j) 에 대한 답을 준다.
예를 들어, 구간 [0, 3] 의 합은 단순히 인덱스 3까지의 prefix sum 이다.
sum_range(0, 3) = prefix_sum[3]:
nums = [ 3 -7 6 0 -2 5 ]
[ 0 1 2 3 4 5 ]
↓
prefix_sum = [ 3 -4 2 2 0 5 ]
[ 0 1 2 3 4 5 ]
(3)
그러므로, i == 0 일 때는:
sum_range(0, j) = prefix_sum[j]
요청된 구간이 0에서 시작하지 않는다면 어떨까?
구간 [2, 4] 의 합을 구하고 싶다고 해보자.
[ 3 -7 6 0 -2 5 ]
[ 0 1 2 3 4 5 ]
이 값을 prefix sums 만으로 구할 방법이 있을까?
모든 prefix sum 값은 인덱스 0에서 시작하는 구간의 합이다.
그러므로 이 구간들을 어떻게 활용할 수 있을지 보자.
구간 [0, 4] 의 합을 생각해 보면,
이는 prefix_sum[4] 에 해당한다.
sum[0 : 4]
[ 3 -7 6 0 -2 5 ]
[ 0 1 2 3 4 5 ]
여기서 핵심 관찰은, 구간 [2, 4] 의 합은
위 합에서 구간 [0, 1] 의 합을 빼면 얻을 수 있다는 점이다.
이를 시각화하면 다음과 같다.
sum[0 : 4]
[ 3 -7 6 0 -2 5 ]
[ 0 1 2 3 4 5 ]
sum[0 : 1] sum[2 : 4]
구간 [0, 4] 와 [0, 1] 의 합이 모두 prefix sum 배열 안의 값이므로,
다음 식으로 구간 [2, 4] 의 합을 얻을 수 있다.
prefix_sum[4] - prefix_sum[1]
따라서, i > 0 일 때는
sum_range(i, j) = prefix_sum[j] - prefix_sum[i - 1]구현
class SumBetweenRange:
def __init__(self, nums: list[int]):
self.prefix_sum = [nums[0]]
for i in range(1, len(nums)):
self.prefix_sum.append(self.prefix_sum[-1] + nums[i])
def sum_range(self, i: int, j: int) -> int:
if i == 0:
return self.prefix_sum[j]
return self.prefix_sum[j] - self.prefix_sum[i - 1]복잡도 분석
시간 및 공간 복잡도 분석
시간 복잡도: 생성자의 시간 복잡도는 O(n) 이며, 여기서 n 은 배열의 길이를 나타낸다.
이는 길이 n 인 prefix_sum 배열을 채우기 때문이다. sum_range 의 시간 복잡도는 O(1) 이다.
공간 복잡도: 공간 복잡도는 prefix sum 배열이 차지하는 공간 때문에 O(n) 이다.Leetcode 문제 풀이 권장
K-Sum Subarrays - LeetCode 560. Subarray Sum Equals K
Product array without current element - LeetCode 238. Product of Array Except Self
[영상 해설 추후 업데이트 예정]