[파이썬] 그리디 알고리즘의 응용과 예시
그리디 알고리즘은 매 순간 최적의 선택을 하는 알고리즘으로, 각 단계에서 가장 유망한 선택을 하여 해답에 도달하는 방법입니다. 이번 블로그 포스트에서는 그리디 알고리즘의 몇 가지 응용과 예시를 살펴보고, 파이썬을 이용한 코드로 구현해 보겠습니다.
1. 거스름돈 문제
거스름돈 문제는 그리디 알고리즘의 대표적인 예제입니다. 어떤 금액을 내야 할 때, 가능한 적은 개수의 동전을 사용하여 거스르는 방법을 찾는 문제입니다.
예시 코드:
def make_change(coins, amount):
coins.sort(reverse=True) # 동전을 큰 순서대로 정렬
num_coins = 0
i = 0
while amount > 0:
if coins[i] <= amount:
num_coins += 1
amount -= coins[i]
else:
i += 1
return num_coins
2. 최소 신장 트리 (Minimum Spanning Tree, MST)
최소 신장 트리는 그래프에서 모든 정점을 포함하면서 사이클이 없고 가중치의 합이 최소인 트리를 찾는 문제입니다. 크루스칼(Kruskal) 알고리즘은 그리디 알고리즘을 기반으로 최소 신장 트리를 구하는 알고리즘입니다.
예시 코드:
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []
def add_edge(self, src, dest, weight):
self.graph.append([src, dest, weight])
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
def union(self, parent, rank, x, y):
xroot = self.find(parent, x)
yroot = self.find(parent, y)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 1
def kruskal_mst(self):
result = []
i = 0
e = 0
self.graph = sorted(self.graph, key=lambda item: item[2])
parent = []
rank = []
for node in range(self.V):
parent.append(node)
rank.append(0)
while e < self.V - 1:
u, v, w = self.graph[i]
i += 1
x = self.find(parent, u)
y = self.find(parent, v)
if x != y:
e += 1
result.append([u, v, w])
self.union(parent, rank, x, y)
return result
3. 탐욕적인 문자열 압축
탐욕적인 문자열 압축은 문자열에서 반복되는 문자열을 찾아 압축하는 문제입니다. 이때, 압축 결과의 길이가 최소가 되도록 압축해야 합니다.
예시 코드:
def compress_string(s):
compressed = ""
count = 1
for i in range(len(s) - 1):
if s[i] == s[i + 1]:
count += 1
else:
compressed += s[i] + str(count)
count = 1
compressed += s[-1] + str(count)
if len(compressed) < len(s):
return compressed
else:
return s
위 예시 코드들에서 볼 수 있듯이 그리디 알고리즘은 간단하면서도 효율적인 문제 해결 방법을 제공합니다. 그러나 항상 최적의 해를 보장하지 않으므로 주의가 필요합니다.
이상으로 그리디 알고리즘의 응용과 예시에 대해 알아보았습니다. 이를 통해 그리디 알고리즘의 개념과 활용법을 이해하고, 실제 문제에 적용할 수 있도록 연습해 보시기 바랍니다.