1.3 탐욕법 (Greedy)

<aside> 💡 "탐욕법"은 문제를 해결하기 위해 현 상태에서 가장 이득이 되는 선택을 하는 알고리즘 패러다임 입니다.

</aside>

탐욕법의 주요 특징은 다음과 같습니다.

1. 탐욕적 선택 속: 현재 단계에서의 선택이 이후에 영향을 미치더라도 현재 단계에서 최적인 선택을 합니다.
2. 최적 부분 구조: 각 단계에서의 선택이 전체 문제에 대한 최적해의 부분해이어야 합니다.
3. 하지만 항상 최적해를 보장하지는 않음: 탐욕적으로 선택하는 것이 항상 최적해를 보장하지는 않을 수 있습니다.

탐욕법의 3번 특징때문에 코딩테스트에서 이를 사용할때는 탐욕법의 해가 과연 코딩테스트 문제에서 원하는 해답일지 고민해봐야합니다.

 

 

위의 구조에서 가장 큰 수를 구하라 하였을 때 실제로 구해야하는 큰 수는 27이지만 탐욕법으로 접근하게 되면 20이 가장 큰 수로 구해지게 됩니다.

이와 같은 상황에서는 탐욕법으로 접근하면 최적 해를 구하지 못합니다.

탐욕법을 사용할 수 있는 가장 대표적인 문제는 거스름돈 문제가 있습니다.

 

📎 거스름돈 N원이 존재할때 10원, 50원, 100원, 500원, 1000원을 가장 적게 사용하여 N을 만드시오

 

탐욕 알고리즘의 해결 방법을 적용한다고 했을 때

1. 거슬러 줘야 할 돈의 개수를 줄이기 위해 현재 가장 비싼 돈을 선택한다. (1000원)
2. 1번 절차로 선택된 돈이 남은 거스름돈을 넘는지 확인하고, 넘는다면 1번 절차로 다시 돌아가서 돈의 액수를 줄인다.
3. 거슬러줘야 할 거스름돈이 남은지 확인하고 남은 경우 1번 절차로 돌아간다.

이를 의사코드로 표현하면 다음과 같습니다

function CoinChange(change):
    coins = [1000, 500, 100, 50, 10]
    
    coinCount = 0
   
    while change > 0:
        currentCoin = coins[0]
        
        while change >= currentCoin:
            change -= currentCoin
            coinCount += 1
        
        coins = coins[1:]
    
    return coinCount