Greedy-algorithm.md

---

개념

현재 상황에서 지금 당장 좋은 것만 고르는 방법

• 매순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고민하지 않는다.

• 사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형

예시 - 거스름돈 문제

Q. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

문제 풀이

• 가장 큰 화폐 단위 부터 거슬러 주는 것 500 > 100 > 50 > 10

def solution():
    coin = int(input())
    count = 0
    array = [500, 100, 50, 10]
    for i in array:
        count+=coin // i
        coin %= i
    return count

하지만 위의 풀이는 거슬러 줄 수 있는 동전의 단위가 가장 큰 금액이 나머지 동전의 배수이기 때문에 가능한 풀이이다. 만약 화폐의 단위가 500, 300, 100, 10 이라면 위의 코드는 답이 될 수 없다.

• 즉, 각 문제 상황에 맞게 가장 최적의 아이디어를 떠올리고 정당성을 확인하는 것이 그리디 알고리즘을 푸는 방법이다.

그리디 알고리즘의 정당성

대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없는 가능성이 다분하다.

• ✔ 위에서 말했듯이, 문제 상황에 맞는 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할수 있어야 한다.