[TIL] 107. 그리디(Greedy; 탐욕 알고리즘)

키워드

• 그리디

그리디 알고리즘

• 완벽한 최적의 답을 찾기보다, 주어진 상황을 한단계씩 빠른 시간내에 해결하기 위해 사용하는 알고리즘

def changes(price):
    change = 1000 - price
    coin_list = [700, 400, 300, 100, 50, 10]
    ans_dict = {}

    for coin in coin_list:
        if change // coin <= 0:
            pass
        else:
            ans_dict[coin] = change // coin
            change %= coin

    return ans_dict

• 위의 코드에서 price=400 일 때, 동전 갯수가 가장 적게 거스름돈을 받는 건 300원 2개인데 그리디를 사용하면 400 1개, 100 2개
• 즉, 최적의 답을 찾지는 못하지만 근사한 수치로 빠르게 문제를 해결할 수 있다는 장점

DP와 Greedy

• DP : 문제를 작은 단위로 분할하여 해결 후, 해결된 중복 문제들의 결과를 이용하여 전체 문제를 해결
• Greedy : 각 단계에서 최선의 답에 접근, 개별적으로 문제를 해결해나아간다.(즉, 숲을 보기보단 나무 하나하나를 해결)