Python을 이용한 그리디 알고리즘(Greedy Algorithm) 구현과 활용

그리디 알고리즘은 매 순간 최적이라고 생각되는 선택을 해 가면서 전체적인 해답에 도달하는 방식입니다. 이 방법은 간단하고 빠른 해결책을 제공하지만, 항상 최적의 해를 보장하지는 않습니다. Python을 사용하여 몇 가지 그리디 알고리즘을 구현하는 방법을 살펴보겠습니다.

 

동전 거스름돈 문제

가장 대표적인 그리디 알고리즘 예제 중 하나는 거스름돈 문제입니다. 고객에게 거슬러 주어야 하는 최소 동전의 수를 찾는 문제로, 가장 큰 단위의 동전부터 시작하여 거스름돈을 만들어 갑니다. Python으로 구현하면 다음과 같습니다:

 

def min_coins(coins, amount):
    coins.sort(reverse=True)
    total_coins = 0
    for coin in coins:
        if amount == 0:
            break
        count = amount // coin
        amount -= count * coin
        total_coins += count
    return total_coins

 

 

이 함수는 동전의 크기가 서로 배수 관계일 때 효율적으로 작동합니다.

 

분할 가능한 배낭 문제 (Fractional Knapsack)

이 문제는 물건을 쪼갤 수 있을 때, 주어진 무게 한도 내에서 물건의 가치가 최대가 되도록 배낭에 담는 방법을 찾는 것입니다. 물건의 가치 대비 무게 비율을 계산하여 높은 것부터 선택합니다. Python 구현은 다음과 같습니다:

 

def fractional_knapsack(value, weight, capacity):
    index = list(range(len(value)))
    ratio = [v/w for v, w in zip(value, weight)]
    index.sort(key=lambda i: ratio[i], reverse=True)
    max_value = 0
    for i in index:
        if weight[i] <= capacity:
            max_value += value[i]
            capacity -= weight[i]
        else:
            max_value += value[i] * (capacity / weight[i])
            break
    return max_value

 

 

최소 회의실 예약

여러 회의가 주어졌을 때, 하나의 회의실에서 최대한 많은 회의를 할 수 있도록 회의의 시작 시간과 끝나는 시간을 고려하여 스케줄을 짜는 문제입니다. 회의의 끝나는 시간을 기준으로 정렬한 후, 가장 빨리 끝나는 회의부터 스케줄을 잡습니다:

 

def max_meetings(start, end):
    meetings = sorted(zip(start, end), key=lambda x: x[1])
    count = 0
    last_end_time = 0
    for s, e in meetings:
        if s >= last_end_time:
            last_end_time = e
            count += 1
    return count

 

 

이와 같이 그리디 알고리즘은 매 순간 최선의 선택을 하여 문제를 해결합니다. 간단하면서도 효율적인 경우가 많지만, 모든 문제 상황에서 최적의 해를 제공하지는 않기 때문에 적용 시 문제의 성격을 잘 이해하고 사용해야 합니다. Python을 사용하면 이러한 알고리즘들을 쉽게 구현하고 실험해 볼 수 있습니다.