# [06-02] 분할 정복 (Divide & Conquer)
분할 정복은 큰 문제를 작은 문제로 나누어 해결한 후 결과를 합치는 효율적인 알고리즘 설계 기법입니다.
🎯 분할 정복 (Divide & Conquer)이란 무엇인가
분할 정복의 기본 개념
분할 정복은 문제를 더 작은 부분 문제로 나누고, 각각을 해결한 뒤, 그 결과를 합쳐서 원래 문제를 해결하는 방법입니다.
실생활 비유:
큰 빌딩 청소하기:
❌ 비효율적: 혼자서 1층부터 10층까지
✅ 분할 정복:
1. 10층을 2개 구역으로 나눔 (분할)
2. 각 구역에 사람 배치 (정복)
3. 결과 합침 (전체 청소 완료)또 다른 예시:
- 군대 조직: 대대 → 중대 → 소대로 나눠서 명령
- 회사 조직: 부서 → 팀 → 개인으로 업무 분담
- 요리: 여러 재료 따로 준비 → 마지막에 합쳐서 완성
분할 정복의 3단계
분할 정복은 항상 다음 3단계를 따릅니다:
1. 분할 (Divide)
└─ 문제를 더 작은 부분 문제로 나눔
2. 정복 (Conquer)
└─ 부분 문제를 재귀적으로 해결 (충분히 작으면 직접 해결)
3. 합치기 (Combine)
└─ 부분 문제의 해답을 합쳐 원래 문제 해결간단한 예시: 배열의 합 구하기
def array_sum(arr, start, end):
"""
배열의 합을 분할 정복으로 구하기
분할 정복의 3단계:
1. 분할: 배열을 반으로 나눔
2. 정복: 각 절반의 합을 재귀로 구함
3. 합치기: 두 결과를 더함
"""
# 기저 조건: 원소가 1개면 그 값 반환
if start == end:
return arr[start]
# 1. 분할: 중간 지점 찾기
mid = (start + end) // 2
# 2. 정복: 각 절반을 재귀로 해결
left_sum = array_sum(arr, start, mid)
right_sum = array_sum(arr, mid + 1, end)
# 3. 합치기: 두 결과를 더함
return left_sum + right_sum
arr = [1, 2, 3, 4, 5, 6, 7, 8]
print(array_sum(arr, 0, len(arr) - 1)) # 36
# 실행 과정:
# [1,2,3,4,5,6,7,8]
# ↓ 분할
# [1,2,3,4] [5,6,7,8]
# ↓ ↓
# [1,2] [3,4] [5,6] [7,8]
# ↓ ↓ ↓ ↓
# [1][2][3][4][5][6][7][8]
# ↓ 합치기
# 3 7 11 15
# ↓
# 10 26
# ↓
# 36왜 분할 정복이 효율적인가
완전 탐색 vs 분할 정복:
# 완전 탐색: 배열에서 최댓값 찾기
def find_max_brute(arr):
max_val = arr[0]
for num in arr: # n번 비교
if num > max_val:
max_val = num
return max_val
# 시간복잡도: O(n)
# 분할 정복: 배열에서 최댓값 찾기
def find_max_divide(arr, start, end):
if start == end:
return arr[start]
mid = (start + end) // 2
left_max = find_max_divide(arr, start, mid)
right_max = find_max_divide(arr, mid + 1, end)
return max(left_max, right_max)
# 시간복잡도: O(n) - 같음!위 예시에서는 시간복잡도가 같지만, 정렬 같은 문제에서는 큰 차이가 납니다:
완전 탐색 정렬 (버블 정렬): O(n²)
분할 정복 정렬 (병합 정렬): O(n log n)
n = 1,000일 때:
O(n²) = 1,000,000 연산
O(n log n) = 약 10,000 연산
→ 100배 빠름!📊 병합 정렬 (Merge Sort)
병합 정렬의 개념
병합 정렬은 분할 정복의 가장 대표적인 예시입니다.
핵심 아이디어:
1. 배열을 반으로 나눔 (Divide)
2. 각 절반을 정렬 (재귀적으로 정렬)
3. 정렬된 두 배열을 합침 (Merge) 시각화:
초기: [38, 27, 43, 3, 9, 82, 10]
분할 단계:
[38, 27, 43, 3, 9, 82, 10]
↓
[38, 27, 43, 3] [9, 82, 10]
↓ ↓
[38, 27] [43, 3] [9, 82] [10]
↓ ↓ ↓ ↓
[38] [27] [43] [3] [9] [82] [10]
합치기 단계:
[27, 38] [3, 43] [9, 82] [10]
↓ ↓
[3, 27, 38, 43] [9, 10, 82]
↓
[3, 9, 10, 27, 38, 43, 82]병합 정렬 구현
def merge_sort(arr):
"""
병합 정렬
시간복잡도: O(n log n)
공간복잡도: O(n) - 추가 배열 필요
"""
# 기저 조건: 원소가 1개 이하면 이미 정렬됨
if len(arr) <= 1:
return arr
# 1. 분할: 중간 지점
mid = len(arr) // 2
# 2. 정복: 각 절반을 재귀로 정렬
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
# 3. 합치기: 정렬된 두 배열 병합
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
# 남은 원소들 추가
result.extend(left[i:])
result.extend(right[j:])
return result
# 사용 예시
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print(sorted_arr) # [3, 9, 10, 27, 38, 43, 82]병합 과정 상세 설명
병합(merge) 함수가 어떻게 동작하는지 자세히 봅시다:
# 예시: [3, 27, 38]과 [9, 10, 82]를 병합
left = [3, 27, 38]
right = [9, 10, 82]
# 초기 상태
i = 0, j = 0
result = []
# 1단계: left[0]=3 vs right[0]=9
# 3 < 9 → 3 선택
i=0, j=0: [3]
i=1, j=0:
# 2단계: left[1]=27 vs right[0]=9
# 27 > 9 → 9 선택
i=1, j=0: [3, 9]
i=1, j=1:
# 3단계: left[1]=27 vs right[1]=10
# 27 > 10 → 10 선택
i=1, j=1: [3, 9, 10]
i=1, j=2:
# 4단계: left[1]=27 vs right[2]=82
# 27 < 82 → 27 선택
i=1, j=2: [3, 9, 10, 27]
i=2, j=2:
# 5단계: left[2]=38 vs right[2]=82
# 38 < 82 → 38 선택
i=2, j=2: [3, 9, 10, 27, 38]
i=3, j=2:
# 6단계: left 끝남, right 남음
# right[2:] = [82] 추가
result = [3, 9, 10, 27, 38, 82]병합 정렬의 시간복잡도
왜 O(n log n)인가?
높이: log n (배열을 반으로 나누는 횟수)
각 레벨에서 비교: n (모든 원소 1번씩)
총 시간: n × log n = O(n log n)
예: n=8
레벨 0: [8개] → 8번 비교
레벨 1: [4개] [4개] → 8번 비교
레벨 2: [2][2] [2][2] → 8번 비교
레벨 3: [1][1][1][1][1][1][1][1] → 0번 비교
총 높이: log₂(8) = 3
총 비교: 3 × 8 = 24 = 8 × log₂(8)⚡ 퀵 정렬 (Quick Sort)
퀵 정렬의 개념
퀵 정렬은 병합 정렬과 다른 방식의 분할 정복입니다.
차이점:
병합 정렬:
- 균등하게 나눔 (항상 반반)
- 합치는 게 핵심 (병합 과정에서 정렬)
퀵 정렬:
- 피벗 기준으로 나눔 (불균등할 수 있음)
- 나누는 게 핵심 (분할 과정에서 정렬)핵심 아이디어:
1. 피벗(pivot) 선택: 배열의 임의의 원소
2. 피벗보다 작은 것은 왼쪽, 큰 것은 오른쪽
3. 각 부분을 재귀로 정렬피벗은 세가지 방식 중 하나로 선택
1. 맨 앞/뒤 요소 선택 (기본)
2. 무작위 선택 (Randomized)
3. 중앙값(Median)
퀵 정렬 동작 원리
초기: [7, 2, 1, 6, 8, 5, 3, 4]
피벗: 4 (마지막 원소)
1단계: 피벗 기준 분할
작은 것(< 4): [2, 1, 3]
피벗(= 4): [4]
큰 것(> 4): [7, 6, 8, 5]
2단계: 각 부분 재귀
[2, 1, 3] 정렬 → [1, 2, 3]
[7, 6, 8, 5] 정렬 → [5, 6, 7, 8]
3단계: 합치기
[1, 2, 3] + [4] + [5, 6, 7, 8]
= [1, 2, 3, 4, 5, 6, 7, 8]퀵 정렬 구현
방법 1: 이해하기 쉬운 버전
def quick_sort_simple(arr):
"""
퀵 정렬 - 간단 버전
장점: 이해하기 쉬움
단점: 추가 메모리 사용
"""
# 기저 조건
if len(arr) <= 1:
return arr
# 1. 피벗 선택 (여기서는 마지막 원소)
pivot = arr[-1]
# 2. 분할: 피벗 기준으로 나누기
left = [x for x in arr[:-1] if x <= pivot] # 작거나 같은 것
right = [x for x in arr[:-1] if x > pivot] # 큰 것
# 3. 재귀로 정렬 + 합치기
return quick_sort_simple(left) + [pivot] + quick_sort_simple(right)
# 사용 예시
arr = [7, 2, 1, 6, 8, 5, 3, 4]
print(quick_sort_simple(arr))
# [1, 2, 3, 4, 5, 6, 7, 8]방법 2: 제자리(In-place) 정렬
def quick_sort(arr, low, high):
"""
퀵 정렬 - 제자리 정렬 버전
장점: 추가 메모리 O(1)
단점: 구현이 복잡
arr: 정렬할 배열
low: 시작 인덱스
high: 끝 인덱스
"""
if low < high:
# 1. 분할: 피벗 위치 찾기
pivot_index = partition(arr, low, high)
# 2. 재귀: 피벗 기준 양쪽 정렬
quick_sort(arr, low, pivot_index - 1) # 왼쪽
quick_sort(arr, pivot_index + 1, high) # 오른쪽
def partition(arr, low, high):
"""
배열을 피벗 기준으로 분할
반환: 피벗의 최종 위치
핵심 아이디어:
- 피벗보다 작은 것들을 왼쪽으로 이동
- 피벗보다 큰 것들을 오른쪽으로 이동
"""
# 피벗 선택 (마지막 원소)
pivot = arr[high]
i = low - 1 # i: 작은 원소들의 마지막 위치
# j: 현재 확인 중인 원소
for j in range(low, high):
if arr[j] <= pivot: # 현재 원소가 피벗보다 작거나 같으면
i += 1 # i를 증가시키고
arr[i], arr[j] = arr[j], arr[i] # arr[i]와 arr[j] 교환 (작은 원소를 왼쪽으로)
# 피벗을 중간에 배치
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
# 사용 예시
arr = [7, 2, 1, 6, 8, 5, 3, 4]
quick_sort(arr, 0, len(arr) - 1)
print(arr) # [1, 2, 3, 4, 5, 6, 7, 8]Partition 과정 상세 설명
partition 함수가 어떻게 동작하는지 단계별로 봅시다:
arr = [7, 2, 1, 6, 8, 5, 3, 4]
pivot = 4 (마지막 원소)
초기: i = -1
j=0: arr[0]=7 > 4 → 교환 안 함
[7, 2, 1, 6, 8, 5, 3, 4]
j (i=-1)
j=1: arr[1]=2 ≤ 4 → 교환!
i = 0
[2, 7, 1, 6, 8, 5, 3, 4]
i j
j=2: arr[2]=1 ≤ 4 → 교환!
i = 1
[2, 1, 7, 6, 8, 5, 3, 4]
i j
j=3: arr[3]=6 > 4 → 교환 안 함
[2, 1, 7, 6, 8, 5, 3, 4]
i j
j=4: arr[4]=8 > 4 → 교환 안 함
[2, 1, 7, 6, 8, 5, 3, 4]
i j
j=5: arr[5]=5 > 4 → 교환 안 함
[2, 1, 7, 6, 8, 5, 3, 4]
i j
j=6: arr[6]=3 ≤ 4 → 교환!
i = 2
[2, 1, 3, 6, 8, 5, 7, 4]
i j
반복 종료, 피벗(4)을 i+1 위치로:
[2, 1, 3, 4, 8, 5, 7, 6]
↑
피벗 위치 (i+1=3)
결과:
- 4 왼쪽 [2,1,3]은 모두 4 이하
- 4 오른쪽 [8,5,7,6]은 모두 4 초과퀵 정렬의 시간복잡도
최선/평균: O(n log n)
- 피벗이 중간값에 가까울 때
- 매번 균등하게 분할
최악: O(n²)
- 피벗이 최솟값이나 최댓값일 때
- 이미 정렬된 배열에서 첫/마지막을 피벗으로
예: [1, 2, 3, 4, 5]에서 항상 마지막을 피벗으로
→ 매번 1개 vs n-1개로 분할
→ n + (n-1) + ... + 1 = O(n²)
해결책: 랜덤 피벗 또는 중간값 피벗🔍 이진 탐색 (Binary Search)
이진 탐색의 개념
이진 탐색은 정렬된 배열에서 특정 값을 찾는 분할 정복 알고리즘입니다.
핵심 아이디어:
1. 중간 원소 확인
2. 찾는 값이 중간보다 작으면 왼쪽 절반 탐색
3. 찾는 값이 중간보다 크면 오른쪽 절반 탐색
4. 반복시각화:
배열: [1, 3, 5, 7, 9, 11, 13, 15, 17]
찾기: 11
1단계: 중간(9) 확인
[1, 3, 5, 7, 9, 11, 13, 15, 17]
↑
9 < 11 → 오른쪽 탐색
2단계: 오른쪽 절반의 중간(13) 확인
[11, 13, 15, 17]
↑
13 > 11 → 왼쪽 탐색
3단계: 왼쪽 절반의 중간(11) 확인
[11]
↑
찾았다!이진 탐색 구현
방법 1: 재귀
def binary_search_recursive(arr, target, left, right):
"""
이진 탐색 - 재귀 버전
arr: 정렬된 배열
target: 찾을 값
left: 탐색 범위 시작
right: 탐색 범위 끝
Returns: target의 인덱스 (없으면 -1)
"""
# 기저 조건: 범위가 유효하지 않음
if left > right:
return -1
# 1. 분할: 중간 지점
mid = (left + right) // 2
# 2. 정복: 중간값 확인
if arr[mid] == target:
return mid # 찾았다!
elif arr[mid] > target:
# 왼쪽 절반 탐색
return binary_search_recursive(arr, target, left, mid - 1)
else:
# 오른쪽 절반 탐색
return binary_search_recursive(arr, target, mid + 1, right)
# 사용 예시
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17]
target = 11
index = binary_search_recursive(arr, target, 0, len(arr) - 1)
print(f"{target}의 위치: {index}") # 5방법 2: 반복문
def binary_search_iterative(arr, target):
"""
이진 탐색 - 반복 버전
장점: 스택 오버플로우 위험 없음
"""
left = 0
right = len(arr) - 1
while left <= right:
mid = (left + right) // 2 # 중간 지점
if arr[mid] == target:
return mid # 찾았다!
elif arr[mid] > target:
right = mid - 1 # 왼쪽으로
else:
left = mid + 1 # 오른쪽으로
return -1 # 못 찾음
# 사용 예시
arr = [1, 3, 5, 7, 9, 11, 13, 15, 17]
print(binary_search_iterative(arr, 11)) # 5 (인덱스)
print(binary_search_iterative(arr, 10)) # -1 (없음)이진 탐색의 시간복잡도
O(log n)
매번 탐색 범위가 절반으로 줄어듦:
n = 16
1단계: 16개
2단계: 8개
3단계: 4개
4단계: 2개
5단계: 1개
총 단계: log₂(16) = 4
순차 탐색 vs 이진 탐색:
n = 1,000,000
순차: 최악 1,000,000번
이진: 최악 20번 (log₂(1,000,000) ≈ 20)
→ 50,000배 빠름!💡 실무 팁
분할 정복을 사용할 때
- 문제를 독립적인 부분으로 나눌 수 있을 때
- 부분 문제가 원래 문제와 같은 형태일 때
- 재귀로 자연스럽게 표현될 때
정렬 알고리즘 선택
병합 정렬:
- 안정 정렬 (같은 값의 순서 유지)
- 최악의 경우도 O(n log n) 보장
- 추가 메모리 O(n) 필요
- 외부 정렬(큰 파일)에 적합
퀵 정렬:
- 평균적으로 가장 빠름
- 제자리 정렬 (메모리 O(1))
- 최악 O(n²) 가능
- 캐시 효율적이진 탐색 주의사항
- 반드시 정렬된 배열에서만 사용
- 중간값 계산 시 오버플로우 주의:
mid = left + (right - left) // 2 - Python은
bisect모듈 제공
import bisect
arr = [1, 3, 5, 7, 9, 11]
index = bisect.bisect_left(arr, 7) # 7의 위치
print(index) # 3🎯 핵심 정리
분할 정복의 본질
- 큰 문제를 작은 문제로 나누어 해결
- 재귀적 구조
- 3단계: 분할 → 정복 → 합치기
주요 알고리즘
알고리즘 시간복잡도 공간복잡도 특징
--------------------------------------------------------
병합 정렬 O(n log n) O(n) 안정, 최악도 보장
퀵 정렬 O(n log n)* O(1)** 평균 가장 빠름
이진 탐색 O(log n) O(1) 정렬 필요
* 평균, 최악은 O(n²)
** 제자리 정렬 시시간복잡도 비교
n = 1,000일 때:
O(n²) = 1,000,000
O(n log n) = 약 10,000 (100배 빠름)
O(log n) = 약 10 (100,000배 빠름)분할 정복 vs 완전 탐색
완전 탐색: 모든 경우 확인 → O(n), O(n²), O(2^n)
분할 정복: 절반씩 줄여가며 → O(log n), O(n log n)
분할 정복이 유리한 경우:
- 정렬, 탐색
- 문제를 독립적으로 나눌 수 있을 때🔗 다음 글에서는
[06-03] 그리디 (Greedy)
- 그리디 알고리즘의 개념: 매 순간 가장 좋은 선택을 하는 전략
- 거스름돈 문제: 큰 동전부터 사용하는 그리디의 대표 예시
- 회의실 배정: 빨리 끝나는 회의부터 선택하는 최적화 기법
- 그리디가 최적해를 보장하는 조건과 증명 방법
이전 글: [06-01] 완전 탐색
다음 글: [06-03] 그리디
시리즈: P1. Computer Science 기초
AI 전문가를 꿈꾸는 도전자