[알고리즘] 최소 동전으로 거슬러 주기, greedy 알고리즘, python (3)

greedy 알고리즘을 사용하면 좋은 경우

 

1. 최적 부분 구조 (Optimal Substructure)

- 부분 문제를 최적화하는 것이 곧 전체를 최적화하는 것이다. 

 

2. 탐욕적 선택 속성 (Greedy Choice property)

- 각 단계에서의 탐욕스런 선택이 최종 답을 구하기 위한 최적의 선택

 

가장 대표적인 문제 최대한 적은 동전을 사용해서 돈 거슬러 주기.

단 동전은 500, 100, 50, 10원만 있다고 가정한다.

작은 동전으로 큰 동전을 만들 수 없으면 문제는 달라짐

 

why?

- 100원, 70원, 10원짜리 동전이 있다고 가정

- 140원을 거슬러 준다. 

- greedy하게 선택하면 100원 1개, 10원 4개를 선택

- 하지만 70원 2개를 선택하는 게 가장 최적임

 

def min_coin_count(value, coin_list):
    # 누적 동전 개수
    count = 0
    coin_list.sort(reverse=True)
    
    # coin_list의 값들을 큰 순서대로 본다
    for i in coin_list:
        # 현재 동전으로 몇 개 거슬러 줄 수 있는지 확인한다
        count += (value // i)

        # 잔액을 계산한다
        value -= (value // i)*i

    return count

 

처음에 내가 실수 했던 것은 

def min_coin_count(value, coin_list):
    # 누적 동전 개수
    count = 0
    coin_list.sort(reverse=True)
    # coin_list의 값들을 큰 순서대로 본다
    for i in coin_list:

        value -= (value // i)*i

        count += (value // i)



    return count

value값을 업데이트 한업데이트한 다음에 count를 업데이트 한 것. count를 업데이트할 때 value가 사용되기 때문에 순서가 바뀌면 안 된다.