Greedy

Table of contents

탐욕 알고리즘 (Greedy Algorithm)

정의

  • 매 선택에서 그 순간 당장 최적인 답을 골라 최종적인 결과에 도달하는 방법

특징

  • 순간마다의 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들이 계속 합쳐져서 최종적(전역적)인 해답을 만들었다고 해도 그것이 최적이라는 보장은 없다.
  • 현재의 선택이 앞으로 남은 선택에 어떤 영향을 끼칠지는 고려하지 않는다.

성질

  1. 탐욕 선택 속성(Greedy Choice Property)
    • 탐욕적으로만 선택을 해도 최적해를 구할 수 있다.
    • 현재 순간의 최적을 한번 선택하면, 이를 번복하지 않는다.
  2. 최적 부분 구조(Optimal Substructure):
    • 전체 문제의 최적해가 각 부분 문제들의 최적해로 이루어진 경우(부분 문제의 최적결과가 전체에도 그대로 적용될 수 있어야 함)
    • ex) 최적 부분 구조를 갖지 않는 경우: 첫 번째 선택을 하고 나서 남는 부분 문제는 최적이 아닌 방법으로 풀어야 하는 경우

원리

  1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다.
  2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다.
  3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

거스름돈 줄이기 문제(Change reduction problem)

정의

  • 최소의 지폐/동전 개수로 거스름돈을 주는 문제

특징

  • MSD(Most Significant Digit) 이용(가장 중요한 단위를 먼저 계산하는 것)
  • 이전의 선택과 관련 없이 현재 상태에서 최선의 결과를 선택하여 전체에서 최적의 결과를 낼 수 있음.

원리

  • 거스름돈의 잔액을 보고 가장 큰 금액의 지폐/동전을 계속해서 고른다.

예시

  • 600원 거슬러 줄 시 (500원->100원->50원->10원 순으로 계산)
    1. 600원 남음. 최적의 선택 = 500원
    2. 100원 남음. 최적의 선택 = 100원
액수 수량
500 1
100 1
50 0
10 0

코드 

#거스름돈을 가장 적은 동전 개수로 지급 (500원 , 100원 , 50원 , 10원) 
list = [0 for i in range(4)] 

sum = int(input("거스름돈을 입력하세요 : "))

while sum != 0 : 
	
  if sum >= 500 : 
		list[0] += 1 
		sum = sum - 500 
	
  elif sum >= 100 : 
		list[1] += 1 
		sum = sum - 100 
	
  elif sum >= 50 : 
		list[2] += 1 
		sum = sum - 50 
	
  elif sum >= 10 : 
		list[3] += 1 
		sum = sum - 10 

print("500원 : ",list[0],"개")

print("100원 : ",list[1],"개")

print("50원 : ",list[2],"개") 

print("10원 : ",list[3],"개")

장점

  • 조건을 만족한다면 현재 상태에서 최선의 결과를 선택하여 전체에서 최적의 결과를 낸다.

단점

  • 가지고 있는 지폐/동전 중에서 큰 단위가 항상 작은 단위의 배수가 아니라면 최적의 결과가 나오지 않을 수 있다.(조건 만족하지 않을 때)
  • ex) 500, 400, 100원으로 1200원 거슬러주기-> 500+400+100+100+100 > 400+400+400

시간복잡도

  • O(화폐의 종류 개수)