1. 그리디 알고리즘 : 그리디 알고리즘 소개, 최소 거스름돈 동전 개수 문제

그리디 알고리즘은 탐욕적으로 가장 좋은 것만 선택하는 알고리즘.

즉 현재 상황에서 지금 당장 좋은 것만 고르는 방법! 매 순간 가장 좋아 보이는 것을 선택하며,

현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.

 

사전에 외우고 있지 않아도 풀 수 있을 가능성이 높은 문제 유형. 반면에 이후에 다룰 정렬,

최단 경로는 알고리즘 사용 방법을 정확히 알고 있어야 함.

 

최단 경로: 플로이드 워셜 혹은 다익스트라 알고리즘과 같은 알고리즘이 있다. 여기서 다익스트라 알고리즘은 엄밀히 말하면 그리디 알고리즘으로 분류 된다. 이는 이후에 다룬다.

 

유형이 다양하기 때문에 항상 잘 풀 수 있는 알고리즘 유형은 아니다.

많은 유형을 접해보고 훈련!

 

문제를 풀기 위한 최소한의 아이디어를 떠올릴 수 있는 능력을 요구. 다시 말해서 현재 상황에서 가장 좋아 보이는 것을 선택해도 문제를 풀 수 있는지를 파악해야함.

 

그리디 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 알게 모르게 제시해준다. 이 기준은 정렬 알고리즘을 사용했을 때 만족시킬 수 있으므로 자주 짝을 이뤄서 출제 됨

 

 

당신은 음식점의 계산을 도와주는 점원이다.

카운터에는 거스름 돈 500원, 100원, 50원, 10원이 무한으로 존재.

손님한테 거슬러야 할 돈이 N원일 때 거슬줘야 할 때 최소 동전 개수.

(거슬러줘야할 돈은 항상 10배수)

 

 

hint : 동전의 수가 최소가 되려면 큰 돈부터 주어야 함!

 

pay  = int(input("지불한 돈을 입력해주세요. :"))

fivehund = 0
hund = 0
threeten = 0
ten = 0

if pay % 10 == 0 :
  while (pay >= 500) :
    pay = pay - 500
    print(pay)
    fivehund = fivehund + 1
    print(fivehund)
  while pay >= 100:
    pay = pay - 100
    hund = hund + 1
  while pay >= 30:
    pay = pay - 30
    threeten = threeten + 1
  while pay >= 10:
    pay = pay - 10
    ten = ten + 1


  print(f"500원 {fivehund} 개")
  print(f"100원 {hund} 개")
  print(f"30원 {threeten} 개")
  print(f"10원 {ten} 개")
  print(f"총 {fivehund+hund+threeten+ten} 개")
else :
  print("10원 단위로 입력해주세요")

7

 처음엔 이렇게 풀었다. 당연히 쉽게 생각할 수 있는 접근 방식인데, 약간 좀 아쉽다는 생각이 들었다.

이 문제를 간단하게 풀 수 없을까 고민.

 

1. 우선 변수를 줄인다. --> 리스트에 담는다.

2. 반복문을 돌릴 때 list의 요소를 하나씩 꺼내 1260과 비교해 본다.

3. 빼주는 것이 아니라 몫의 개수를 하나씩 저장

4. 받은 돈과 거스름돈의 나머지를 구함.

 

pay = 1260

coin_list = [500, 100, 30 ,10]
coin_count = 0

for coin in coin_list:
  coin_count += pay//coin
  pay %= coin 
  
print(coin_count)

6

 

 와우 너무 쉽다!

시간 복잡도는 화폐 단위의 개수인 k이다!

O(k) 받는 돈은 no 상관

 

 하지만 항상 이런 유형의 문제가 "당장 좋은 것" 고르는 그리디 알고리즘이 먹히는 것은 아님.

대부분의 문제는 그리디 알고리즘을 이용했을 때 '최적의 해'를 찾을 수 없을 가능성이 다분하다.

 

문제의 해법을 찾았을 때는 그 해법이 정당한지 검토해야 한다. 거스름돈 문제를 그리디 알고리즘으로 해결할 수 있는 이유가 있다.

위 문제는 큰 단위가 작은 화폐의 단위들이 항상 배수이기 때문에 가능함. (아니라면 다이나믹 프로그래밍을 이용. 추후에 다룸.)

예를 들어 거스름돈이 800원일 경우이고 거스름돈이 단위가 500 , 400, 100일 경우,

400 두 개로 거스르는 것이 가장 최적이 됨. 그렇다면 가장 큰 화폐의 단위로 먼저 나눠주는 그리디 방법이 통하지 않음

대부분 그리디 알고리즘 문제는 최소한의 아이디어를 떠올리고 정당한지 검토할 수 있어야 함.

 

코딩테스트에서  유형 파악이 안 될 시 "그리디 알고리즘"을 의심.  만일 오랜 시간 고민해도 찾을 수 없으면, 다이나믹 프로그래밍, 그래프 알고리즘을 이용한다.

 

처음 만났을 때 다양한 아이디어를 고려. 

가장 먼저 '10원 자리로만 모두 거슬러주면 어떻게 되지' -> '최적의 해를 구할 수 없겠구나!'

또 다른 문제 풀이 방법을 하나씩 곰곰이 생각해보다보면 결국 '가장 큰 500원 짜리부터 거슬러서 ~'가 나오게 됨.