그리디 알고리즘은 최적해를 구하기 위해 항상 현재 상태에서 가장 최선의 선택을 하는 기법입니다. 이번 블로그 포스트에서는 그리디 알고리즘을 응용하고 활용한 몇 가지 사례들을 살펴보겠습니다. 파이썬을 사용하여 구현된 코드 예시도 함께 제공할 것입니다.
1. 거스름돈 문제
거스름돈 문제는 그리디 알고리즘이 잘 적용되는 대표적인 사례입니다. 이 문제를 해결하기 위해서는 가장 큰 단위의 동전부터 시작하여 거스름돈을 지불할 수 있는 가장 적은 동전의 개수를 찾아야 합니다.
def greedy_change(n, coins):
change = [] # 거스름돈 동전 리스트
for coin in coins:
num = n // coin # 동전 개수 계산
n %= coin # 남은 거스름돈
change.append(num)
return change
위 예시 코드에서 n은 거스름돈으로 받아야 할 돈의 액수이고, coins는 동전의 종류를 담은 배열입니다. 이 코드는 동전의 종류가 주어지면 해당 동전으로 거스름돈을 최소한의 개수로 지불하는 방법을 반환합니다.
2. 스케줄링 문제
스케줄링 문제는 작업의 시작 시간과 완료 시간이 주어졌을 때, 모든 작업을 가장 효율적으로 수행하는 방법을 찾는 문제입니다. 이때 그리디 알고리즘을 사용하여 가장 빨리 끝나는 작업을 우선적으로 수행하는 방법이 최적해를 보장합니다.
def greedy_scheduler(jobs):
sorted_jobs = sorted(jobs, key=lambda x: x[1]) # 완료 시간 기준으로 정렬
schedule = []
current_time = 0 # 현재까지의 시간
for job in sorted_jobs:
if job[0] >= current_time: # 작업 시작 시간이 현재 시간 이후라면
schedule.append(job)
current_time = job[1] # 작업 완료 시간을 현재 시간으로 업데이트
return schedule
위 예시 코드에서 jobs는 작업의 시작 시간과 완료 시간을 튜플로 담은 배열입니다. 이 코드는 작업의 완료 시간을 기준으로 정렬한 후 가장 빨리 끝나는 작업부터 순서대로 스케줄에 추가하여 최적의 작업 스케줄을 반환합니다.
3. 최소 신장 트리 문제
최소 신장 트리 문제는 그래프에서 모든 정점을 포함하는 최소한의 간선으로 이루어진 트리를 찾는 문제입니다. 그리디 알고리즘인 크루스칼 알고리즘이 최소 신장 트리 문제를 효율적으로 해결할 수 있는 방법 중 하나입니다.
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []
def add_edge(self, u, v, w):
self.graph.append([u, v, w])
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
def union(self, parent, rank, x, y):
root_x = self.find(parent, x)
root_y = self.find(parent, y)
if rank[root_x] < rank[root_y]:
parent[root_x] = root_y
elif rank[root_x] > rank[root_y]:
parent[root_y] = root_x
else:
parent[root_y] = root_x
rank[root_x] += 1
def kruskal(self):
result = []
i = 0
e = 0
self.graph = sorted(self.graph, key=lambda x: x[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
위 예시 코드는 크루스칼 알고리즘을 사용하여 그래프에서 최소 신장 트리를 찾는 방법입니다. add_edge() 메서드를 사용하여 그래프의 간선을 추가한 후 kruskal() 메서드를 호출하면 최소 신장 트리를 반환합니다.
위에서 소개한 예시들은 그리디 알고리즘이 다양한 문제에 적용될 수 있는 사례들 중 일부에 불과합니다. 그러나 이를 통해 그리디 알고리즘의 응용 및 활용 사례를 이해할 수 있습니다. 그리디 알고리즘은 항상 최적해를 보장하지는 않지만, 적절하게 사용된다면 효율적인 해결 방법을 제공할 수 있습니다.