탐욕 알고리즘

머신러닝에서 의사결정 트리를 구현할 때 사용하는 알고리즘

의사결정 트리는 설명하기 쉽기 때문에 분석가들이 선호하는 알고리즘 중 하나이다.

매 순간마다 최선의 선택을 하며,

가장 좋다고 생각되는 것만 선택한 것들로 최종적인 해답을 구하는 알고리즘

주의할 점은 전체를 고려하는게 아니라

문제를 부분적으로 나누어,

나누어진 문제에 대한 최적의 해답을 구하게끔 해야한다는 것

예제 : 14원의 잔돈을 줘야하는데, 잔돈의 종류가 10원, 7원, 1원이 있으면

잔돈을 가장 빨리 줄 수 있는 방법은?

coin=[10,7,1]
coin=sorted(coin,reverse=True) # 큰 값을 맨 앞으로 오게끔 정렬
def greedy():
    num=int(input('잔돈을 입력하세요~ '))
    for i in coin:
        if coin.index(i)!=len(coin)-1:
            print(str(i)+'원 동전 '+str(num//i)+'개, ',end='')
            num=num%i
        else:
            print(str(i)+'원 동전 '+str(num//i)+'개로 줍니다.')
greedy()