[파이썬] 그리디 알고리즘의 활용과 최적화
그리디 알고리즘은 최적해를 구하는 데에 유용한 알고리즘입니다. 그리디 알고리즘은 각 단계에서 지금 당장 가장 좋아 보이는 선택을 하는 방식으로 문제를 해결합니다. 이러한 선택은 지역적으로는 최적이지만, 전체적으로는 최적해를 보장하지는 않을 수 있습니다.
하지만, 그리디 알고리즘은 문제의 특성에 따라 유용하게 사용할 수 있는 경우가 많습니다. 특히 아래와 같은 경우에 그리디 알고리즘을 활용하면 좋은 성능을 얻을 수 있습니다.
1. 배낭 문제 (Knapsack Problem)
배낭 문제는 주어진 배낭의 용량 내에서 가장 가치가 높은 물건의 조합을 찾는 문제입니다. 이 때, 물건은 분할할 수 없어야 합니다.
그리디 알고리즘을 적용한 배낭 문제 해결 방법은 다음과 같습니다.
def knapsack_greedy(items, weight):
items = sorted(items, key=lambda x: x.value / x.weight, reverse=True)
total_value = 0
total_weight = 0
selected_items = []
for item in items:
if total_weight + item.weight <= weight:
selected_items.append(item)
total_value += item.value
total_weight += item.weight
return selected_items, total_value
2. 거스름돈 문제 (Change Making Problem)
거스름돈 문제는 가게에서 물건을 구매하는데 동전을 최소한으로 사용하여 거스름돈을 주는 문제입니다.
그리디 알고리즘을 적용한 거스름돈 문제 해결 방법은 다음과 같습니다.
def make_change_greedy(coins, amount):
coins = sorted(coins, reverse=True)
change = []
total_coins = 0
for coin in coins:
while amount >= coin:
change.append(coin)
amount -= coin
total_coins += 1
return change, total_coins
3. 탐욕적 스케줄링 (Greedy Scheduling Problem)
탐욕적 스케줄링은 주어진 작업들을 가장 효율적으로 스케줄링하는 문제입니다. 각 작업은 시작 시간, 종료 시간, 수행 시간을 가지고 있으며, 한 번에 하나의 작업만을 실행할 수 있습니다.
그리디 알고리즘을 적용한 탐욕적 스케줄링 해결 방법은 다음과 같습니다.
def greedy_scheduling(jobs):
jobs = sorted(jobs, key=lambda x: x.end_time)
schedule = []
current_time = 0
for job in jobs:
if job.start_time >= current_time:
schedule.append(job)
current_time = job.end_time
return schedule
그리디 알고리즘은 문제에 따라 가장 최적의 해를 구할 수 있는 효율적인 방법을 제공합니다. 그러나 항상 최적해를 보장하는 것은 아니므로 문제의 특징과 제약 조건을 잘 파악하여 사용하는 것이 중요합니다.