DSA Interview Prep · 강의

누적 합과 누적 합계

Q: “누적 합과 누적 합계” 강의는 무료인가요?

네 — “누적 합과 누적 합계” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

Q: DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?

사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.

Q: “누적 합과 누적 합계” 강의는 얼마나 걸리나요?

대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.

Q: 이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?

네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.

O(1) 시간에 구간 합 질의에 답할 수 있도록 누적 합 배열을 만들고, 최대 합 부분 배열 같은 부분 배열 문제에 적용합니다.

누적 합과 누적 합계은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.

구간 합 문제

배열 nums가 주어졌을 때, 다음과 같은 질의를 여러 번 처리해야 합니다: 인덱스 i부터 인덱스 j까지 요소의 합은 얼마인가요? 각 질의를 단순하게 계산하면 O(n) 시간이 걸리므로, k개의 질의에는 O(n×k)이 필요합니다. 누적 합 배열을 사용하면 O(n) 시간에 누적 합계를 미리 계산한 뒤 각 질의에 O(1) 시간으로 답할 수 있습니다. 이는 면접에서 가장 널리 사용되는 사전 계산 기법 중 하나입니다.

# Naive: O(n) per query
def range_sum_naive(nums, i, j):
    return sum(nums[i:j+1])

nums = [1, 3, 5, 7, 9]
print(range_sum_naive(nums, 1, 3))  # 3+5+7 = 15
print(range_sum_naive(nums, 0, 4))  # 1+3+5+7+9 = 25
# For 1000 queries, this takes 5000 operations

누적 합 배열 만들기

prefix[i]를 nums[0]부터 nums[i-1]까지의 합으로 정의합니다(슬롯을 하나 더 두고 0부터 시작하는 인덱스에 1만큼 오프셋을 적용하면 경계 사례를 더 깔끔하게 처리할 수 있습니다). 한 번의 순회로 O(n)에 구축할 수 있습니다: prefix[i] = prefix[i-1] + nums[i-1]. 그러면 구간 질의 sum(i, j)는 prefix[j+1] - prefix[i]가 되어, O(1)이 걸리는 한 번의 뺄셈으로 처리할 수 있습니다.

def build_prefix(nums):
    n = len(nums)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + nums[i]
    return prefix

def range_sum(prefix, i, j):
    return prefix[j+1] - prefix[i]  # O(1)

nums = [1, 3, 5, 7, 9]
pre = build_prefix(nums)
print(pre)                    # [0, 1, 4, 9, 16, 25]
print(range_sum(pre, 1, 3))  # 9 - 1 = 8? Wait: 3+5+7=15
# Hmm: prefix[4]-prefix[1] = 16-1 = 15  correct
print(range_sum(pre, 1, 3))  # 15

합이 K인 부분 배열

합이 k와 같은 부분 배열의 개수를 찾는 문제는 해시 맵과 누적 합을 함께 사용하는 고전적인 문제입니다. 핵심 통찰은 i부터 j까지의 부분 배열 합이 prefix[j] - prefix[i-1]와 같다는 것입니다. 이 값이 k가 되기를 원한다면 prefix[i-1] = prefix[j] - k가 됩니다. 왼쪽에서 오른쪽으로 순회하면서 누적 합을 유지하고, current_sum - k가 이전에 몇 번 등장했는지 조회하면 전체 O(n) 시간에 모든 유효한 부분 배열을 셀 수 있습니다.

from collections import defaultdict

def subarray_sum_k(nums, k):
    count = 0
    current = 0
    freq = defaultdict(int)
    freq[0] = 1  # empty prefix
    for n in nums:
        current += n
        count += freq[current - k]  # how many prior sums give diff=k
        freq[current] += 1
    return count

print(subarray_sum_k([1, 1, 1], 2))    # 2
print(subarray_sum_k([1, 2, 3], 3))    # 2  ([1,2] and [3])

누적 합을 이용한 최대 부분 배열 합

최대 부분 배열 합은 누적 합 문제로 표현할 수 있습니다. 각 인덱스 j에 대해 모든 i < j 중 prefix[j] - prefix[i]를 최대로 만들어야 합니다. 각 j에서 최적인 i는 지금까지 본 누적 합 중 최솟값에 해당합니다. 왼쪽에서 오른쪽으로 순회하면서 min_prefix를 추적하면 O(n) 시간이 걸립니다. 이는 누적 합의 관점에서 바라본 카다네 알고리즘과 같습니다.

def max_subarray_prefix(nums):
    max_sum  = float('-inf')
    min_pre  = 0  # prefix[0] = 0
    current  = 0
    for n in nums:
        current += n
        max_sum = max(max_sum, current - min_pre)
        min_pre = min(min_pre, current)
    return max_sum

print(max_subarray_prefix([-2,1,-3,4,-1,2,1,-5,4]))
# 6  (same as Kadane's)
print(max_subarray_prefix([-1,-2,-3]))
# -1

격자 질의를 위한 2차원 누적 합

누적 합은 2차원 격자로도 확장할 수 있습니다. P[i][j]를 (0,0)부터 (i-1,j-1)까지의 직사각형에 있는 모든 요소의 합으로 정의합니다. 포함-배제 공식으로 구축합니다: P[i][j] = P[i-1][j] + P[i][j-1] - P[i-1][j-1] + grid[i-1][j-1]. 그러면 (r1,c1)부터 (r2,c2)까지의 모든 직사각형 합 질의를 네 번의 조회로 O(1)에 처리할 수 있습니다.

def build_2d_prefix(grid):
    R, C = len(grid), len(grid[0])
    P = [[0]*(C+1) for _ in range(R+1)]
    for r in range(1, R+1):
        for c in range(1, C+1):
            P[r][c] = (P[r-1][c] + P[r][c-1]
                       - P[r-1][c-1] + grid[r-1][c-1])
    return P

def rect_sum(P, r1, c1, r2, c2):
    return P[r2+1][c2+1] - P[r1][c2+1] - P[r2+1][c1] + P[r1][c1]

grid = [[3,0,1,4],[5,6,3,2],[1,2,0,1]]
P = build_2d_prefix(grid)
print(rect_sum(P, 0, 0, 1, 1))  # 3+0+5+6 = 14

평형 인덱스를 위한 누적 합

평형 인덱스는 왼쪽 요소의 합과 오른쪽 요소의 합이 같은 위치입니다. 먼저 전체 합을 계산한 다음, 왼쪽의 누적 합을 유지하면서 순회합니다. 오른쪽 합은 total - left_sum - nums[i]입니다. 각 인덱스에서 O(1)에 같은지 확인할 수 있으므로 전체 시간 복잡도는 O(n)입니다. 이는 누적 합 배열 두 개를 따로 사용하는 대신 누적 합 하나로 처리하는 방법을 보여 줍니다.

def find_pivot_index(nums):
    total = sum(nums)
    left_sum = 0
    for i, n in enumerate(nums):
        # right_sum = total - left_sum - nums[i]
        if left_sum == total - left_sum - n:
            return i
        left_sum += n
    return -1

print(find_pivot_index([1, 7, 3, 6, 5, 6]))  # 3
print(find_pivot_index([1, 2, 3]))             # -1

자기 자신을 제외한 곱 배열

배열이 주어졌을 때, 각 요소에 자기 자신을 제외한 모든 요소의 곱을 담은 배열을 반환합니다. 나눗셈은 사용할 수 없습니다. 앞쪽 누적 곱과 뒤쪽 누적 곱을 사용합니다: result[i] = (i보다 앞에 있는 모든 요소의 곱) × (i보다 뒤에 있는 모든 요소의 곱). 왼쪽에서 오른쪽으로 순회하면서 앞쪽 누적 곱을 만든 다음, 누적 변수를 사용해 오른쪽에서 왼쪽으로 순회하면서 뒤쪽 누적 곱을 곱합니다. 뒤쪽 곱을 위한 추가 배열은 필요하지 않습니다.

def product_except_self(nums):
    n = len(nums)
    result = [1] * n
    # Left pass: result[i] = product of nums[:i]
    prefix = 1
    for i in range(n):
        result[i] = prefix
        prefix *= nums[i]
    # Right pass: multiply in product of nums[i+1:]
    suffix = 1
    for i in range(n-1, -1, -1):
        result[i] *= suffix
        suffix *= nums[i]
    return result

print(product_except_self([1, 2, 3, 4]))
# [24, 12, 8, 6]   O(n) time, O(1) extra space

나머지를 이용한 누적 합

일부 문제에서는 합이 k로 나누어떨어지는 부분 배열의 개수를 묻습니다. 누적 합을 k로 나눈 나머지를 사용하면 prefix[j] % k == prefix[i] % k일 때 sum(i+1..j)가 k로 나누어떨어집니다. 순회하면서 각 나머지 값의 개수를 세는 해시 맵을 사용하면 O(n) 시간에 해결할 수 있습니다. 중요한 초기화는 freq[0] = 1이며, 이를 통해 인덱스 0에서 시작하는 부분 배열을 처리할 수 있습니다.

from collections import defaultdict

def subarray_div_by_k(nums, k):
    freq = defaultdict(int)
    freq[0] = 1
    current = 0
    count = 0
    for n in nums:
        current = (current + n) % k
        count += freq[current]
        freq[current] += 1
    return count

print(subarray_div_by_k([4, 5, 0, -2, -3, 1], 5))
# 7  (seven subarrays divisible by 5)

구간 갱신을 위한 차분 배열

차분 배열은 누적 합의 역연산입니다. 배열이 주어졌을 때 diff[i] = nums[i] - nums[i-1]를 미리 계산합니다. [l, r] 구간에 x를 더하려면 차분 배열에서 O(1) 연산 두 번만 수행하면 됩니다: diff[l] += x와 diff[r+1] -= x. 모든 갱신을 완료한 뒤 한 번의 누적 합 순회로 결과 배열을 복원합니다. 이를 통해 k번의 구간 갱신을 O(n×k)에서 O(n + k)로 줄일 수 있습니다.

def apply_range_updates(n, updates):
    # updates: list of (l, r, val)
    diff = [0] * (n + 1)
    for l, r, val in updates:
        diff[l]   += val
        diff[r+1] -= val
    # Reconstruct with prefix sum
    result = []
    running = 0
    for i in range(n):
        running += diff[i]
        result.append(running)
    return result

# Add 3 to [1,3], add 1 to [0,2]
print(apply_range_updates(5, [(1,3,3),(0,2,1)]))
# [1, 4, 4, 3, 0]

면접 문제의 누적 합

누적 합은 다양한 문제 유형에 등장합니다:

구간 질의 — 부분 배열 합, 직사각형 합
부분 배열 개수 세기 — 합이 k인 경우, k로 나누어떨어지는 경우
곱 문제 — 자기 자신을 제외한 곱
평형 — 피벗 인덱스 찾기
구간 갱신 — 차분 배열

누적 합이나 구간 기반 집계가 포함된 문제를 보면 먼저 누적 합을 떠올리세요. 누적 합은 거의 항상 단순한 O(n²) 완전 탐색을 O(n) 해법으로 바꾸어 줍니다.

# Template: prefix sum + hash map for subarray problems
from collections import defaultdict

def subarray_count_template(nums, target):
    """
    Count subarrays with property involving prefix sums.
    Adapt 'target' and lookup condition for each problem.
    """
    freq = defaultdict(int)
    freq[0] = 1          # empty prefix at sum=0
    current = 0
    count = 0
    for n in nums:
        current += n
        count += freq[current - target]  # adjust per problem
        freq[current] += 1
    return count

print(subarray_count_template([1,2,3,2,1], 3))  # 3

누적 합과 누적 최댓값

누적 합 외에도 많은 문제에서는 변수 하나로 누적 최댓값이나 누적 최솟값을 유지합니다. 주식을 사고팔기 가장 좋은 시점 문제에서는 가격의 누적 최솟값을 사용하고, 왼쪽에서 빗물을 받는 문제에서는 왼쪽 높이의 누적 최댓값을 사용합니다. 이러한 패턴은 한 번의 순회와 O(1)의 추가 공간만 필요하므로 시간과 공간 효율 모두에서 가장 우수한 기준이 됩니다.

def max_profit(prices):
    # Running minimum buy price
    min_price = float('inf')
    max_prof  = 0
    for price in prices:
        if price < min_price:
            min_price = price
        elif price - min_price > max_prof:
            max_prof = price - min_price
    return max_prof

def left_max_array(heights):
    # Running max from left for trapping rain water
    n = len(heights)
    left_max = [0] * n
    left_max[0] = heights[0]
    for i in range(1, n):
        left_max[i] = max(left_max[i-1], heights[i])
    return left_max

print(max_profit([7,1,5,3,6,4]))  # 5

빠른 확인

이 레슨에서 배운 자료 구조 및 알고리즘 & 코딩 면접 준비 개념을 제대로 이해했는지 확인해 보세요.

학습 내용 요약

이 레슨에서는 다음을 배웠습니다: 누적 합은 한 번의 O(n) 순회로 누적 합을 미리 계산하여 O(n)의 구간 질의를 O(1)의 조회로 바꿉니다. 또한 누적 합과 해시 맵을 결합하면 특정 합을 가지거나 특정 나머지 조건을 만족하는 부분 배열의 개수를 O(n)에 셀 수 있습니다. 그리고 차분 배열은 그 역연산으로, O(1)에 구간을 갱신하고 마지막에 한 번의 누적 합 복원 순회로 결과를 만들 수 있습니다. 다음에는 양 끝에서 시작하는 포인터를 사용해 투 포인터 기법을 살펴봅니다.

자주 묻는 질문