그리디 알고리즘은 현재 상황에서 가장 최적인 선택을 하는 알고리즘입니다. 이번 글에서는 그리디 알고리즘의 응용과 예제를 소개하고, 파이썬으로 구현하는 방법을 설명하겠습니다.
1. 거스름돈 문제
거스름돈 문제는 그리디 알고리즘의 대표적인 예시입니다. 손님에게 돌려줘야 할 거스름돈의 개수를 최소화하는 문제로, 각 동전의 가치가 서로 배수 관계일 경우에 그리디 알고리즘으로 최적의 해를 구할 수 있습니다.
예시 코드
def change_money(money, coins):
change = []
coins.sort(reverse=True)
for coin in coins:
num = money // coin
money -= num * coin
change.append((coin, num))
return change
money = 1260
coins = [500, 100, 50, 10]
result = change_money(money, coins)
print(result)
위 코드는 1260원을 거슬러주기 위해 사용할 동전의 최소 개수를 구하는 예제입니다. 동전의 가치가 큰 순서대로 정렬하여 가장 큰 동전부터 사용하며, 거스름돈을 계속해서 갱신하고 결과를 리스트에 저장합니다.
2. 회의실 배정 문제
회의실 배정 문제는 주어진 회의 시간표에서 겹치지 않는 최대 개수의 회의를 고르는 문제입니다. 그리디 알고리즘으로 해결 가능한 문제 중 하나입니다.
예시 코드
def max_meetings(meetings):
sorted_meetings = sorted(meetings, key=lambda x: x[1])
selected = []
prev_end = 0
for meeting in sorted_meetings:
start, end = meeting
if prev_end <= start:
selected.append(meeting)
prev_end = end
return selected
meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]
result = max_meetings(meetings)
print(result)
위 코드는 주어진 회의 시간표에서 최대 개수의 겹치지 않는 회의를 선택하는 예제입니다. 회의 종료 시간을 기준으로 오름차순 정렬한 뒤, 겹치지 않는 회의를 선택하도록 합니다.
3. 배낭 문제
배낭 문제는 주어진 물건들의 가치와 무게를 고려하여 배낭의 용량 내에서 최대의 가치를 얻는 문제입니다. 그리디 알고리즘으로 해결할 수 없는 문제지만, 그리디 알고리즘을 이용한 근사적인 해법도 존재합니다.
예시 코드
def knapsack(capacity, items):
items.sort(key=lambda x: x[1]/x[0], reverse=True)
total_value = 0
selected = []
for item in items:
if item[0] <= capacity:
total_value += item[1]
capacity -= item[0]
selected.append(item)
return total_value, selected
capacity = 15
items = [(10, 60), (20, 100), (30, 120)]
result = knapsack(capacity, items)
print(result)
위 코드는 용량이 15인 배낭에 넣을 수 있는 물건들의 조합으로 얻을 수 있는 최대 가치를 구하는 예제입니다. 각 물건의 가치 대 무게 비율에 따라 내림차순 정렬한 뒤, 배낭에 넣을 수 있는 물건을 선택하고 가치의 합을 계산합니다.
위 예제들을 통해 그리디 알고리즘의 응용과 예제가 어떻게 구현되는지 살펴보았습니다. 그리디 알고리즘은 최적해를 보장하지 않을 수 있지만, 효율적이고 간결한 구현을 통해 다양한 문제를 해결할 수 있습니다.