알고리즘 (탐욕 알고리즘)

탐욕 알고리즘

탐욕 알고리즘(greedy algorithm)은 코테에서 가장 많이 등장하는 알고리즘 유형이다. 반드시 알고 넘어가야하는 중요한 알고리즘이다. 탐욕 알고리즘의 특징은 여러개의 선택지가 주어지고 그 중 하나를 선택해야 할 때 매 순간 최적의 방법을 선택하는 방식으로 진행된다는 점이다.

탐욕 알고리즘 예제

탐욕 알고리즘에서 가장 기본적인 유형은 동전 수 카운팅하기 문제이다.

500,100,50,10 동전이 있다고 가정했을 때 원하는 값을 가장 적은 수의 동전으로 조합해라

이러한 경우에 매 순간 최적의 방법은 가장 큰 값인 500원을 가장 많이 사용하고 더 이상 사용이 불가능하면 다음 가장 큰 값인 100원 짜리 동전을 많이 사용하는 순으로 진행되야 가장 적은 수의 동전으로 원하는 값을 만들어 낼 수가 있다.

coin_list= [1,500,50,10]
coin_list.sort(reverse=True)

def greedy(value, coin_list):
    count = 0
    used_coin = []
    for coin in coin_list:
        coin_num = value // coin
        count += coin_num
        value -= coin_num * coin
        used_coin.append([coin, coin_num])
    return used_coin, count

탐욕 알고리즘의 한계

탐욕 알고리즘은 최적의 해에 가까운 값은 구할 수 있지만 그것이 완벽한 최적의 해를 뜻하는 것이 아니다. 일일히 경우의 수를 계산하고 따져보면 더 낳은 해가 발견될 수 있다. 하지만 탐욕 알고리즘을 사용하면 짧은 시간에 최적의 해에 가까운 값을 찾을 수 있다.