탐욕 알고리즘 (Greedy Algorithm)#
탐욕 알고리즘(Greedy Algorithm)은 최적화 문제를 해결하기 위한 간단하면서도 강력한 알고리즘 패러다임이다.
이 알고리즘은 ‘탐욕적’이라는 이름처럼, 각 단계에서 현재 상황에서 가장 좋아 보이는 선택(locally optimal choice)을 하는 방식으로 동작한다.
즉, 지금 당장 최적의 선택을 하면 전체적으로도 최적의 결과를 얻을 수 있을 것이라는 기대를 바탕으로 한다.
탐욕 알고리즘은 직관적이고 효율적인 알고리즘 설계 패러다임으로, 많은 최적화 문제에서 간단하면서도 강력한 해결책을 제공한다.
각 단계에서 현재 상황에서 가장 좋은 선택을 하는 방식으로 작동하며, 일부 문제에서는 전역 최적해를 보장한다.
그러나 모든 문제에 적용할 수 있는 것은 아니며, 탐욕 알고리즘이 최적해를 보장하는지 반드시 검증해야 한다.
탐욕 알고리즘이 적용 가능한 경우에는 다른 방법(동적 계획법, 백트래킹 등)보다 일반적으로 더 빠르고 메모리 사용량이 적다.
실제 문제를 해결할 때는 문제의 특성을 분석하고, 탐욕적 선택 속성과 최적 부분 구조가 있는지 확인하여 탐욕 알고리즘의 적용 가능성을 판단해야 한다. 그리고 최적해를 보장하는지 증명하거나, 적어도 반례가 없는지 확인하는 과정이 중요하다.
탐욕 알고리즘의 작동 원리#
탐욕 알고리즘은 다음과 같은 단계로 구성된다:
- 선택 절차(Selection Procedure): 현재 상태에서 가장 좋은 선택을 결정한다.
- 적절성 검사(Feasibility Check): 선택이 문제의 제약조건을 만족하는지 확인한다.
- 해답 검사(Solution Check): 지금까지의 선택들이 문제의 해답을 제공하는지 확인한다.
이러한 단계를 반복하면서 최종 해답에 도달하게 된다.
탐욕 알고리즘의 특징#
- 단순성: 구현이 간단하고 이해하기 쉽다.
- 효율성: 일반적으로 실행 시간이 빠르다.
- 지역적 최적화: 각 단계에서 최적의 선택을 한다.
- 일회성 결정: 한번 선택한 것은 나중에 변경하지 않는다.
- 문제 의존성: 모든 문제에서 최적해를 보장하지는 않는다.
탐욕 알고리즘의 장단점#
- 단순성: 알고리즘이 직관적이고 구현하기 쉽다.
- 효율성: 대부분의 경우 실행 시간이 빠르다.
- 적은 자원: 추가적인 메모리나 계산 리소스가 적게 필요합니다.하다.
- 증분적 접근: 부분 해답을 점진적으로 구축한다.
- 최적해 보장 안함: 많은 문제에서 최적해를 찾지 못할 수 있다.
- 역추적 불가: 한번 내린 결정을 번복하지 않기 때문에, 선택이 잘못되었을 때 수정할 수 없다.
- 문제 의존성: 문제의 구조에 매우 의존적이다.
- 증명 필요: 탐욕 알고리즘이 최적해를 보장하는지 증명하는 과정이 필요합니다.
탐욕 알고리즘 설계 및 증명 방법#
- 탐욕 알고리즘 설계 단계
- 문제 분석: 문제가 탐욕 알고리즘으로 해결 가능한지 검토한다.
- 탐욕적 선택 정의: 각 단계에서 어떤 기준으로 선택할지 결정한다.
- 알고리즘 설계: 탐욕적 선택을 바탕으로 알고리즘을 설계한다.
- 최적성 증명: 탐욕 알고리즘이 최적해를 보장하는지 증명한다.
- 구현 및 테스트: 알고리즘을 구현하고 테스트한다.
- 최적성 증명 방법
탐욕 알고리즘이 최적해를 보장한다는 것을 증명하기 위한 일반적인 방법들:- 교환 논법(Exchange Argument)
탐욕적 선택이 항상 최적해의 일부가 될 수 있음을 보이는 방법이다.
최적해에 탐욕적 선택이 포함되어 있지 않다면, 이를 탐욕적 선택으로 교체해도 여전히 최적해임을 증명한다. - 귀납적 증명(Inductive Proof)
탐욕적 선택 후 남은 부분 문제에 대해서도 탐욕 알고리즘이 최적해를 찾는다는 것을 귀납적으로 증명한다.
탐욕 알고리즘 문제 해결 전략#
탐욕 알고리즘으로 문제를 해결할 때 고려해야 할 주요 전략과 패턴.
- 문제 분석 및 탐욕적 선택 결정
- 최적 부분 구조 확인: 문제가 최적 부분 구조를 가지는지 확인한다.
- 탐욕적 선택 정의: 각 단계에서 어떤 선택이 최적인지 결정한다.
- 선택의 안전성 검증: 탐욕적 선택이 항상 최적해를 보장하는지 확인한다.
- 일반적인 탐욕 전략 패턴
많은 문제에서 활용되는 일반적인 탐욕 전략 패턴: - 가장 큰/작은 요소 선택: 값이 가장 크거나 작은 요소를 우선적으로 선택한다.
- 비율 기반 선택: 두 값의 비율(예: 가치/무게)을 기준으로 선택한다.
- 가장 일찍/늦게 끝나는 것 선택: 종료 시간이 빠른 순으로 선택한다.
- 간선 기반 선택: 가중치가 가장 작은 간선부터 선택한다.
- 탐욕 알고리즘 디버깅 및 검증
- 작은 입력으로 테스트: 쉽게 검증할 수 있는 작은 입력으로 시작한다.
- 반례 찾기: 알고리즘이 실패할 수 있는 반례를 적극적으로 찾아본다.
- 증명 시도: 알고리즘이 최적해를 보장하는지 수학적으로 증명해본다.
- 최악의 경우 분석: 최악의 경우 시간 및 공간 복잡도를 분석한다.
탐욕 알고리즘이 최적해를 보장하는 경우#
탐욕 알고리즘이 항상 최적의 해답을 제공하지는 않는다. 그러나 다음 두 가지 속성을 가진 문제에서는 최적해를 보장한다.
탐욕 선택 속성(Greedy Choice Property)
현재의 선택이 이후의 선택에 영향을 주지 않으며, 지역적으로 최적인 선택이 전체적으로도 최적이 되는 속성.
즉, 각 단계에서의 최적의 선택이 누적되어 전체 문제의 최적해가 된다.
최적 부분 구조(Optimal Substructure)
큰 문제의 최적해가 작은 부분 문제들의 최적해로부터 구성될 수 있는 속성.
이는 동적 계획법(Dynamic Programming)과도 관련이 있는 개념이다.
이 두 속성을 모두 만족하는 문제에서는 탐욕 알고리즘이 항상 최적해를 찾을 수 있다.
탐욕 알고리즘의 대표적인 예제#
거스름돈 문제(Coin Change Problem)#
가장 적은 수의 동전을 사용하여 특정 금액을 만드는 문제이다.
한국의 화폐 시스템(10원, 50원, 100원, 500원)처럼 각 동전이 이전 동전의 배수인 경우, 탐욕 알고리즘이 최적해를 보장한다.
알고리즘:
- 가능한 가장 큰 단위의 동전부터 사용한다.
- 남은 금액에 대해 계속해서 가장 큰 단위의 동전을 사용한다.
예시 코드:
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 coin_change_greedy(coins, amount):
# 내림차순으로 동전 정렬
coins.sort(reverse=True)
coin_count = 0
coin_used = []
for coin in coins:
# 현재 동전으로 만들 수 있는 최대 개수를 사용
count = amount // coin
coin_count += count
amount -= count * coin
# 사용한 동전 기록
coin_used.append((coin, count))
# 금액이 0이 되면 종료
if amount == 0:
break
# 모든 동전을 사용해도 금액을 만들 수 없는 경우
if amount > 0:
return "거스름돈을 만들 수 없습니다."
return coin_count, coin_used
# 예시: 한국 화폐 시스템
coins = [500, 100, 50, 10]
amount = 1260
count, used = coin_change_greedy(coins, amount)
print(f"최소 동전 개수: {count}")
print("사용한 동전:")
for coin, num in used:
if num > 0:
print(f"{coin}원: {num}개")
|
활동 선택 문제(Activity Selection Problem)#
여러 활동이 있고, 각 활동은 시작 시간과 종료 시간이 있을 때, 한 사람이 가능한 많은 활동에 참여하려면 어떤 활동들을 선택해야 하는지 결정하는 문제.
알고리즘:
- 활동들을 종료 시간 기준으로 오름차순 정렬한다.
- 첫 번째 활동(가장 일찍 끝나는 활동)을 선택한다.
- 이전에 선택한 활동의 종료 시간 이후에 시작하는 활동 중 가장 일찍 끝나는 활동을 선택한다.
- 3번 과정을 반복한다.
예시 코드:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| def activity_selection(activities):
# 활동을 종료 시간 기준으로 정렬
activities.sort(key=lambda x: x[1])
selected = [activities[0]] # 첫 번째 활동 선택
last_finish_time = activities[0][1]
for i in range(1, len(activities)):
start_time, finish_time = activities[i]
# 현재 활동의 시작 시간이 마지막으로 선택된 활동의 종료 시간 이후라면 선택
if start_time >= last_finish_time:
selected.append(activities[i])
last_finish_time = finish_time
return selected
# 예시: (시작 시간, 종료 시간) 형태의 활동 리스트
activities = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]
selected_activities = activity_selection(activities)
print("선택된 활동들:")
for i, (start, finish) in enumerate(selected_activities):
print(f"활동 {i+1}: 시작={start}, 종료={finish}")
|
분수 배낭 문제(Fractional Knapsack Problem)#
여러 물건과 각 물건의 무게와 가치가 주어졌을 때, 제한된 용량의 배낭에 물건을 담아 최대 가치를 얻는 문제.
물건을 쪼개서 담을 수 있는 경우, 탐욕 알고리즘으로 최적해를 구할 수 있다.
알고리즘:
- 각 물건의 단위 무게당 가치(가치/무게)를 계산한다.
- 물건들을 단위 무게당 가치 기준으로 내림차순 정렬한다.
- 정렬된 순서대로 물건을 최대한 배낭에 담는다.
- 배낭의 용량이 물건의 무게보다 작은 경우, 물건의 일부만 담는다.
예시 코드:
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
| def fractional_knapsack(items, capacity):
# 각 물건의 무게당 가치 계산 및 정렬
for item in items:
item.append(item[0] / item[1]) # 가치/무게 추가
items.sort(key=lambda x: x[2], reverse=True) # 무게당 가치 기준으로 내림차순 정렬
total_value = 0
knapsack = []
for value, weight, ratio in items:
if capacity >= weight: # 물건 전체를 담을 수 있는 경우
knapsack.append((value, weight, 1.0)) # 마지막 값은 담은 비율
total_value += value
capacity -= weight
else: # 물건의 일부만 담을 수 있는 경우
fraction = capacity / weight
knapsack.append((value, weight, fraction))
total_value += value * fraction
capacity = 0
break
return total_value, knapsack
# 예시: [가치, 무게] 형태의 물건 리스트
items = [[60, 10], [100, 20], [120, 30]]
capacity = 50
total_value, selected_items = fractional_knapsack(items, capacity)
print(f"총 가치: {total_value}")
print("선택된 물건들:")
for i, (value, weight, fraction) in enumerate(selected_items):
print(f"물건 {i+1}: 가치={value}, 무게={weight}, 담은 비율={fraction:f}")
|
허프만 코딩(Huffman Coding)#
문자의 빈도수에 따라 가변 길이 코드를 생성하는 데이터 압축 알고리즘
자주 등장하는 문자는 짧은 코드로, 드물게 등장하는 문자는 긴 코드로 인코딩한다.
알고리즘:
- 각 문자와 빈도수를 리프 노드로 하는 최소 힙(우선순위 큐)을 생성한다.
- 가장 빈도수가 낮은 두 노드를 꺼내 새로운 내부 노드로 합친다.
- 새 노드의 빈도수는 두 자식 노드의 빈도수 합이다.
- 새 노드를 최소 힙에 추가한다.
- 최소 힙에 노드가 하나만 남을 때까지 2~4 과정을 반복한다.
- 최종 트리에서 왼쪽 간선은 0, 오른쪽 간선은 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
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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
| import heapq
from collections import defaultdict
class Node:
def __init__(self, char, freq):
self.char = char
self.freq = freq
self.left = None
self.right = None
def __lt__(self, other):
return self.freq < other.freq
def build_huffman_tree(text):
# 문자 빈도수 계산
frequency = defaultdict(int)
for char in text:
frequency[char] += 1
# 우선순위 큐 초기화
priority_queue = []
for char, freq in frequency.items():
heapq.heappush(priority_queue, Node(char, freq))
# 허프만 트리 구축
while len(priority_queue) > 1:
# 가장 빈도수가 낮은 두 노드 추출
left = heapq.heappop(priority_queue)
right = heapq.heappop(priority_queue)
# 내부 노드 생성
internal_node = Node(None, left.freq + right.freq)
internal_node.left = left
internal_node.right = right
# 새 노드를 우선순위 큐에 추가
heapq.heappush(priority_queue, internal_node)
# 루트 노드 반환
return priority_queue[0]
def generate_codes(node, code="", mapping=None):
if mapping is None:
mapping = {}
# 리프 노드인 경우 문자와 코드 매핑
if node.char is not None:
mapping[node.char] = code
else:
# 왼쪽 자식에게는 0, 오른쪽 자식에게는 1 할당
generate_codes(node.left, code + "0", mapping)
generate_codes(node.right, code + "1", mapping)
return mapping
def huffman_encoding(text):
if not text:
return "", None
# 허프만 트리 구축
root = build_huffman_tree(text)
# 코드 생성
codes = generate_codes(root)
# 인코딩
encoded_text = ""
for char in text:
encoded_text += codes[char]
return encoded_text, root
def huffman_decoding(encoded_text, root):
if not encoded_text:
return ""
decoded_text = ""
current_node = root
for bit in encoded_text:
# 0이면 왼쪽, 1이면 오른쪽으로 이동
current_node = current_node.left if bit == "0" else current_node.right
# 리프 노드에 도달하면 문자 추가
if current_node.char is not None:
decoded_text += current_node.char
current_node = root
return decoded_text
# 예시
text = "this is an example for huffman encoding"
encoded_text, huffman_tree = huffman_encoding(text)
print(f"원본 크기: {len(text) * 8} 비트") # ASCII 기준 1문자 = 8비트
print(f"압축 크기: {len(encoded_text)} 비트")
print(f"압축률: {(1 - len(encoded_text) / (len(text) * 8)) * 100:f}%")
decoded_text = huffman_decoding(encoded_text, huffman_tree)
print(f"디코딩 결과: {decoded_text}")
# 코드 출력
codes = generate_codes(huffman_tree)
print("\n각 문자의 코드:")
for char, code in sorted(codes.items()):
print(f"'{char}': {code}")
|
탐욕 알고리즘이 실패하는 경우#
분할 불가능한 배낭 문제(0-1 Knapsack Problem)#
물건을 쪼갤 수 없는 경우, 탐욕 알고리즘은 최적해를 보장하지 않는다.
반례:
- 배낭 용량: 10
- 물건1: 가치=60, 무게=10
- 물건2: 가치=100, 무게=8
- 물건3: 가치=120, 무게=5
탐욕적 접근 (가치/무게 기준):
- 물건3 선택: 가치/무게 = 24, 남은 용량 = 5
- 물건2를 선택하려 하지만 무게가 8이라 불가능
- 물건1을 선택하려 하지만 무게가 10이라 불가능
- 총 가치: 120
최적해:
- 물건2와 물건3 선택: 총 가치 = 100 + 120 = 220
최소 신장 트리 알고리즘#
프림(Prim)과 크루스칼(Kruskal) 알고리즘은 최소 신장 트리를 구하는 데 탐욕 알고리즘을 사용하지만, 일부 그래프 문제에서는 탐욕 접근이 실패할 수 있다.
그래프 색칠 문제(Graph Coloring Problem)#
각 정점에 인접한 정점과 다른 색을 칠하는 문제에서, 가장 많은 연결을 가진 정점부터 색을 칠하는 탐욕 접근은 최소 색상 수를 보장하지 않는다.
탐욕 알고리즘의 실제 응용 사례#
네트워크 라우팅#
다익스트라(Dijkstra) 알고리즘은 출발점에서 다른 모든 정점까지의 최단 경로를 찾는 탐욕 알고리즘이다.
인터넷에서 패킷 라우팅 등에 사용된다.
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
| import heapq
def dijkstra(graph, start):
# 초기화
distances = {node: float('infinity') for node in graph}
distances[start] = 0
priority_queue = [(0, start)]
while priority_queue:
current_distance, current_node = heapq.heappop(priority_queue)
# 현재 노드가 이미 처리된 경우 스킵
if current_distance > distances[current_node]:
continue
# 인접 노드 탐색
for neighbor, weight in graph[current_node].items():
distance = current_distance + weight
# 더 짧은 경로 발견 시 업데이트
if distance < distances[neighbor]:
distances[neighbor] = distance
heapq.heappush(priority_queue, (distance, neighbor))
return distances
# 예시: 그래프는 인접 리스트로 표현
graph = {
'A': {'B': 1, 'C': 4},
'B': {'A': 1, 'C': 2, 'D': 5},
'C': {'A': 4, 'B': 2, 'D': 1},
'D': {'B': 5, 'C': 1}
}
distances = dijkstra(graph, 'A')
print("A로부터의 최단 거리:")
for node, distance in distances.items():
print(f"{node}: {distance}")
|
스케줄링 알고리즘#
작업 스케줄링, CPU 스케줄링 등에서 탐욕 알고리즘이 널리 사용된다.
최단 작업 우선(SJF, Shortest Job First) 스케줄링#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| def shortest_job_first(jobs):
# 작업을 실행 시간 기준으로 정렬
jobs.sort(key=lambda x: x[1])
total_waiting_time = 0
current_time = 0
schedule = []
for job_id, execution_time in jobs:
schedule.append((job_id, current_time, current_time + execution_time))
total_waiting_time += current_time
current_time += execution_time
average_waiting_time = total_waiting_time / len(jobs)
return schedule, average_waiting_time
# 예시: (작업ID, 실행시간) 형태의 작업 리스트
jobs = [(1, 6), (2, 2), (3, 8), (4, 3), (5, 4)]
schedule, avg_waiting = shortest_job_first(jobs)
print(f"평균 대기 시간: {avg_waiting}")
print("스케줄:")
for job_id, start_time, end_time in schedule:
print(f"작업 {job_id}: 시작={start_time}, 종료={end_time}")
|
마감 시간과 이익이 있는 작업들을 스케줄링하여 최대 이익을 얻는 문제#
- 작업들을 이익 기준으로 내림차순 정렬한다.
- 각 작업에 대해, 마감 시간부터 역순으로 가장 늦게 가능한 시간 슬롯에 배정한다.
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 job_scheduling(jobs):
# 작업을 이익 기준으로 내림차순 정렬
jobs.sort(key=lambda x: x[2], reverse=True)
# 최대 마감 시간 찾기
max_deadline = max(job[1] for job in jobs)
# 결과 및 시간표 초기화
result = [None] * max_deadline
total_profit = 0
# 각 작업에 대해
for job_id, deadline, profit in jobs:
# 마감 시간부터 역순으로 가능한 시간 슬롯 찾기
for i in range(min(max_deadline, deadline) - 1, -1, -1):
if result[i] is None:
result[i] = job_id
total_profit += profit
break
scheduled_jobs = [job_id for job_id in result if job_id is not None]
return scheduled_jobs, total_profit
# 예시: (작업ID, 마감시간, 이익) 형태의 작업 리스트
jobs = [(1, 4, 20), (2, 1, 10), (3, 1, 40), (4, 1, 30)]
scheduled_jobs, total_profit = job_scheduling(jobs)
print(f"최대 이익: {total_profit}")
print(f"스케줄링된 작업: {scheduled_jobs}")
|
데이터 압축#
앞서 살펴본 허프만 코딩 외에도, LZ77, LZ78, LZW 등의 데이터 압축 알고리즘에서 탐욕적 접근이 사용된다.
인공지능 및 기계학습#
의사결정 트리(Decision Tree) 구축 시 정보 이득(Information Gain)이 가장 큰 특성부터 선택하는 전략도 탐욕 알고리즘의 일종이다.
참고 및 출처#
Divide and Conquer vs. Greedy Algorithm “Divide and Conquer"와 “Greedy Algorithm"은 문제 해결을 위한 두 가지 중요한 알고리즘 패러다임이다.
분할 정복은 문제를 더 작은 하위 문제로 나누어 해결하는 체계적인 접근 방식인 반면, 탐욕 알고리즘은 각 단계에서 지역적 최적 선택을 통해 문제를 해결하는 직관적인 접근 방식이다.
분할 정복은 정확한 최적해를 보장하지만 구현이 복잡할 수 있고, 탐욕 알고리즘은 구현이 간단하고 효율적이지만 항상 최적해를 보장하지는 않는다. 문제의 특성을 잘 이해하고 적절한 알고리즘을 선택하는 것이 중요하다.
...