그리디 알고리즘(탐욕법)

• 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 일반적으로 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력이 필요함
• 현재 상황에서 단순히 가장 좋아 보이는 것만을 반복적으로 선택했을 경우 최적의 해가 될 수 있는지 검토해야 하기 때문에 정당성 분석이 중요하다.

최적의 해

 

 

각 노드 상황마다 최적의 해를 찾는 경우

각 노드 상황마다 최적의 해를 찾을 경우 총합은 4+10+5 = 19 이지만 사실은 진짜 최적의 해는 4 + 9 + 8 = 21이다.

따라서 지금 같은 상황에서는 그리디 알고리즘이 최적의 해를 보장할 수 없다 라고 표현한다.

 

그렇기 때문에 코딩 테스트에서 출제 되는 그리디 문제는 탐욕법으로 풀었을 경우 최적의 해가 보장 되는 경우에 출제가 된다.

 

[문제] 거스름 돈

어느 가게에 계산을 도와주는 점원이 있다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다. 가게를 방문한 손님은 점원에게 N원의 돈을 지불 했을 경우에 교환 받는 동전의 최소 개수는 몇개 인가? 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

 

- 해법:

가장 큰 화폐부터 돈을 거슬러 준다. 

이 정당성이 검증이 되는 이유에는 거스름 돈중 큰 단위가 항상 작은 단위의 배수이기 때문에 작은 단위들을 종합해 다른 해가 나올 수 없기 때문이다.

 

ex) 1000원을 600원,500원,100원으로 거슬러 줄 경우 :

탐욕법(600원 1개 ,100원 4개), 최적의 해 (500원 2개)

 

- 시간 복잡도:

화폐의 종류가 N개 이면, for문이 화폐의 종류만큼 반복되기 때문에 시간 복잡도는 O(N)

- 코드:

n = 1260
count = 0

# 큰 단위부터 교환
array = [500,100,50,10]

for money in array:
    # 거슬러준 동전 갯수
    count += n // money
    # 교환 하고 남은 잔액
    n %= money


print(count)

 

- 결과:

6