[CS 기초 #15] 그리디와 분할정복: 효율적인 문제 해결의 두 가지 전략
[CS 기초 #15] 그리디와 분할정복: 효율적인 문제 해결의 두 가지 전략
빠르고 효율적인 문제 해결! 그리디와 분할정복으로 복잡한 문제를 간단하게 풉니다.
🎯 이 글을 읽고 나면
- 그리디 알고리즘의 원리와 조건을 이해합니다
- 분할정복의 3단계(분할/정복/결합)를 안다
- 그리디가 통하는 문제와 안 통하는 문제를 구분합니다
- 병합 정렬, 퀵 정렬을 분할정복으로 이해합니다
- 각 기법의 장단점과 활용 사례를 설명할 수 있습니다
📚 사전 지식
- 정렬 알고리즘: 이전 글: 정렬 참고
- 재귀 함수: 분할정복의 핵심
- 시간 복잡도: 마스터 정리 이해
💡 핵심 개념 미리보기
그리디(Greedy)는 매 순간 최선의 선택을 하는 알고리즘으로, 간단하지만 항상 최적해를 보장하진 않습니다. 분할정복(Divide and Conquer)은 문제를 반으로 나누어 해결하며, 병합/퀵 정렬, 이진 탐색이 대표적입니다. 그리디는 O(n log n), 분할정복은 대부분 O(n log n)입니다!
🎯 들어가며: 두 가지 강력한 전략
“지금 당장 최선의 선택을 하자” vs “문제를 나누어 정복하자” - 어떤 전략이 더 좋을까요?
오늘은 알고리즘 설계의 두 가지 핵심 전략인 그리디 알고리즘(Greedy Algorithm)과 분할 정복(Divide and Conquer)을 깊이 있게 알아보겠습니다. 각각의 장단점과 적용 시기를 완벽하게 마스터해봅시다!
📊 그리디 vs 분할정복 vs DP
graph TB
subgraph "알고리즘 설계 전략"
G[그리디<br/>Greedy]
DC[분할 정복<br/>Divide & Conquer]
DP[동적 계획법<br/>Dynamic Programming]
end
G --> G1[지역 최적해]
G --> G2[탐욕 선택]
G --> G3[되돌릴 수 없음]
DC --> DC1[문제 분할]
DC --> DC2[독립적 해결]
DC --> DC3[결과 병합]
DP --> DP1[중복 부분문제]
DP --> DP2[최적 부분구조]
DP --> DP3[메모이제이션]
전략 비교
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
def strategy_comparison():
"""알고리즘 설계 전략 비교"""
strategies = {
"그리디": {
"접근": "각 단계에서 지역적 최적해 선택",
"장점": "간단하고 빠름",
"단점": "항상 최적해 보장 안됨",
"시간": "대부분 O(n log n) 이하",
"예시": "활동 선택, 허프만 코딩"
},
"분할정복": {
"접근": "문제를 작은 부분으로 나누어 해결",
"장점": "병렬 처리 가능",
"단점": "재귀 오버헤드",
"시간": "보통 O(n log n)",
"예시": "병합 정렬, 퀵 정렬"
},
"동적계획법": {
"접근": "중복 부분 문제 결과 저장",
"장점": "최적해 보장",
"단점": "메모리 사용량 많음",
"시간": "보통 O(n²) 또는 O(n³)",
"예시": "배낭 문제, LCS"
}
}
print("알고리즘 설계 전략 비교:")
print("=" * 70)
for name, details in strategies.items():
print(f"\n{name}:")
for key, value in details.items():
print(f" {key}: {value}")
strategy_comparison()
💰 그리디 알고리즘
그리디 선택 속성
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def greedy_properties():
"""그리디 알고리즘이 최적해를 보장하는 조건"""
properties = {
"탐욕 선택 속성 (Greedy Choice Property)": {
"정의": "지역적 최적해가 전역적 최적해로 이어짐",
"확인방법": "귀납법으로 증명",
"예시": "활동 선택 - 가장 빨리 끝나는 활동 선택"
},
"최적 부분 구조 (Optimal Substructure)": {
"정의": "부분 문제의 최적해로 전체 최적해 구성",
"확인방법": "부분 문제 독립성 확인",
"예시": "최단 경로 - 부분 경로도 최단"
}
}
print("그리디 알고리즘 속성:")
for prop, details in properties.items():
print(f"\n{prop}:")
for key, value in details.items():
print(f" {key}: {value}")
# 그리디가 실패하는 경우
print("\n\n⚠️ 그리디가 실패하는 경우:")
print(" - 0/1 배낭 문제 (부분 선택 불가)")
print(" - 최장 경로 문제 (지역 최적 ≠ 전역 최적)")
print(" - 동전 교환 (특정 동전 조합에서 실패)")
greedy_properties()
1. 활동 선택 문제
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
def activity_selection(activities):
"""활동 선택 문제 - O(n log n)
겹치지 않는 최대 활동 수 선택
"""
# 종료 시간으로 정렬
activities.sort(key=lambda x: x[1])
selected = []
last_finish = 0
for start, finish in activities:
if start >= last_finish:
selected.append((start, finish))
last_finish = finish
return selected
def activity_selection_visualization(activities):
"""활동 선택 시각화"""
activities.sort(key=lambda x: x[1])
print("활동 목록 (시작, 종료):")
for i, (s, f) in enumerate(activities):
print(f" 활동 {i+1}: ({s}, {f})")
print("\n그리디 선택 과정:")
print("-" * 50)
selected = []
last_finish = 0
for i, (start, finish) in enumerate(activities):
if start >= last_finish:
print(f"✓ 활동 {i+1} 선택: ({start}, {finish})")
selected.append((start, finish))
last_finish = finish
else:
print(f"✗ 활동 {i+1} 제외: ({start}, {finish}) - 겹침")
print(f"\n선택된 활동 수: {len(selected)}")
# 타임라인 시각화
print("\n타임라인:")
max_time = max(f for _, f in activities)
for i, (s, f) in enumerate(activities):
line = [' '] * (max_time + 1)
for t in range(s, f):
line[t] = '█'
if (s, f) in selected:
print(f"활동 {i+1}: {''.join(line)} ✓")
else:
print(f"활동 {i+1}: {''.join(line)}")
# 테스트
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (8, 12), (2, 14), (12, 16)]
activity_selection_visualization(activities)
2. 허프만 코딩
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
import heapq
from collections import Counter
class HuffmanNode:
def __init__(self, char=None, freq=0, left=None, right=None):
self.char = char
self.freq = freq
self.left = left
self.right = right
def __lt__(self, other):
return self.freq < other.freq
def huffman_encoding(text):
"""허프만 인코딩 - O(n log n)"""
if not text:
return None, {}
# 빈도 계산
freq = Counter(text)
# 최소 힙 초기화
heap = [HuffmanNode(char, f) for char, f in freq.items()]
heapq.heapify(heap)
# 허프만 트리 구성
while len(heap) > 1:
left = heapq.heappop(heap)
right = heapq.heappop(heap)
merged = HuffmanNode(freq=left.freq + right.freq,
left=left, right=right)
heapq.heappush(heap, merged)
# 코드 생성
root = heap[0]
codes = {}
def generate_codes(node, code=""):
if node:
if node.char: # 리프 노드
codes[node.char] = code if code else "0"
else:
generate_codes(node.left, code + "0")
generate_codes(node.right, code + "1")
generate_codes(root)
# 인코딩
encoded = ''.join(codes[char] for char in text)
return encoded, codes
def huffman_compression_ratio(text):
"""허프만 압축률 계산"""
encoded, codes = huffman_encoding(text)
if not encoded:
return
# 원본 크기 (8비트 * 문자 수)
original_bits = len(text) * 8
# 압축 후 크기
compressed_bits = len(encoded)
# 압축률
ratio = (1 - compressed_bits / original_bits) * 100
print(f"텍스트: '{text}'")
print(f"문자 빈도: {Counter(text)}")
print("\n허프만 코드:")
for char, code in sorted(codes.items()):
print(f" '{char}': {code}")
print(f"\n원본: {original_bits} bits")
print(f"압축: {compressed_bits} bits")
print(f"압축률: {ratio:.1f}%")
print(f"\n인코딩 결과: {encoded[:50]}...")
# 테스트
text = "this is an example of a huffman tree"
huffman_compression_ratio(text)
3. 크루스칼 알고리즘 (MST)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
def kruskal_mst(n, edges):
"""크루스칼 MST - O(E log E)"""
# 가중치로 정렬 (그리디 선택)
edges.sort(key=lambda x: x[2])
uf = UnionFind(n)
mst = []
total_weight = 0
for u, v, weight in edges:
if uf.union(u, v):
mst.append((u, v, weight))
total_weight += weight
if len(mst) == n - 1:
break
return mst, total_weight
def visualize_kruskal(n, edges):
"""크루스칼 알고리즘 시각화"""
edges.sort(key=lambda x: x[2])
print("간선 목록 (정렬됨):")
for u, v, w in edges:
print(f" ({u}, {v}): {w}")
print("\n크루스칼 진행 과정:")
print("-" * 50)
uf = UnionFind(n)
mst = []
total = 0
for u, v, weight in edges:
if uf.union(u, v):
mst.append((u, v, weight))
total += weight
print(f"✓ 간선 ({u}, {v}): {weight} 추가 → 총 가중치: {total}")
if len(mst) == n - 1:
print("\nMST 완성!")
break
else:
print(f"✗ 간선 ({u}, {v}): {weight} 제외 (사이클 형성)")
return mst, total
# 테스트
edges = [
(0, 1, 4), (0, 7, 8), (1, 2, 8), (1, 7, 11),
(2, 3, 7), (2, 5, 4), (2, 8, 2), (3, 4, 9),
(3, 5, 14), (4, 5, 10), (5, 6, 2), (6, 7, 1),
(6, 8, 6), (7, 8, 7)
]
mst, weight = visualize_kruskal(9, edges)
print(f"\n최종 MST 가중치: {weight}")
4. 다익스트라 알고리즘
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
import heapq
def dijkstra_greedy(graph, start):
"""다익스트라 최단 경로 - O((V + E) log V)
그리디: 매번 최단 거리 정점 선택
"""
n = len(graph)
dist = [float('inf')] * n
dist[start] = 0
visited = [False] * n
# (거리, 정점)
pq = [(0, start)]
while pq:
d, u = heapq.heappop(pq)
if visited[u]:
continue
visited[u] = True
for v, weight in graph[u]:
if not visited[v] and dist[u] + weight < dist[v]:
dist[v] = dist[u] + weight
heapq.heappush(pq, (dist[v], v))
return dist
def dijkstra_step_by_step(graph, start):
"""다익스트라 단계별 실행"""
n = len(graph)
dist = [float('inf')] * n
dist[start] = 0
visited = [False] * n
print(f"시작 정점: {start}")
print("초기 거리:", dist)
print("\n진행 과정:")
print("-" * 50)
pq = [(0, start)]
step = 0
while pq:
d, u = heapq.heappop(pq)
if visited[u]:
continue
step += 1
visited[u] = True
print(f"\n단계 {step}: 정점 {u} 선택 (거리: {d})")
updated = []
for v, weight in graph[u]:
if not visited[v]:
new_dist = dist[u] + weight
if new_dist < dist[v]:
dist[v] = new_dist
heapq.heappush(pq, (dist[v], v))
updated.append(f"{v}({new_dist})")
if updated:
print(f" 갱신: {', '.join(updated)}")
print(f" 현재 거리: {dist}")
return dist
# 테스트
graph = [
[(1, 4), (7, 8)], # 0
[(0, 4), (2, 8), (7, 11)], # 1
[(1, 8), (3, 7), (5, 4), (8, 2)], # 2
[(2, 7), (4, 9), (5, 14)], # 3
[(3, 9), (5, 10)], # 4
[(2, 4), (3, 14), (4, 10), (6, 2)], # 5
[(5, 2), (7, 1), (8, 6)], # 6
[(0, 8), (1, 11), (6, 1), (8, 7)], # 7
[(2, 2), (6, 6), (7, 7)] # 8
]
distances = dijkstra_step_by_step(graph, 0)
print(f"\n최종 최단 거리: {distances}")
5. 부분 배낭 문제
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
def fractional_knapsack(items, capacity):
"""부분 배낭 문제 - O(n log n)
그리디: 가치/무게 비율이 높은 순서로 선택
"""
# (가치/무게, 무게, 가치) 순으로 정렬
items.sort(key=lambda x: x[1]/x[0], reverse=True)
total_value = 0
selected = []
for weight, value in items:
if capacity >= weight:
# 전체 선택
total_value += value
selected.append((weight, value, 1.0))
capacity -= weight
elif capacity > 0:
# 부분 선택
fraction = capacity / weight
total_value += value * fraction
selected.append((weight, value, fraction))
capacity = 0
break
return total_value, selected
def compare_knapsack_approaches():
"""0/1 배낭 vs 부분 배낭 비교"""
items = [(10, 60), (20, 100), (30, 120)]
capacity = 50
print("물건 목록 (무게, 가치):")
for i, (w, v) in enumerate(items):
print(f" 물건 {i+1}: {w}kg, ${v} (비율: ${v/w:.1f}/kg)")
print(f"배낭 용량: {capacity}kg")
# 부분 배낭 (그리디)
print("\n부분 배낭 (그리디):")
frac_value, frac_selected = fractional_knapsack(items.copy(), capacity)
for w, v, f in frac_selected:
if f == 1.0:
print(f" 물건 {w}kg 전체 선택: ${v}")
else:
print(f" 물건 {w}kg의 {f*100:.0f}% 선택: ${v*f:.0f}")
print(f" 총 가치: ${frac_value:.0f}")
# 0/1 배낭은 다른 접근 필요 (DP)
print("\n0/1 배낭은 그리디로 최적해 보장 안됨!")
print("(DP 사용 필요)")
compare_knapsack_approaches()
🔨 분할 정복
분할 정복 패러다임
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
def divide_conquer_paradigm():
"""분할 정복 3단계"""
steps = {
"1. Divide (분할)": {
"설명": "문제를 더 작은 부분 문제로 분할",
"예시": "배열을 반으로 나누기",
"시간": "보통 O(1) 또는 O(n)"
},
"2. Conquer (정복)": {
"설명": "부분 문제를 재귀적으로 해결",
"예시": "각 부분 배열을 정렬",
"시간": "T(n/2) × 부분 문제 수"
},
"3. Combine (결합)": {
"설명": "부분 해를 합쳐 전체 해 구성",
"예시": "정렬된 배열들을 병합",
"시간": "보통 O(n)"
}
}
print("분할 정복 패러다임:")
print("=" * 50)
for step, details in steps.items():
print(f"\n{step}:")
for key, value in details.items():
print(f" {key}: {value}")
# 마스터 정리
print("\n\n마스터 정리 (Master Theorem):")
print("T(n) = aT(n/b) + f(n)")
print(" • a: 부분 문제 개수")
print(" • b: 분할 크기")
print(" • f(n): 분할/결합 비용")
divide_conquer_paradigm()
1. 병합 정렬 (Merge Sort)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
def merge_sort(arr):
"""병합 정렬 - O(n log n)"""
if len(arr) <= 1:
return arr
# Divide
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
# Conquer
left_sorted = merge_sort(left)
right_sorted = merge_sort(right)
# Combine
return merge(left_sorted, right_sorted)
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
def merge_sort_visualization(arr, depth=0):
"""병합 정렬 시각화"""
indent = " " * depth
if len(arr) <= 1:
print(f"{indent}Base case: {arr}")
return arr
print(f"{indent}Divide: {arr}")
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
print(f"{indent} Left: {left}")
print(f"{indent} Right: {right}")
left_sorted = merge_sort_visualization(left, depth + 1)
right_sorted = merge_sort_visualization(right, depth + 1)
merged = merge(left_sorted, right_sorted)
print(f"{indent}Combine: {merged}")
return merged
# 테스트
arr = [38, 27, 43, 3, 9, 82, 10]
print("병합 정렬 과정:")
print("=" * 50)
sorted_arr = merge_sort_visualization(arr)
print(f"\n최종 결과: {sorted_arr}")
2. 퀵 정렬 (Quick Sort)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
def quick_sort(arr, low=0, high=None):
"""퀵 정렬 - 평균 O(n log n), 최악 O(n²)"""
if high is None:
high = len(arr) - 1
if low < high:
# Divide: 분할
pivot_idx = partition(arr, low, high)
# Conquer: 재귀 정렬
quick_sort(arr, low, pivot_idx - 1)
quick_sort(arr, pivot_idx + 1, high)
return arr
def partition(arr, low, high):
"""분할 함수"""
pivot = arr[high]
i = low - 1
for j in range(low, high):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
def quick_sort_with_stats(arr):
"""퀵 정렬 통계"""
comparisons = 0
swaps = 0
def partition_with_stats(arr, low, high):
nonlocal comparisons, swaps
pivot = arr[high]
i = low - 1
for j in range(low, high):
comparisons += 1
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
swaps += 1
arr[i + 1], arr[high] = arr[high], arr[i + 1]
swaps += 1
return i + 1
def quick_sort_helper(arr, low, high):
if low < high:
pivot_idx = partition_with_stats(arr, low, high)
quick_sort_helper(arr, low, pivot_idx - 1)
quick_sort_helper(arr, pivot_idx + 1, high)
arr_copy = arr.copy()
quick_sort_helper(arr_copy, 0, len(arr_copy) - 1)
print(f"원본: {arr}")
print(f"정렬: {arr_copy}")
print(f"비교 횟수: {comparisons}")
print(f"교환 횟수: {swaps}")
return arr_copy
# 테스트
arr = [10, 7, 8, 9, 1, 5]
quick_sort_with_stats(arr)
3. 최대 부분 배열 (Maximum Subarray)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
def max_subarray_divide_conquer(arr, low, high):
"""최대 부분 배열 - O(n log n)"""
if low == high:
return low, high, arr[low]
mid = (low + high) // 2
# 왼쪽 부분의 최대
left_low, left_high, left_sum = max_subarray_divide_conquer(arr, low, mid)
# 오른쪽 부분의 최대
right_low, right_high, right_sum = max_subarray_divide_conquer(arr, mid + 1, high)
# 중간을 걸치는 최대
cross_low, cross_high, cross_sum = max_crossing_subarray(arr, low, mid, high)
# 최댓값 선택
if left_sum >= right_sum and left_sum >= cross_sum:
return left_low, left_high, left_sum
elif right_sum >= left_sum and right_sum >= cross_sum:
return right_low, right_high, right_sum
else:
return cross_low, cross_high, cross_sum
def max_crossing_subarray(arr, low, mid, high):
"""중간을 걸치는 최대 부분 배열"""
# 왼쪽 최대
left_sum = float('-inf')
sum_val = 0
max_left = mid
for i in range(mid, low - 1, -1):
sum_val += arr[i]
if sum_val > left_sum:
left_sum = sum_val
max_left = i
# 오른쪽 최대
right_sum = float('-inf')
sum_val = 0
max_right = mid + 1
for j in range(mid + 1, high + 1):
sum_val += arr[j]
if sum_val > right_sum:
right_sum = sum_val
max_right = j
return max_left, max_right, left_sum + right_sum
# 테스트
arr = [-2, -3, 4, -1, -2, 1, 5, -3]
low, high, max_sum = max_subarray_divide_conquer(arr, 0, len(arr) - 1)
print(f"배열: {arr}")
print(f"최대 부분 배열: {arr[low:high+1]}")
print(f"합: {max_sum}")
4. 거듭제곱 (Fast Exponentiation)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
def power_naive(x, n):
"""단순 거듭제곱 - O(n)"""
result = 1
for _ in range(n):
result *= x
return result
def power_divide_conquer(x, n):
"""분할 정복 거듭제곱 - O(log n)"""
if n == 0:
return 1
if n < 0:
return 1 / power_divide_conquer(x, -n)
if n % 2 == 0:
half = power_divide_conquer(x, n // 2)
return half * half
else:
return x * power_divide_conquer(x, n - 1)
def power_iterative(x, n):
"""반복적 거듭제곱 - O(log n)"""
if n < 0:
x = 1 / x
n = -n
result = 1
current_product = x
while n > 0:
if n % 2 == 1:
result *= current_product
current_product *= current_product
n //= 2
return result
def power_comparison(x, n):
"""거듭제곱 방법 비교"""
import time
# 작은 n에서는 모두 테스트
if n <= 100000:
start = time.perf_counter()
result1 = power_naive(x, n)
time1 = time.perf_counter() - start
else:
time1 = float('inf')
result1 = "너무 큼"
start = time.perf_counter()
result2 = power_divide_conquer(x, n)
time2 = time.perf_counter() - start
start = time.perf_counter()
result3 = power_iterative(x, n)
time3 = time.perf_counter() - start
print(f"{x}^{n} 계산:")
print(f" 단순: {time1:.9f}초")
print(f" 분할정복: {time2:.9f}초")
print(f" 반복: {time3:.9f}초")
if time1 != float('inf'):
print(f" 속도 향상: {time1/time2:.0f}배")
# 테스트
power_comparison(2, 1000)
5. Strassen 행렬 곱셈
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
import numpy as np
def matrix_multiply_naive(A, B):
"""단순 행렬 곱셈 - O(n³)"""
n = len(A)
C = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
for k in range(n):
C[i][j] += A[i][k] * B[k][j]
return C
def strassen_multiply(A, B):
"""Strassen 행렬 곱셈 - O(n^2.807)"""
n = len(A)
# Base case
if n == 1:
return [[A[0][0] * B[0][0]]]
# 행렬 분할
mid = n // 2
A11 = [A[i][:mid] for i in range(mid)]
A12 = [A[i][mid:] for i in range(mid)]
A21 = [A[i][:mid] for i in range(mid, n)]
A22 = [A[i][mid:] for i in range(mid, n)]
B11 = [B[i][:mid] for i in range(mid)]
B12 = [B[i][mid:] for i in range(mid)]
B21 = [B[i][:mid] for i in range(mid, n)]
B22 = [B[i][mid:] for i in range(mid, n)]
# Strassen의 7개 곱셈
M1 = strassen_multiply(add_matrix(A11, A22), add_matrix(B11, B22))
M2 = strassen_multiply(add_matrix(A21, A22), B11)
M3 = strassen_multiply(A11, sub_matrix(B12, B22))
M4 = strassen_multiply(A22, sub_matrix(B21, B11))
M5 = strassen_multiply(add_matrix(A11, A12), B22)
M6 = strassen_multiply(sub_matrix(A21, A11), add_matrix(B11, B12))
M7 = strassen_multiply(sub_matrix(A12, A22), add_matrix(B21, B22))
# 결과 계산
C11 = add_matrix(sub_matrix(add_matrix(M1, M4), M5), M7)
C12 = add_matrix(M3, M5)
C21 = add_matrix(M2, M4)
C22 = add_matrix(sub_matrix(add_matrix(M1, M3), M2), M6)
# 결과 병합
C = []
for i in range(mid):
C.append(C11[i] + C12[i])
for i in range(mid):
C.append(C21[i] + C22[i])
return C
def add_matrix(A, B):
"""행렬 덧셈"""
n = len(A)
return [[A[i][j] + B[i][j] for j in range(n)] for i in range(n)]
def sub_matrix(A, B):
"""행렬 뺄셈"""
n = len(A)
return [[A[i][j] - B[i][j] for j in range(n)] for i in range(n)]
# 간단한 테스트
A = [[1, 2], [3, 4]]
B = [[5, 6], [7, 8]]
print("A =", A)
print("B =", B)
print("A × B =", matrix_multiply_naive(A, B))
🔄 그리디 vs 분할정복 실전 비교
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
def compare_strategies():
"""문제별 최적 전략 선택"""
problems = {
"동전 교환": {
"그리디": "특정 동전 조합에서만 최적",
"DP": "항상 최적해 보장",
"분할정복": "적용 어려움"
},
"정렬": {
"그리디": "선택 정렬 (비효율적)",
"DP": "적용 어려움",
"분할정복": "병합/퀵 정렬 (효율적)"
},
"최단 경로": {
"그리디": "다익스트라 (양수 가중치)",
"DP": "벨만-포드 (음수 가중치)",
"분할정복": "적용 어려움"
},
"배낭 문제": {
"그리디": "부분 배낭만 최적",
"DP": "0/1 배낭 최적",
"분할정복": "적용 어려움"
},
"행렬 곱셈": {
"그리디": "적용 불가",
"DP": "연쇄 행렬 곱셈",
"분할정복": "Strassen 알고리즘"
}
}
print("문제별 전략 비교:")
print("=" * 70)
for problem, strategies in problems.items():
print(f"\n{problem}:")
for strategy, solution in strategies.items():
print(f" {strategy:10}: {solution}")
compare_strategies()
🎯 핵심 정리
꼭 기억해야 할 5가지
- 그리디: 지역 최적해 → 전역 최적해 (증명 필요)
- 분할정복: 독립적 부분 문제로 분할
- 그리디 조건: 탐욕 선택 속성 + 최적 부분 구조
- 마스터 정리: T(n) = aT(n/b) + f(n)
- 선택 기준: 문제 특성에 따라 적절한 전략 선택
알고리즘 선택 가이드
- 그리디 사용: 탐욕 선택이 최적해 보장할 때
- 분할정복 사용: 독립적 부분 문제로 나눌 수 있을 때
- DP 사용: 중복 부분 문제가 있을 때
- 하이브리드: 여러 전략 조합 가능
📚 추가 학습 자료
추천 문제
- LeetCode: Jump Game, Partition Labels, Majority Element
- 프로그래머스: 체육복, 조이스틱, 큰 수 만들기
- 백준: 11047(동전 0), 1931(회의실 배정), 2630(색종이 만들기)
🚀 다음 시간 예고
다음 포스트에서는 실무 응용편을 시작합니다! 데이터베이스 이론을 다루며 SQL, 정규화, 인덱싱, 트랜잭션 등을 알아보겠습니다!
📌 시리즈 네비게이션
이 기사는 저작권자의 CC BY 4.0 라이센스를 따릅니다.