[자료구조] [Greedy_Algorithm] 개념 및 예시 문제

특정 시점에 주어진 정보 안에서 최적의 답을 찾아 나가는 방식이다. 간단하고 빠르다는 장점이 있으나 전역적으로 보았을 때, 최적의 해를 보장하지 않는다. 전제 조건 없이 Greedy algorithm을 적용할 수 있다.

 

다음의 두 가지 조건에 해당하는 경우, Greedy algorithm을 적용하면 최적의 해를 구할 수 있다.

1) Optimal substructure   우리가 구하고자 하는 문제들을 부분 문제로 나누어서 그것들의 최적의 답을 이용해서 해를 구하고자 할 경우

2) Greedy choice property 각 단계에서 최적의 답을 구하는 것이 궁극적으로 최종답을 찾아가는데 적합할 경우. 이 경우에는 case by case이므로 예시로 해당 문제에 대한 접근을 해나가야 조건에 해당하는지 알 수 있다.

 

(ex. 거스름돈 500, 50, 10원 동전을 이용해 최소한의 동전으로 거스러 주는 문제의 경우, 동전의 단위가 바뀌면 greedy choice property가 충족되지 않는다. 실수하기 쉬운 부분이다)

 

거슬러 줄 수 있는 coin_list를 받아서, 
거슬러줘야 하는 돈에 대해서 최소한의 coin수로 거슬러 주는 경우
먼저 해야 할 일이, coin_list를 역정렬해서(내림차순) 
sorted() 함수에서, reverse인자를 True로 바꿔줘야 한다. 
sorted(coin_list, reverse=True)

#내가 푼 코드

def min_coin_count(value, coin_list):
    # 코드를 작성하세요.
    v = value
    count = 0
    coin_list = sorted(coin_list, reverse=True)
    
    for i in range(0, len(coin_list)):
        c = v//coin_list[i]
        count += c
        v -= (coin_list[i]*c)
    
    return count

#좀 더 효율적으로 푼 코드
def min_coin_count(value, coin_list):
    count = 0

    #아예 sorted된 리스트를 받아서 거기에 있는 coin들을 불러오는 방식
    for coin in sorted(coin_list, reverse=True):
        count += (value // coin)
        #나누고 난 다음에 나머지와 관련된 함수 %
        value %= coin

    return count