[python/자료구조] 그리디 알고리즘

 

 

그리디 알고리즘(Greedy Algotirhm) 이란?

---

현재 상황에서 지금 당장 좋은 것만 고르는 방법을 말한다.

최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 한다.

 

 

---

 

 

< 연습문제 >

Q. 거스름 돈

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

 

A.

  
  n = 1260
  count = 0

  array = [ 500, 100, 50, 10 ]

  for coin in array:
      count += n // coin
      n %= coin

  print(count)
  

-> 거스름 돈이 1,260원일 때, array리스트(동전)의 500, 100, 50, 10을 차례대로 불러온다.

거스름 돈을 동전으로 나누고 몫은 count, 나머지는 n에 넣어 초기화한다.

시간복잡도는 O(K)로 동전의 총 종류에만 영향을 받는다.