그리디 알고리즘은 최적해를 구하는 데에 매우 효과적인 알고리즘입니다. 이 알고리즘은 매 단계에서 가장 최적인 선택을 하는 것으로 접근합니다. 이번 블로그 포스트에서는 그리디 알고리즘의 몇 가지 응용과 예시를 살펴보겠습니다.

1. 거스름돈 문제

거스름돈 문제는 그리디 알고리즘을 활용한 대표적인 예시입니다. 이 문제는 돈의 단위가 주어졌을 때, 가장 적은 개수의 동전으로 거스름돈을 주는 방법을 찾는 것입니다.

예를 들어, 돈의 단위가 [500원, 100원, 50원, 10원]이라고 가정해봅시다. 만약 거스름돈이 1260원이라면, 그리디 알고리즘을 활용하여 500원 2개, 100원 2개, 50원 1개, 10원 1개로 총 6개의 동전을 사용할 수 있습니다.

아래는 이러한 거스름돈 문제를 그리디 알고리즘을 사용하여 풀어보는 예시 코드입니다:

def change_coins(n, coin_types):
    count = 0
    for coin in coin_types:
        count += n // coin
        n %= coin
    return count

coin_types = [500, 100, 50, 10]
n = 1260

result = change_coins(n, coin_types)
print(result)  # 출력: 6

2. 회의실 배정 문제 (Interval Scheduling Problem)

회의실 배정 문제는 그리디 알고리즘을 사용하여 최대한 많은 회의를 진행할 수 있는 방법을 찾는 문제입니다. 각 회의는 시작 시간과 끝 시간이 주어지고, 한 회의가 끝나는 시간과 다음 회의의 시작 시간이 겹치지 않도록 회의를 선택해야 합니다.

아래는 회의의 시작 시간과 끝 시간을 리스트로 주어졌을 때, 그리디 알고리즘을 사용하여 최대한 많은 회의를 선택하는 예시 코드입니다:

def select_meetings(meetings):
    meetings.sort(key=lambda x: x[1])  # 끝 시간을 기준으로 정렬
    selected_meetings = [meetings[0]]
    end_time = meetings[0][1]
    
    for meeting in meetings[1:]:
        start_time = meeting[0]
        if start_time >= end_time:
            selected_meetings.append(meeting)
            end_time = meeting[1]
            
    return selected_meetings

meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 8), (5, 9), (6, 10), (8, 11), (8, 12), (2, 13), (12, 14)]

result = select_meetings(meetings)
print(result)  # 출력: [(1, 4), (5, 7), (8, 11), (12, 14)]

위의 예시에서는 총 11개의 회의가 주어졌고, 그리디 알고리즘을 사용하여 최대한 많은 회의를 선택한 결과 4개의 회의를 선택할 수 있었습니다.

이처럼 그리디 알고리즘은 최적해를 구하는 문제에서 쉽고 빠르게 접근할 수 있는 유용한 알고리즘입니다. 하지만 항상 최적해를 보장하지는 않으므로 주의가 필요합니다. 각 상황에 맞게 적절히 사용해야 합니다.