분할 정복 템플릿
병합 정렬에서 세 단계 템플릿(분할, 정복, 결합)을 추출하고 이를 새로운 형태의 문제에 체계적으로 적용합니다.
분할 정복 템플릿은(는) CoddyKit의 무료 DSA Interview Prep 강의입니다. 이것은 4개 중 1번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 DSA Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
분할 정복이란 무엇인가
분할 정복(D&C)은 문제를 같은 유형의 독립적인 하위 문제로 나누고, 각 문제를 재귀적으로 해결한 뒤 해를 결합하여 문제를 풉니다. 핵심 단어는 독립적이라는 것입니다. 하위 문제는 서로 상태를 공유하지 않습니다(DP에서는 하위 문제가 겹치는 것과 다릅니다). 대표적인 예로 병합 정렬, 이분 탐색, 퀵 정렬, 최근접 점 쌍, 고속 행렬 곱셈이 있습니다. 분할 정복은 일반적으로 세 단계 서식을 통해 O(n log n) 시간 복잡도를 달성합니다.
# Divide and Conquer vs DP:
# D&C: sub-problems are INDEPENDENT (no overlap)
# DP: sub-problems OVERLAP (same sub-problem solved multiple times)
# D&C examples:
# Merge sort: split array in half, sort each, merge
# Binary search: check midpoint, recurse on one half
# Max subarray (D&C): find max in left half, right half, crossing
# Recurrence pattern:
# T(n) = 2T(n/2) + O(n) → O(n log n) [merge sort]
# T(n) = T(n/2) + O(1) → O(log n) [binary search]
# T(n) = T(n/k) + O(n) → O(n log_k n) [k-way split]세 단계 서식
모든 분할 정복 알고리즘은 세 단계를 따릅니다. (1) 분할 — 문제를 일반적으로 중간 지점에서 둘 이상의 더 작은 하위 문제로 나눕니다. (2) 정복 — 각 하위 문제를 재귀적으로 해결합니다. 재귀를 멈출 기저 사례를 정의합니다(대개 n ≤ 1). (3) 결합 — 하위 문제의 해를 병합하거나 결합하여 전체 해를 만듭니다. 창의성이 필요한 부분은 전적으로 결합 단계이며, 분할은 대개 중간 지점에서 나누는 것에 불과합니다.
def divide_and_conquer(arr, lo, hi):
# BASE CASE: trivial sub-problem
if lo >= hi:
return base_case_result(arr, lo, hi)
# DIVIDE: split at midpoint
mid = (lo + hi) // 2
# CONQUER: solve sub-problems recursively
left_result = divide_and_conquer(arr, lo, mid)
right_result = divide_and_conquer(arr, mid + 1, hi)
# COMBINE: merge results
return combine(left_result, right_result, arr, lo, mid, hi)
def base_case_result(arr, lo, hi): return arr[lo]
def combine(l, r, arr, lo, mid, hi): return max(l, r)대표적인 예로 보는 병합 정렬
병합 정렬은 분할 정복을 완벽하게 보여 줍니다. 배열을 중간 지점에서 분할합니다. 각 절반을 재귀적으로 정렬하여 정복합니다. 두 정렬된 절반을 O(n)에 병합하여 결합합니다. 모든 작업은 병합 단계에서 이루어집니다. 점화식은 T(n) = 2T(n/2) + O(n)입니다. 마스터 정리의 2번 경우에 따라 T(n) = O(n log n)입니다. 이는 반드시 암기해야 할 가장 중요한 분할 정복 점화식입니다.
def merge_sort(arr):
# BASE CASE
if len(arr) <= 1:
return arr
# DIVIDE
mid = len(arr) // 2
# CONQUER
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# COMBINE
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i]); i += 1
else:
result.append(right[j]); j += 1
return result + left[i:] + right[j:]
print(merge_sort([5, 3, 8, 1, 9, 2])) # [1,2,3,5,8,9]마스터 정리 빠른 참고표
마스터 정리는 T(n) = aT(n/b) + f(n) 형태의 점화식을 풉니다. 1번 경우: f(n) = O(n^(log_b(a) - ε)) → T(n) = O(n^log_b(a)). 2번 경우: f(n) = O(n^log_b(a)) → T(n) = O(n^log_b(a) × log n). 3번 경우: f(n) = Ω(n^(log_b(a) + ε)) → T(n) = O(f(n)). 병합 정렬에서는 a=2, b=2, f(n)=O(n), n^log_2(2)=n이므로 → 2번 경우 → O(n log n)입니다.
# Master Theorem quick examples:
# T(n) = 2T(n/2) + O(n) → a=2,b=2,f=n,n^log2(2)=n → Case2 → O(n log n)
# T(n) = 2T(n/2) + O(1) → a=2,b=2,f=1,n^1=n >> 1 → Case1 → O(n)
# T(n) = 2T(n/2) + O(n^2) → a=2,b=2,f=n^2,n^1 << n^2 → Case3 → O(n^2)
# T(n) = T(n/2) + O(1) → a=1,b=2,f=1,n^log2(1)=1=f → Case2 → O(log n)
# T(n) = T(n/3)+T(2n/3)+O(n) → Master doesn't apply directly → O(n log n) by recursion tree
recurrences = [
('Merge sort: 2T(n/2)+n', 'O(n log n)'),
('Binary search: T(n/2)+1', 'O(log n)'),
('Naive matrix mult: 8T(n/2)+n^2', 'O(n^3)'),
('Strassen: 7T(n/2)+n^2', 'O(n^2.81)'),
]
for r, sol in recurrences: print(r, '->', sol)최대 부분 배열: 분할 정복 접근법
최대 부분 배열에 분할 정복을 적용하면 답은 세 경우 중 하나입니다. 왼쪽 절반에 완전히 있거나, 오른쪽 절반에 완전히 있거나, 중간 지점을 가로지릅니다. 가로지르는 경우에는 중간 지점에서 왼쪽과 오른쪽으로 확장하면서 각 방향의 최대 합을 구한 다음 결합합니다. 이 O(n log n) 분할 정복 방식은 카데인 알고리즘의 O(n)보다 느리지만, 서식을 훌륭하게 보여 주며 분할 정복에 관한 면접의 단골 문제입니다.
def max_subarray_dc(nums, lo=None, hi=None):
if lo is None: lo, hi = 0, len(nums) - 1
if lo == hi: return nums[lo]
mid = (lo + hi) // 2
# Conquer
left_max = max_subarray_dc(nums, lo, mid)
right_max = max_subarray_dc(nums, mid + 1, hi)
# Cross-midpoint sum
left_sum = curr = 0
for i in range(mid, lo - 1, -1):
curr += nums[i]
left_sum = max(left_sum, curr)
right_sum = curr = 0
for i in range(mid + 1, hi + 1):
curr += nums[i]
right_sum = max(right_sum, curr)
cross_max = left_sum + right_sum
return max(left_max, right_max, cross_max)
nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray_dc(nums)) # 6거듭제곱 함수: 빠른 거듭제곱
빠른 거듭제곱 (LeetCode 50)은 분할 정복을 사용해 x^n을 O(log n)에 계산합니다. n이 짝수이면 x^n = (x^(n/2))^2입니다. n이 홀수이면 x^n = x × x^(n-1)입니다. 음의 n은 x^(-n) = 1/x^n으로 처리합니다. 각 재귀 호출에서 n이 절반으로 줄어들기 때문에 깊이는 O(log n)입니다. 결합 단계가 단순한 곱셈에 불과한, 간단하지만 효과적인 예입니다.
def my_pow(x, n):
if n < 0:
return 1 / my_pow(x, -n)
# BASE CASE
if n == 0: return 1
# DIVIDE and CONQUER
half = my_pow(x, n // 2)
if n % 2 == 0:
return half * half # even: x^n = (x^(n/2))^2
else:
return x * half * half # odd: x^n = x * (x^(n/2))^2
print(my_pow(2, 10)) # 1024
print(my_pow(2, -2)) # 0.25
print(my_pow(3, 5)) # 243
print(my_pow(0, 0)) # 1정렬된 배열에서 BST 만들기
정렬된 배열을 BST로 변환 (LeetCode 108)은 분할 정복을 사용합니다. 중간 지점을 루트로 선택하여 높이 균형을 보장하고, 왼쪽 절반에서 왼쪽 하위 트리를, 오른쪽 절반에서 오른쪽 하위 트리를 재귀적으로 만듭니다. 이렇게 하면 최소 높이가 O(log n)인 높이 균형 BST가 만들어집니다. 분할 정복 구조는 이분 탐색과 비슷합니다. 재귀의 각 수준에서 현재 하위 범위의 중간 지점을 루트로 지정합니다.
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def sorted_array_to_bst(nums):
def helper(lo, hi):
if lo > hi: return None
mid = (lo + hi) // 2
node = TreeNode(nums[mid]) # DIVIDE at midpoint
node.left = helper(lo, mid - 1) # CONQUER left
node.right = helper(mid + 1, hi) # CONQUER right
# COMBINE: already done by assignment
return node
return helper(0, len(nums) - 1)
def inorder(node):
if not node: return []
return inorder(node.left) + [node.val] + inorder(node.right)
root = sorted_array_to_bst([-10, -3, 0, 5, 9])
print(inorder(root)) # [-10,-3,0,5,9] (sorted, proving BST property)분할 정복이 최선이 아닌 경우
분할 정복에는 함수 호출 스택 깊이, 배열 슬라이싱(인덱스를 사용하지 않는 경우), 결합 단계라는 추가 비용이 있습니다. 결합 단계가 O(n) 이하일 때 최적입니다. 하위 문제가 겹치면 분할 정복은 해를 불필요하게 다시 계산하므로 DP가 필요합니다. 결합 단계가 지배적이면(예: O(n²)) 분할 정복은 단순한 접근법보다 나아지지 않습니다. 언제 선택해야 하는지 알아 두세요. 독립적인 하위 문제에는 분할 정복을, 겹치는 하위 문제에는 DP를 사용합니다.
# When D&C hurts:
# Fibonacci with pure D&C (no memo): T(n) = T(n-1) + T(n-2) → O(2^n)
# Sub-problems OVERLAP → use DP or memoisation instead
def fib_dc(n):
if n <= 1: return n
return fib_dc(n-1) + fib_dc(n-2) # O(2^n)!
def fib_dp(n):
a, b = 0, 1
for _ in range(n): a, b = b, a+b
return a # O(n)
print(fib_dp(30)) # fast
# fib_dc(40) would take seconds — do not run large values!정렬된 행렬에서 이분 탐색을 위한 분할 정복
각 행과 열이 정렬된 2차원 행렬에서 검색하는 문제(LeetCode 240)는 분할 정복으로 해결할 수 있습니다. 오른쪽 위 모서리에서 시작합니다. 현재 값이 목표보다 크면 왼쪽으로 이동하여 열을 제거합니다. 현재 값이 목표보다 작으면 아래로 이동하여 행을 제거합니다. 같으면 찾은 것입니다. 이 O(m+n) 알고리즘은 기술적으로 재귀적인 분할 정복은 아니지만, 각 단계에서 검색 공간의 절반을 제거한다는 핵심 아이디어를 공유합니다.
def search_matrix(matrix, target):
if not matrix: return False
m, n = len(matrix), len(matrix[0])
row, col = 0, n - 1 # start top-right
while row < m and col >= 0:
val = matrix[row][col]
if val == target:
return True
elif val > target:
col -= 1 # eliminate this column
else:
row += 1 # eliminate this row
return False
matrix = [
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
print(search_matrix(matrix, 5)) # True
print(search_matrix(matrix, 20)) # False재귀 트리 분석
마스터 정리에 맞지 않는 분할 정복 점화식에는 재귀 트리 방법을 사용합니다. 재귀 호출의 각 수준을 그리고 수준마다 수행하는 작업을 합산합니다. 병합 정렬에서는 k번째 수준에 크기가 n/2^k인 하위 문제가 2^k개 있습니다. 수준별 작업량 = 2^k × O(n/2^k) = O(n)입니다. 전체 수준 수 = log n입니다. 전체 작업량 = O(n log n)입니다. 이 시각적 방법은 모든 점화식에 적용할 수 있으며, 분할 정복이 일반적으로 O(n log n)에 도달하는 이유를 직관적으로 이해하게 해 줍니다.
# Merge sort recursion tree analysis:
# Level 0: 1 problem of size n → O(n) work
# Level 1: 2 problems of size n/2 → 2*O(n/2) = O(n) work
# Level 2: 4 problems of size n/4 → 4*O(n/4) = O(n) work
# ...
# Level log(n): n problems of size 1 → n*O(1) = O(n) work
# Total levels = log(n)+1
# Total work = O(n) * O(log n) = O(n log n)
import math
n = 64
levels = int(math.log2(n)) + 1
print(f'n={n}: {levels} levels, {n}*{levels} = {n*levels} work units')
print(f'O(n log n) = O({n} * {int(math.log2(n))}) = O({n*int(math.log2(n))})')면접에서 분할 정복 설명하기
면접에서 분할 정복 해법을 설명할 때는 다음과 같이 하세요. (1) 세 단계를 명시적으로 말합니다. "중간 지점에서 분할하고, 각 절반을 재귀적으로 해결한 다음, 병합하여 결합하겠습니다." (2) 기저 사례를 명확히 식별합니다. (3) 점화식을 도출합니다. T(n) = 2T(n/2) + O(n). (4) 마스터 정리나 재귀 트리를 적용하여 O(n log n)을 도출합니다. (5) 다른 방법보다 분할 정복이 더 낫거나 불리한 경우를 언급합니다(겹치는 하위 문제에는 DP, 최대 부분 배열에는 카데인 알고리즘).
# D&C interview template to memorize:
def dc_template(problem, lo, hi):
# 1. BASE CASE (state it first)
if lo == hi: return solve_base(problem, lo)
# 2. DIVIDE
mid = (lo + hi) // 2
# 3. CONQUER
left = dc_template(problem, lo, mid)
right = dc_template(problem, mid + 1, hi)
# 4. COMBINE (this is where the algorithm-specific logic goes)
return combine_results(left, right, problem, lo, mid, hi)
def solve_base(p, i): return p[i]
def combine_results(l, r, p, lo, mid, hi): return max(l, r)
print('D&C template: base-divide-conquer-combine')
print('Complexity usually: T(n)=2T(n/2)+O(n) → O(n log n)')빠른 확인
이 수업에서 다룬 자료 구조 및 알고리즘 — 코딩 면접 준비 개념에 대한 이해도를 확인하세요.
수업 요약
이 수업에서는 다음을 배웠습니다. 분할 정복은 기저 사례 → 중간 지점에서 분할 → 재귀적으로 정복 → 결합이라는 서식을 따릅니다. T(n) = 2T(n/2) + O(n)은 마스터 정리 2번 경우에 따라 O(n log n)을 제공합니다. 또한 분할 정복은 독립적인 하위 문제에 최적이며, 하위 문제가 겹칠 때는 DP가 필요합니다. 다음에는 수정된 병합 정렬을 사용해 배열의 역전 수를 세는 데 분할 정복을 적용합니다.
자주 묻는 질문
“분할 정복 템플릿” 강의는 무료인가요?
네 — “분할 정복 템플릿” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 DSA Interview Prep 강의 전체를 잠금 해제할 수 있습니다. DSA Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“분할 정복 템플릿”에서 뭘 배우나요?
병합 정렬에서 세 단계 템플릿(분할, 정복, 결합)을 추출하고 이를 새로운 형태의 문제에 체계적으로 적용합니다. 브라우저에서 직접 실행하는 실습 코드로 DSA Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
DSA Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 DSA Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 1번째 강의입니다.
“분할 정복 템플릿” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 DSA Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 DSA Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.