그리디(Greedy) 알고리즘은 현재 상황에서 가장 좋은 선택을 하는 것을 반복하여 최적해를 구하는 알고리즘 기법입니다. 파이썬에서는 다음과 같이 그리디 알고리즘을 구현할 수 있습니다.

예제1: 동전 거스름돈 문제

n원의 동전을 거슬러 주어야 할 때, 거슬러 줄 동전의 개수가 최소가 되도록 하려면 어떻게 거슬러 줘야 할까요? 예를 들어, 1260원을 거슬러 주어야 할 때, 500원, 100원, 50원, 10원 동전이 각각 몇 개씩 필요한지 구하는 문제입니다.

def change(n):
    coins = [500, 100, 50, 10]  # 동전 종류
    count = 0  # 거슬러 준 동전 개수
    for coin in coins:
        count += n // coin  # 동전 개수 누적
        n %= coin  # 거슬러 줘야 할 돈 계산
    return count

# 1260원 거슬러 주기
print(change(1260))  # 출력 결과: 6

위 코드에서 change() 함수는 n원을 거슬러 줄 때, 최소한의 동전 개수를 계산하여 리턴합니다. 동전 종류를 리스트로 정의하고, 반복문을 통해 각 동전 종류마다 거슬러 줘야 할 동전 개수를 계산합니다. 거슬러 줘야 할 돈을 계산하기 위해 나머지 연산자(%)를 사용합니다. 마지막으로 거슬러 준 동전 개수를 리턴합니다.

예제2: 동전 거스름돈

동전의 종류와 거스름돈의 금액이 주어졌을 때, 거슬러줘야 할 동전의 최소 개수를 구하는 예제입니다.

def coin_change(coins, amount):
    coins.sort(reverse=True)  # 동전의 큰 단위부터 검사
    count = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
    if amount == 0:
        return count
    else:
        return -1

# 동전 거스름돈 문제 예제
coins = [500, 100, 50, 10]
amount = 1260
print(coin_change(coins, amount))

위 코드에서 coin_change() 함수는 주어진 동전의 종류와 거스름돈의 금액을 받아 거슬러줘야 할 동전의 최소 개수를 구합니다. 동전의 종류를 큰 단위부터 검사하면서 거슬러줘야 할 금액(amount)보다 작은 동전을 가능한 많이 거슬러주면 됩니다. 거슬러줘야 할 금액이 동전의 종류로 나누어 떨어지지 않는 경우, 거스름돈을 정확히 거슬러줄 수 없으므로 -1을 리턴합니다.

예제3: 회의실 배정

주어진 회의 일정 중 겹치지 않게 최대한 많은 회의를 할 수 있는 예제입니다.

def meeting_rooms(intervals):
    intervals.sort(key=lambda x: x[1])  # 종료시간 기준으로 정렬
    count = 0
    end_time = 0
    for interval in intervals:
        if interval[0] >= end_time:
            end_time = interval[1]
            count += 1
    return count

# 회의실 배정 문제 예제
intervals = [(0, 30), (5, 10), (15, 20)]
print(meeting_rooms(intervals))

위 코드에서 meeting_rooms() 함수는 주어진 회의 일정 중 겹치지 않게 최대한 많은 회의를 할 수 있는 개수를 구합니다. 회의 일정을 종료시간을 기준으로 정렬하면서, 현재 회의가 이전 회의의 종료시간보다 뒤에 시작하는 경우에만 회의를 할 수 있습니다. 이전 회의의 종료시간을 갱신하고, 회의를 할 수 있는 개수를 증가시킵니다.