[Algorithm] 그리디 (탐욕) 알고리즘

그리디 알고리즘(탐욕법, Greedy Algorithm)

 

매 선택에서 현재 상황에 지금 당장 좋은 것만을 선택하여 적합한 결과를 도출하는 알고리즘 설계 기법

이 방법은 선택하는 그 순간에는 최적인 방법이지만 최종적으로 보면 그 선택들이 최적이라는 보장은 없다. 

 

그리디 알고리즘은 완전한 최적해를 보장하지는 않지만 그런대로 괜찮은 해답을 알려준다. 

계산속도가 정확한 알고리즘에 비해서 빠른 경우가 많다. 따라서, 적당히 괜찮은 해답을 정해진 시간 내 찾을 때 적합한 알고리즘이다.   

 

대표적인 그리디 알고리즘의 예 : 다익스트라 알고리즘(최단 경로 문제)

 

 

 

대표적인 그리디 알고리즘 문제 : 거스름 동전 개수 구하기

def greedy(money):
    m = [500, 100, 50, 10]
    cnt = 0
    for i in m:
        temp = divmod(money, i)
        print(f'{i}원짜리 동전 : {temp[0]}개')
        cnt += temp[0]
        money = temp[1]
    return cnt

print(f'최소한으로 거슬러주는 동전의 개수 : {greedy(3820)}개')

# 출력값
500원짜리 동전 : 7개
100원짜리 동전 : 3개
50원짜리 동전 : 0개
10원짜리 동전 : 2개
최소한으로 거슬러주는 동전의 개수 : 12개

 

[백준(Baekjoon] 11047 동전 0