[Greedy Algorithm] 당장 좋은 것만 선택하는 Greedy

1. 당장 좋은 것만 선택하는 Greedy Alogrithm

Greedy Alogorithm 이란?

📌현재 상황에서 지금 당장 좋은 것만 고르는 방법📌
즉, 매 순간 가장 좋아 보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

보통 코딩테스트에서 출제되는 Greedy Alogorithm 유형의 문제는 창의력, 즉 문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있능 능력을 요구한다.

Greedy Alogirithm 은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 문제에서 ‘가장 큰 순서대로’ 혹은 ‘가장 작은 순서대로’와 같은 기준을 알게 모르게 제시해준다.

대체로, 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 Greedy Algorithm 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제된다.

예제 1. 거스름돈

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

문제 해설

💥 아이디어 : 가장 큰 화폐 단위부터 돈을 거슬러 준다. 💥</u>

N원을 거슬러 줘야 할 때, 가장 먼저 500원부터 최대한 거슬러 주고 그 다음 100원, 50원, 10원 이런식으로 주면 동전을 최소한으로 거슬러 줄 수 있다.

예를 들어 입력으로 주어진 N을 1,260원이라고 가정하면 아래와 같은 과정으로 거슬러 줄 수 있다.

Step 0 초기 단계 - 남은 돈 : 1,260원
점원 : 500 500 100 100 50 10
손님 :

Step 1 남은 돈 : 260원 1,260원에서 500원짜리로 거슬러 줄 수 있는 돈은 1,000원, 즉 500원 2개이고 남은 돈은 260원이다.
점원 : 100 100 50 10
손님 : 500 500

Step 2 남은 돈 : 60원 앞 단계에서 남은 돈 260원에서 100원 단위로 거슬러줄 수 있는 돈은 200원, 즉 100원 2개이고 남은 돈은 60원이다.
점원 : 50 10
손님 : 500 500 100 100

Step 3 남은 돈 : 10원 앞 단계에서 남은 돈 60원에서 50원 단위로 거슬러줄 수 있는 돈은 50원 1개이고, 남은 돈은 10원이다.
점원 : 10
손님 : 500 500 100 100 50

Stop 4 남은 돈 : 0원 이제 남은 돈은 10원이고, 10원 1개를 거슬러 주며 거스름돈 계산을 모두 마쳤다.
점원 :
손님 : 500 500 100 100 50 10

따라서, N이 1,260원일 때 손님이 받은 동전의 최소 개수는 6개이다.

Python code

n = 1260
count = 0

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

for coin in coin_types:
  count += n // coin # 해당 화폐로 거슬러 줄 수 있는 동전의 개수 세기
  n %= coin

print(count)

화폐의 종류가 K개라고 할 경우, 위 소스 코드의 시간 복잡도는 O(K) 이다.

해당 알고리즘의 시간 복잡도는 동전의 총 종류에만 영향을 받고 거슬러 주어야할 돈 N에는 영향을 받지 않는다는 것을 알 수 있다.

Greedy Algorithm의 정당성

Greedy Alogirithm 으로 문제의 해법을 찾았을 경우에는 그 해법이 정당한지 검토해야 한다.
위 예제를 Greedy Algorithm 으로 해결할 수 있었던 이유는 가지고 있는 동전 중에서 큰 단위가 항상 작은 단위의 배수이므로 작은 단위의 동전들을 조합해 다른 해가 나올 수 없기 때문이다.

---

🐢 현재 공부하고 있는 이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저자 의 책을 학습하며 기록 및 정리를 하기위한 내용들입니다. 🐢

감사합니다.😊

Algorithm 카테고리 내 다른 글 보러가기