알고리즘 - Greedy (탐욕 알고리즘, 욕심쟁이 알고리즘), 최적해 찾기

Greedy Alogrithm 

Greedy는 사전적인 의미로 '탐욕스러운', '욕심많은' 이라는 뜻을 가지고 있다. 

탐욕 알고리즘 또는 욕심쟁이 알고리즘 라고도 불린다. 

미래를 생각하지 않고 선택의 순간마다 당장 눈앞에 보이는 최적의 선택을 하는 기법

각 단계에서 최선의 선택을 한 것이 전체적으로도 최선이길 바라는 알고리즘

 

 

 

그리디 알고리즘 해결 방법

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

 

그리디 알고리즘 조건

그리디 알고리즘을 적용하기 위해서는 2가지 조건을 성립해야 한다.

 

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

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

 

위의 2가지 조건이 성립하지 않는 경우에는 최적해를 구하지 못한다.

그럼 위의 조건이 성립하지 않는다면 그리디 알고리즘을 사용하지 못할까?  아니다. 

그리디 알고리즘은 항상 최적의 결과를 도출하지는 않지만, 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있다.

 

 

그리디 알고리즘 예시

민지가 마트를 가서 라면과 아이스크림을 샀다. 총 6120원이 나왔다. 
계산을 하기 위해 7000원을 냈다. 민지는 거스름돈을 싫어해서 최소한으로 거슬러 달라고 하였다. 
이 때, 마트 사장님은 어떻게 거슬러 줘야할까? 

 

동전은 500, 100, 50, 10원이 있다고 가정한다. 

• 거스름돈 880원을 채우기 위해서 먼저 가장 큰 500원짜리 동전을 한 개를 선택한다. (두 개는 1000원이 되므로 X)
• 그 다음은 100원짜리 동전을 세 개 선택한다.
• 그다음엔 50원짜리 동전 세 개와 10원짜리 동전 세 개를 선택할 것이다.

 

 

 

그리디 알고리즘 해결 방법 절차와 비교

1. 선택 : 거스름돈 범위 안에서 가장 큰 동전을 우선 선택한다. 
2. 적절성 검사 : 1번 과정을 통해 동전들의 합이 거스름돈을 초과하는지 검사를 한다. 만약, 초과하면 가장 마지막에 선택한 동전을 빼고,                       1번으로 돌아가 더 작은 동전을 선택한다. 
3. 해답 검사 : 선택된 동전들이 거스름돈과 일치하는지 검사한다.