[탐욕법] 당장 좋은 것만 선택하는 그리디

그리디 알고리즘이란

그리디 알고리즘이란 한국어로 번역하면 탐욕적인이라는 뜻으로 현재 상황에서 지금 당장 좋은 것만 고르는 알고리즘입니다.

그 뜻은 해당하는 구간에서 가장 좋은 것만 선택하고 다음 구간을 고려하지 않는다는 뜻입니다.

아래에 거스름 돈에서 그리디를 사용할 떄와 사용하면 안될 때를 설명하겠습니다.

거스름 돈 코드

# 그리디 알고리즘 코인선택
def greed_coin(N,coins):
    count = 0
    for coin in coins:
        count+= N//coin
        N %=coin
    print("최소 동전 " , count)
    
N = 1310
coins = [500,100,50,10]
greed_coin(N,coins)

1310원의 돈을 그리디 알고리즘으로 해결하는 코드입니다. 몫은 코인에서 남은 돈을 나눈 값(동전 카운트), 나머지는 현재 남은 돈에서 코인으로 나눈 값으로 동전이 큰 순으로 구현할 수 있습니다.

 

그리디 알고리즘 문제점

모든 문제를 그리디 알고리즘으로 풀 수 있을까는 생각을 많이 해야합니다. 위 거스름 돈 코드 같은 경우 큰 단위가 항상 작은 단위의 배수 형태일 때 최적의 해를 보장할 수 있다는 사실을 알 수 있습니다. 하지만  N = 900, coins = [500,400,100] 인 경우 그리디를 사용할 경우 최소 동전은 400원 두 개, 100원 하나 총 3개를 반환해야 하지만 500 원 하나 100원 4개로 최소 동전은 5개를 반환하는 문제가 생겨 이와 같은 경우 문제를 해결하기 위해서는 그리디 알고리즘 말고 다른 다이나믹 프로그래밍을 사용해 문제를 해결해야합니다.