[알고리즘] 그리디 (Greedy)

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

• 탐욕 알고리즘, 욕심쟁이 기법이라고도 함
  ✔ 탐욕적 : 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 지금 당장 최적인 답을 선택하는 과정을 반복하여 결과를 도출하는 알고리즘

❗ 문제점 ❗
그 순간 가장 최선의 선택을 하는 기법이기 때문에 최종적인 결과에 대해서는 최적의 해를 보장할 수 없다.

성립해야 하는 2가지 조건

• 항상 최적해가 되지 않으므로 특수한 조건이 만족되어야 사용할 수 있다.

1. 탐욕스런 선택 조건: 앞의 선택이 이후의 선택에 영향을 주지 않음
2. 최적 부분 구조 조건 : 매 순간의 최적의 해가 문제 전체에 대한 최적 해여야 함

그리디 알고리즘을 적용하여 최적해를 구할 수 있는 문제는 위의 두 조건을 만족한다.
위의 2가지 조건을 만족할 때 그리디 알고리즘이 잘 작용하고, 이 조건들을 만족하지 못하면 최적해를 구하지 못하고 근삿값은 구할 수 있음

장점

• 항상 최적의 결과를 도출하는 것은 아니지만 어느 정도 최적의 해에 근사한 값을 빠르게 구할 수 있음 (속도 빠름)

문제 해결 방법

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

예시 문제

💡 거스름돈 문제
당신은 음식점의 계산을 도와주는 점원입니다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원 동전이 무한개 존재합니다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러주어야 할 동전의 최소 개수를 구하라. 단, 거슬러 줘야 할 돈 N은 항상 10의 배수이다.

• 가장 큰 단위의 돈부터 생각하자
• 최소 개수를 구하는 문제이므로 가장 큰 단위부터 거슬러주고 나머지를 그 다음 단위의 화폐로 거슬러 주는 것

def solution(money):
	answer=0
	arr = [500, 100, 50, 10]
	remain = money
	for coin in arr:
		answer += remain // coin		
		remain %= coin
	
	return answer