#1 Greedy Algorithm

그리디 알고리즘

그리디 알고리즘은 그대로 직역하여 국내에서는 "탐욕 법"으로 소개된다. 어떠한 문제가 있을 때 단순 무식하게, 탐욕적으로 문제를 푸는 알고리즘이다.

 

여기서 탐욕적이라는 말은 "현재 상황에서 가장 좋은 것만 고르는 방법"이다. 매 순간 가장 좋아 보이는 것만 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

 

예시로 알아보자.

 

 

<예시> 거스름 돈

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

 

 

<문제 해설>

그리디 알고리즘 문제의 대표 유형으로 가장 간단한 아이디어만 떠올릴 수 있다면 해결할 수 있다.

 

이 문제에서 아이디어는 "가장 큰 화폐 단위부터" 돈을 거슬러 주는 것이다. N원을 거슬러 줘야 할 때, 가장 먼저 500원으로 거슬러 준다. 그 다음 100원, 50원, 10원 차례대로 거슬러 주면 된다.

 

Input: N = 1260

 

[Step 0] 초기 단계 - 남은 돈: 1,260원

 

[Step 1] 남은 돈: 260원 - 1260원에서 500원으로 거슬러 줄 수 있는 돈은 1000원, 즉 500원 2개이고, 남은 돈은 260원이다.

 

 

[Step 2] 남은 돈: 60원 - 앞 단계에서 남은 돈 260원에서 100원 단위로 거슬러줄 수 있는 돈은 200원, 즉 100원 2개이고 남은 돈은 60원이다.

 

 

[Step 3] 남은 돈: 10원 - 앞 단계에서 남은 돈 60원에서 50원 단위로 거슬러줄 수 있는 돈은 50원 1개이고, 남은 돈은 10원이다.

 

[Step 4] 남은 돈: 0원 - 이제 남은 돈은 10원이고, 10원 1개를 거슬러 주며 계산을 마친다.

 

 

<구현 코드>

n = 1260
count = 0

# 큰 단위의 화폐부터 차례대로 확인하기
array = [500, 100, 50, 10]

for coin in array:
    count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
    n %= coin # 화페로 나눈 나머지 n에 대입

print(count)

 

 

Ref:

- 이것이 코딩 테스트다 with Python, 나동빈, 한빛미디어

- https://freedeveloper.tistory.com