[TIL] 그리디 알고리즘(탐욕법, Greedy Algorithm)

그리디 알고리즘(탐욕법, Greedy Algorithm)

• 각 단계에서 가장 좋아 보이는 선택을 하는 방식이다. 현재 상황에서 최선을 선택을 한다. 
• 한 번 선택한 것은 되돌리지 않는다. 
• 빠르고 간단하지만, 항상 최적의 해를 보장하지는 않는다. 

 

예제 (거스름돈 문제) 

def 거스름돈(금액):
    동전 = [500, 100, 50, 10]  # 사용 가능한 동전의 종류
    결과 = {}

    for 단위 in 동전:
        개수 = 금액 // 단위
        if 개수 > 0:
            결과[단위] = 개수
            금액 %= 단위

    return 결과

print(거스름돈(1260))

• 가장 큰 단위의 동전부터 시작한다. 
• 현재 금액에서 해당 동전을 최대한 많이 사용한다. 
• 남은 금액에 대해 다음으로 큰 단위의 동전으로 넘어간다. 
• 모든 동전에 대해 이 과정을 반복한다. 

이 방식은 거스름돈 문제에서는 최적의 해를 보장하지만, 모든 문제에서 그렇지는 않는다. 그리디 알고리즘이 잘 작동하는 다른 예시로는 크루스칼 알고리즘(최소 신장 트리), 다익스트라 알고리즘(최단 경로) 등이 있다. 

 

연습 문제 

• [백준] https://www.acmicpc.net/step/33