Greedy Algorithms

Greedy 알고리즘

Greedy란?

그리디 알고리즘은 현재 상황에서 지금 당장 좋은 것만을 고르는 방법을 의미하며, 문제를 풀기 위해 최소한의 아이디어를 떠올릴 수 있는 능력이 필요하다.
⇒ 단순히 가장 좋아 보이는 것을 반복적으로 선택하여 최적의 해를 구할 수 있는지를 검토해야한다.

Greedy 알고리즘 조건

탐욕스러운 선택 조건

탐욕적인 선택은 항상 안전하다는 것이 보장되어야한다.
즉, 현재 상황에서 가장 좋은 것을 선택하는 방식을 통해 최적의 해를 구할 수
있다는 정당성이 존재해야한다.

최적 부분 구조 조건

문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적의 해결 방법이다라는 조건입니다.
즉, 전체 문제의 안에는 여러 단계가 존재하고 여러 단계 내의 하나 하나의 단계에 대해 최적해가 도출되어야 한다는 것입니다.

Greedy 알고리즘 문제 예시

거스름돈 문제

당신은 음식점의 계산을 도와주는 점원입니다.
카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원 동전이 무한개 존재합니다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러주어야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

가장 큰 화폐 단위인 500원 단위부터 차례로 거슬러 주게되면 최소의 동전 개수를 구할 수 있다.

• 정당성 확인: 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문에 정당하다
  ctex) 만약 화폐 단위가 500원, 400원, 100원일 경우에는 배수가 아니게 되기 때문에 그리디 방식으로 풀 수 없다.

Python Code

def solution(money):
    answer = 0
    change = [500, 100, 50, 10]

    for i in change:
        answer += money // i
        money %= i
    
		return answer