[이코테 python] Ch.3 그리디 (+ 거스름돈 문제)

3.1  그리디(Greedy) 알고리즘

 

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

 

 

그리디 알고리즘은 탐욕법 이라고도 불리며,

현재 상황에서 가장 최선의 선택만을 하는 알고리즘이다.

 

즉, 현재의 선택이 나중에 미칠 영향은 고려되지 않는다.

 

 

 

---

 

3.2  그리디 알고리즘 문제유형

 

 

그리디 알고리즘 문제유형은 다른 유형에 비해,

 

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

 

 

하지만 문제를 풀기 위한 아이디어와 창의력을 요구한다.

 

따라서 많은 문제 유형을 접하고 풀어보는 훈련이 필요하다.

 

 

 

먼저, 코딩테스트에는 문제 유형을 바로 파악하기 어렵다면, 그리디 문제를 의심해본다.
하지만 정당한 탐욕적 해결법이 없다면, 다이나믹 프로그래밍 / 그래프 알고리즘을 고민해보자.

 

 

 

또한, 그리디 문제에서는 '가장 큰 순서대로' / '가장 작은 순서대로' 와 같은 기준을 제시한다.

 

따라서, 정렬 문제와 같이 출제되는 경우가 많다.

 

 

---

 

3.3  그리디 알고리즘의 정당성

 

그리디 알고리즘은 최적의 해를 찾을 수 없을 가능성이 높다.

 

따라서, 그리디 알고리즘으로 문제를 해결하고자 할 때에는, 해법의 정당성을 검토해야 한다.

 

---

 

3.4  그리디 알고리즘 예시 - 거스름돈

 

 

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

 

 

1) 문제 해결 아이디어

 

 

가장 큰 화폐부터 돈을 거슬러 주자.

 

 

예를 들어 N이 1260원인 경우,

 

500원으로 거슬러 줄 수 있는 최대 개수 : 2개

100원으로 거슬러 줄 수 있는 최대 개수 : 2개

50원으로 거슬러 줄 수 있는 최대 개수 : 1개

10원으로 거슬러 줄 수 있는 최대 개수 : 1개

 

를 차례대로 거슬러 주면 된다.

 

 

 

2) 문제 해결 코드 ( Python)

 

n = 1260
count = 0

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

for coin in coin_type:

    # 해당 화폐로 거슬러 줄 수 있는 개수
    count += n // coin

    # 남은 금액
    n %= coin

print(count)

 

 

1) count = 0 : 동전의 개수를 세는 변수

 

2) coin_type : 가장 큰 화폐부터 확인하도록 하는 배열

 

3) count += n // coin : 남은 금액을 500 원부터 차례대로 나눈 몫을, count 에 추가한다.

 

4)  n %= coin : 남은 금액을 500원 부터 차례대로 나눈 나머지를, 다시 남은금액으로 지정한다.

 

 

 

시간복잡도는 거슬러 줘야 하는 금액과는 상관없이, 동전의 총 종류에만 영향을 받으므로
화폐의 종류가 K일때 시간복잡도는 O(K) 이다.

 

 

 

3) 문제 해결 정당성

 

 

이 문제에서는 큰 단위의 동전이 항상 작은 단위의 동전의 배수이므로,
작은 단위의 동전을 종합하여 다른 해가 나올 수 없다.

 

 

예를 들어, 화폐의 종류가 500원, 400원, 100원 이라면

800원을 거슬러 줄 때

 

그리디 알고리즘을 사용하면 4번을 거슬러 줘야 하지만 (500 + 100 + 100 + 100),

최적의 해는 2번을 거슬러 주는 것이다. (400 + 400)

 

 

하지만, 

이 문제에서는 큰 단위가 작은 단위의 배수이므로

단순히 큰 단위부터 거슬러 주는 탐욕법으로 문제를 해결할 수 있다.

 

 

 

 

 

 

 

 

나동빈 '이것이 코딩 테스트다 with 파이썬' 책을 기반으로 작성하였습니다.

https://www.youtube.com/watch?v=m-9pAwq1o3w&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC