[알고리즘] Greedy Algorithm[그리디; 탐욕법]

탐욕법(탐욕 알고리즘)이란 건 기본적으로 최적해를 구하는 데에 사용되는 근사적인 방법이다. 여러 경우 중 하나를 결정해야 할 때마다(=선택의 기로에 설 때마다) 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달하는 방식인데, 지역적으로는 최적일지 몰라도 전역적으로는 최적이라는 보장이 없는 게 일반적인 상황이다. 때문에 탐욕 알고리즘은 지역적으로 최적이면서 전역적으로도 최적인 문제들이어야 사용 가능하다.

---

이런 알고리즘이 가지고 있앞어야 하는 전제는, 각 선택이 다음 선택에는 전혀 무관한 값(all 독립)이어야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미로 해석할 수 있다. 이를 조건으로 바꾸게 되면, 

• 탐욕적 선택 속성 : 앞의 선택이 이후의 선택에 영향을 줘선 안 된다
• 최적 부분 구조(Optimal Structure) : 최종 해결법은 부분 문제에 대한 최적의 방법으로 구성된다. 
• 위 조건이 성립하지 않으면 탐욕 알고리즘은 최적해를 구하지 못한다. 그럼에도 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있다는 장점이 있어, 근사 알고리즘으로는 사용할 수 있다!
  
  • 매트로이드(Matroid) : 어떤 문제의 공간이 매트로이드 구조라면 탐욕법은 그 해를 언제나 구할 수 있다. 그러나 그 역은 성립하지 않는다. 
  • 매트로이드 구조란 일차 독립의 성질을 공리화하여 얻은 조합론적 구조를 의미한다. 꽤나 다양한 곳에서 발견되기 때문에 탐욕 알고리즘의 활용도를 높여 주는 구조.

---

탐욕 알고리즘은 그렇다면 문제를 어떻게 해결할까? 해결 과정은 크게 3단계를 거친다.

1. 선택(할 수 있는 최적의 선택)
2. 적절성 검사(문제 조건에 부합하는지)
3. 해답 검사(검토)

이를 대표적인 예제인 거스름돈 문제 를 들고 와봤는데, 여기에다 적용해보자. 

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

작은 단위부터 생각하게 되면 최소 개수를 구하는 입장에선 정말 머리가 아프므로(N이 1000원인데 10원부터 생각하면 10 * 100, 10 * 95 + 50, .. 이렇게 생각하게 되니까) 큰 덩어리부터 생각해보자. 

 

1. 할 수 있는 최적의 선택은 500원이다. 500원부터 시작하면 된다.

2. 선택한 동전들의 합이 거슬러 줄 금액을 초과하는지 검사해서 피드백을 진행한다. 가령 N이 1000원이라면, 500원은 모자란다. 500원 * 2개 선택하니 딱 1000원에 부합하므로, 더 이상 수정할 필요 없이 이대로 선택하면 되는 것

3. 최종적으로 선택된 동전들의 합이 실제 N(거슬러 줘야 하는 금액)과 일치하는지 확인해보고, 액수가 차거나 넘치면 다시 1로 돌아가 선택을 진행한다. 

---

이를 구현하면 (Python 사용) 아래와 같은 함수로 표현할 수 있다. 

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

그러면 다음 포스트는 다시 프로그래머스로....