[알고리즘] 그리디(탐욕) 알고리즘

그리디 알고리즘

• 당장(현재 상황)의 좋은 것만 선택하는 알고리즘
• 미래를 생각하지 않고 당장의 선택에서 가장 좋은 선택을 하는 것. 
• 즉, 그리디(탐욕) 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.

그리디 알고리즘 문제를 해결하는 방법

그리디 알고리즘을 적용하려면 다음 두가지 조건을 만족해야 한다. 

탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.

최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

 

탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이며, 최적 부분 구조 조건은 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것이다.

 

탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다. 이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있다.

탐욕 알고리즘을 적용해도 언제나 최적해를 구할 수 있는 문제(매트로이드)가 있고, 이러한 문제에 탐욕 알고리즘을 사용해서 빠른 계산 속도로 답을 구할 수 있다. 그래서 실용적으로 사용할 수 있다.

근사 알고리즘(Approximation Algorithm)이란?

• 근사 알고리즘(approximation algorithm)은 어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘을 의미한다.
• 이 알고리즘은 가장 최적화되는 답을 구할 수는 없지만, 비교적 빠른 시간에 계산이 가능하며 어느 정도 보장된 근사해를 계산할 수 있다.

그리디 알고리즘을 사용하는 문제는 간단한 문제로 나올 가능성이 매우 크다고 할 수 있음.

그리디 알고리즘은 문제를 풀어나가는 방법보다는 이것이 과연 그리디 알고리즘으로 풀 수 있는 문제인지 확인하는 과정이 선행되고 더 중요한 과정.

 

정당성 분석 [가장 중요한 단계]

단순히 가장 좋아 보이는 것을 반복적으로 선택해도 '최적'의 해를 구할 수 있는지 검토해야 한다. 

 

문제 예시 - 거스름 돈 

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.

 

위 문제의 경우에는 가장 큰 화폐 단위 돈부터 거슬러 주는 것이 최적의 해를 보장한다. 

가지고 있는 동전 중에서 큰 단위의 동전은 항상 작은 단위의 '배수'이므로 작은 단위의 동전들을 종합해 다른 해가 나올 수 없기 때문. 

 

이런 경우에 만약 화폐 단위가 500, 400, 100엔이라면 어떻게 될까? -> 최적의 해를 보장하지 못하기 때문에 그리디 알고리즘으로 해결할 수 없을것. 

#얼마짜리 물건을 사는지 입력받기(a변수에)
a = int(input())

#누적 동전 개수
JPY_CoinList = (500,100,50,10,5,1)

#개수를 세주는 함수
def minimum_Coin(value, JPY_CoinList):
#입력을 얼마짜리 물건인지와 동전의 종류가 뭐뭐 있는지를 받는다
  count = 0
  #동전의 개수를 0으로 초기화
  residue = 1000-value
  #거스름돈이 얼마인지 계산(1000엔을 내는 것으로 고정되어 있으니까)
  for i in JPY_CoinList:
    #i가 첫번째면 500, i가 두번째면 100, i가 세번째면 50 등의 순서로 진행하면서 index를 준다
    count += int(residue/i)
    #예를 들어, i가 첫번째인 경우 500원짜리 동전이 몇 개까지 커버가능한지를 센다
    residue -= int(residue/i)*i
    #동전을 센 금액만큼 빼주고 다시 for 루프가 반복될 수 있도록 한다
  return count
  #동전 개수를 몇개인지 return한다

print(minimum_Coin(a, JPY_CoinList))
#함수의 결과를 출력한다

출처: https://blog.tomclansys.com/64 [톰 클란시의 IT 블로그:티스토리]

특징

1. 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많음. 
2. '코딩테스트'에서는 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황에서, 이를 추론할 수 있어야 풀리도록 출제됨.