최대 부분 배열과 최대 곱 부분 배열
maximum-sum-subarray에 Kadane 알고리즘을 적용하고, 곱 변형 문제를 위해 최댓값과 최솟값을 모두 추적하도록 확장합니다.
최대 부분 배열과 최대 곱 부분 배열은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
최대 합 부분 배열 문제
최대 부분 배열 문제는 1차원 숫자 배열에서 합이 가장 큰 연속 부분 배열을 찾는 문제입니다. 예를 들어 [-2, 1, -3, 4, -1, 2, 1, -5, 4]에서는 부분 배열 [4, -1, 2, 1]의 합이 6으로 가장 큽니다. 무차별 대입 O(n²) 방식은 모든 부분 배열을 확인하지만, 카데인 알고리즘은 O(n)에 문제를 해결합니다.
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
# Brute force: O(n^2)
max_sum = float('-inf')
for i in range(len(nums)):
curr = 0
for j in range(i, len(nums)):
curr += nums[j]
max_sum = max(max_sum, curr)
print(max_sum) # 6카데인 알고리즘의 직관
카데인 알고리즘은 배열을 한 번 순회하면서 누적되는 current_sum을 유지합니다. 각 원소에서 기존 부분 배열을 확장할지 또는 이 원소부터 새로 시작할지 결정합니다. current_sum이 음수가 되면 이후 어떤 부분 배열에도 손해만 되므로 다시 시작합니다. 점화식은 current_sum = max(num, current_sum + num)입니다.
def max_subarray(nums):
max_sum = current_sum = nums[0]
for num in nums[1:]:
# Extend or start fresh?
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray(nums)) # 6카데인 알고리즘 추적
[-2, 1, -3, 4, -1, 2, 1, -5, 4]에 카데인 알고리즘을 적용해 보겠습니다. 시작할 때 누적값=-2, 최댓값=-2입니다. 1에서는 누적값=max(1,-2+1)=1, 최댓값=1입니다. -3에서는 누적값=max(-3,1-3)=-2, 최댓값=1입니다. 4에서는 누적값=max(4,-2+4)=4, 최댓값=4입니다. -1에서는 누적값=3, 최댓값=4입니다. 2에서는 누적값=5, 최댓값=5입니다. 1에서는 누적값=6, 최댓값=6입니다. -5에서는 누적값=1입니다. 4에서는 누적값=5, 최댓값=6입니다. 이 알고리즘은 인덱스 6에서 끝나는 부분 배열이 최적임을 정확하게 찾아냅니다.
def max_subarray_trace(nums):
curr = max_sum = nums[0]
for i, num in enumerate(nums[1:], 1):
new_curr = max(num, curr + num)
max_sum = max(max_sum, new_curr)
print(f'i={i}, num={num}, curr: {curr}->{new_curr}, max={max_sum}')
curr = new_curr
return max_sum
max_subarray_trace([-2, 1, -3, 4, -1, 2, 1, -5, 4])실제 부분 배열 반환하기
면접관이 합만이 아니라 부분 배열 자체를 반환하라고 요청한다면 시작 인덱스와 끝 인덱스를 추적해야 합니다. 다시 시작할 때(즉, num > current_sum + num일 때) temp_start를 갱신합니다. max_sum을 갱신할 때 temp_start를 start로 저장하고 현재 인덱스를 end로 저장합니다. 이렇게 해도 동일한 O(n) 알고리즘에 O(1)의 추가 비용만 더해집니다.
def max_subarray_indices(nums):
max_sum = curr = nums[0]
start = end = temp_start = 0
for i in range(1, len(nums)):
if nums[i] > curr + nums[i]:
curr = nums[i]
temp_start = i
else:
curr += nums[i]
if curr > max_sum:
max_sum = curr
start, end = temp_start, i
return max_sum, nums[start:end+1]
print(max_subarray_indices([-2, 1, -3, 4, -1, 2, 1, -5, 4]))
# (6, [4, -1, 2, 1])최대 곱 부분 배열 문제
최대 곱 부분 배열 문제는 음수 때문에 합을 구하는 경우보다 더 까다롭습니다. 음수 두 개를 곱하면 양수가 되므로, 매우 작은 음의 곱이 다른 음수와 곱해진 뒤 최댓값이 될 수 있습니다. [2, 3, -2, 4]의 답은 6([2, 3])입니다. [-2, 0, -1]의 답은 0입니다. 각 단계에서 최댓값과 최솟값을 모두 추적해야 합니다.
nums = [2, 3, -2, 4]
# [2,3,-2,4]: products [2, 6, -12, -48]
# subarrays: [2]=2, [2,3]=6, [3]=3, etc.
# max is 6 from subarray [2,3]
nums2 = [-2, 3, -4]
# [-2]*3*[-4] = 24
# negative*negative=positive!
print('Expected:', 24)최댓값과 최솟값 곱을 함께 추적하기
핵심 통찰은 각 위치에서 현재 최댓값이 num, max_so_far * num, min_so_far * num 중 하나라는 것입니다. 마지막 항은 음수로 인해 최솟값이 최댓값으로 바뀔 때 도움이 됩니다. 최솟값도 마찬가지로 계산합니다. 같은 단계에서 이미 갱신된 값을 사용하지 않도록 이전 값을 기준으로 두 값 모두 cur_max와 cur_min을 동시에 갱신해야 합니다.
def max_product(nums):
max_prod = min_prod = result = nums[0]
for num in nums[1:]:
# All three candidates for new max
candidates = (num, max_prod * num, min_prod * num)
max_prod, min_prod = max(candidates), min(candidates)
result = max(result, max_prod)
return result
print(max_product([2, 3, -2, 4])) # 6
print(max_product([-2, 3, -4])) # 24
print(max_product([-2, 0, -1])) # 0
print(max_product([-2])) # -2최소 곱이 중요한 이유
[-3, -10, 5]를 살펴보겠습니다. -3을 처리한 후에는 최댓값=-3, 최솟값=-3입니다. -10을 처리하면 후보는 (-10, 30, 30)이므로 최댓값=30, 최솟값=-10입니다. 5를 처리하면 후보는 (5, 150, -50)이므로 최댓값=150입니다. min_prod를 추적하지 않으면 매우 작은 음의 최솟값에 다시 음수를 곱할 때 발생하는 반전을 놓치게 됩니다. 이전의 동일한 값에서 max와 min을 모두 계산해 오래된 값을 읽는 오류를 방지해야 합니다.
def max_product_traced(nums):
max_p = min_p = result = nums[0]
for num in nums[1:]:
prev_max, prev_min = max_p, min_p
max_p = max(num, prev_max * num, prev_min * num)
min_p = min(num, prev_max * num, prev_min * num)
result = max(result, max_p)
print(f'num={num}: max_p={max_p}, min_p={min_p}')
return result
max_product_traced([-3, -10, 5])
# max_p after -10: 30 (flip!)
# max_p after 5: 1500은 곱을 초기화합니다
배열의 0은 누적되는 두 곱을 모두 0으로 초기화하여 배열을 사실상 서로 독립적인 부분 배열로 나눕니다. num = 0이면 max_prod * 0 = 0과 min_prod * 0 = 0이 모두 성립하므로 세 후보가 모두 0이 되고, 이전 결과의 최댓값이 유지됩니다. 특수 처리가 필요하지 않습니다 — 일반 공식이 0을 자연스럽게 처리합니다.
def max_product(nums):
max_p = min_p = result = nums[0]
for num in nums[1:]:
cands = (num, max_p * num, min_p * num)
max_p, min_p = max(cands), min(cands)
result = max(result, max_p)
return result
# Zero splits array into independent subarrays
print(max_product([3, -1, 4, 0, 2, 5, -1])) # 10 (2*5)
print(max_product([0, 2])) # 2
print(max_product([-1, 0, -2])) # 0대안: 왼쪽-오른쪽 곱 순회
또 다른 방법은 왼쪽에서 오른쪽으로 순회한 다음 오른쪽에서 왼쪽으로 순회하면서, 0을 만나면 누적 곱을 1로 초기화하는 것입니다. 최대 곱 부분 배열은 0을 절대 가로지르지 않으므로, 한 방향에서 음수 때문에 결과가 나빠지더라도 반대 방향으로 순회하면 그 반전을 포착할 수 있습니다. 이 방법은 우아하지만, 면접에서는 최솟값/최댓값 추적 방식이 더 일반적으로 기대됩니다.
def max_product_sweep(nums):
result = max(nums)
left = right = 1
n = len(nums)
for i in range(n):
left *= nums[i]
right *= nums[n - 1 - i]
result = max(result, left, right)
if left == 0: left = 1
if right == 0: right = 1
return result
print(max_product_sweep([2, 3, -2, 4])) # 6
print(max_product_sweep([-2, 3, -4])) # 24
print(max_product_sweep([-2, 0, -1])) # 0카데인 알고리즘과 곱셈의 주요 차이점
합 부분 배열과 곱 부분 배열은 중요한 차이가 있습니다. 합에서는 음수가 항상 해로우므로 탐욕적으로 다시 시작합니다. 곱에서는 음수 두 개가 도움이 될 수 있으므로 양쪽 극단을 모두 추적해야 합니다. 또한 0은 곱에서는 종료점이지만 합에서는 약간 해로울 뿐입니다. 면접에서 설명할 때는 이러한 차이를 명확히 인정하고, 코드를 작성하기 전에 최솟값을 추적해야 하는 이유를 설명해야 합니다.
# Max Sum Subarray: O(n) time, O(1) space
def max_sum(nums):
curr = result = nums[0]
for n in nums[1:]:
curr = max(n, curr + n) # restart or extend
result = max(result, curr)
return result
# Max Product Subarray: O(n) time, O(1) space
def max_prod(nums):
lo = hi = result = nums[0]
for n in nums[1:]:
lo, hi = min(n, lo*n, hi*n), max(n, lo*n, hi*n)
result = max(result, hi)
return result
print(max_sum([-2, 1, -3, 4, -1, 2, 1])) # 6
print(max_prod([-2, 3, -4])) # 24복잡도 및 면접 팁
카데인 알고리즘(최대 합)과 최솟값/최댓값 추적 방식(최대 곱)은 모두 O(n) 시간과 O(1) 공간에 실행됩니다. 주요 면접 팁은 다음과 같습니다. (1) 최대 합 문제에서는 분할 정복 O(n log n) 대안을 언급해 폭넓은 이해를 보여 주세요. (2) 최대 곱 문제에서는 오래된 데이터를 사용하지 않도록 이전 값에서 min_prod와 max_prod를 동시에 갱신한다는 점을 강조하세요. (3) 배열이 비어 있을 수 있는지, 부분 배열이 비어 있지 않아야 하는지 항상 확인하세요. (관례상 부분 배열은 비어 있지 않아야 합니다.)
# Both run O(n) time, O(1) space
# Kadane handles: all negative (returns least negative)
# Product handles: zeros (resets naturally), negatives (tracks both extremes)
nums_all_neg = [-5, -2, -8]
print('Max sum (all neg):', max(max(nums_all_neg[0:1]),
max(x for x in nums_all_neg))) # -2
# Correct: return the maximum element when all are negative빠른 확인
이 단원에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해도를 확인해 보세요.
단원 요약
이 단원에서는 카데인 알고리즘이 각 원소에서 확장하거나 다시 시작하는 방식으로 O(n)에 최대 합 부분 배열을 해결한다는 것, 음수의 반전 때문에 최대 곱 부분 배열에서는 누적되는 최솟값과 최댓값을 모두 추적해야 한다는 것, 0은 특수 처리 코드 없이도 누적 곱을 자연스럽게 초기화한다는 것을 배웠습니다. 다음으로 1차원 DP 표를 사용하는 단어 분할 문제를 살펴봅니다.
자주 묻는 질문
“최대 부분 배열과 최대 곱 부분 배열” 강의는 무료인가요?
네 — “최대 부분 배열과 최대 곱 부분 배열” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“최대 부분 배열과 최대 곱 부분 배열”에서 뭘 배우나요?
maximum-sum-subarray에 Kadane 알고리즘을 적용하고, 곱 변형 문제를 위해 최댓값과 최솟값을 모두 추적하도록 확장합니다. 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“최대 부분 배열과 최대 곱 부분 배열” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- House Robber: 선택 또는 건너뛰기 점화식
- 최대 부분 배열과 최대 곱 부분 배열
- 단어 분할과 문자열 분할
- 경우의 수 디코딩과 경로 세기