그리디 알고리즘

현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘이다.
-> 전체를 봤을 때 항상 최적의 해를 보장하진 않는다.

핵심 이론

1. 해 선택: 현재 상태에서 가장 최선이라고 생각하는 해를 선택한다.
2. 적절성 검사 : 현재 선택한 해가 전체 문제의 제약 조건에 벗어나지 않는지 검사한다.
3. 해 검사: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다.
   전체 문제를 해결하지 못한다면 1로 돌아가 같은 과정을 반복한다.

코드구현

그리디 알고리즘은 문제에 따라 다양하게 구현가능하므로, 정해진 코드가 없다.
아래 코드는 대표적인 문제인 거스름돈을 계산하는 그리디 알고리즘 코드이다.

def give_change(coins, amount):
    coins.sort(reverse=True)  # 동전을 큰 단위부터 정렬합니다.
    change = []  # 거스름돈을 담을 리스트

    for coin in coins:
        while coin <= amount:
            change.append(coin)
            amount -= coin

    if amount > 0:
        return []  # 거스름돈을 정확히 주지 못하는 경우 빈 리스트 반환
    else:
        return change

coins는 동전의 종류를 담은 배열이고, amount는 거스름돈 금액이다.