Greedy Algorithm

Greedy Algorithm 은, 그때 그때의 최선을 택하는 방법으로 진행하는 알고리즘이에요. 

 

전과 후를 생각하지 않고 당장 최선의 결과를 낼 수 있는 방향으로 진행됩니다. 

 

어떠한 경우에는 순간순간의 앞을 내다보지 않는 선택을 통해 실제로도 최고의 결과값을 가질 수 있지만, 그렇지 않을 때도 있기 때문에 Greedy Algorithm 을 사용해도 될지 먼저 판단하는게 중요해요. 

 

'Greedy' 라는 단어의 어감이 그리 좋게 느껴지지 않으실 수는 있겠지만, 종종 매우 효율적이고 간단한 답을 낼 수 있는 방법 중 하나에요.

 

Dynamic programming 처럼 optimization problems 를 풀 때 사용되기도 하지만, Dynamic 과 크게 다른 점 하나는 훨씬 간단하다는 거죠. 

 

Dynamic programming 에서는 큰 덩어리를 여러개로 쪼개는 Recursion 이 사용되지만, greedy Approach 에는 나누는 그런거 없습니다.

 

Greedy Algorithm 은 그 순간 순간에 최선의 선택을 내리는 방식을 계속 진행하여 정답에 도달합니다.

 

즉, 위에서 한번 언급했지만 내리는 최선의 선택들로 인해 도달하는 마지막 결과도 정말 최고의 결과인지를 알아야합니다.  

 

 

 

많이 사용되는 예시는 '거스름돈' 입니다. 

 

사람들은 보통 거스름돈을 가장 적은 수의 화폐로 받고 싶어하기 때문에,

첫째 목표는 정확한 액수의 거스름돈을 주는 것

둘째 목표는 가장 적은 수의 화폐를 거슬러 주는 것 

이라고 정의할 수 있습니다. 

 

이제 동전을 거슬러 주는 상황에서의 logic 을 하나하나 들여다보겠습니다.

1. 줄 수 있는 가장 큰 화폐가 어떤 것인지 확인합니다. (이 과정을 selection procedure 라고 합니다.)

2. 그 지폐를 거스름돈에 포함했을 때 줘야 하는 금액을 초과하지 않는지 확인합니다. ( feasibility check )

3. 만약 초과하지 않는다면, 해당 지폐를 줄 거스름 돈 set 에 포함시킵니다. 

4. 줄 거스름 돈 set 에 있는 액수와 줘야하는 거스름돈의 가격 (값) 이 같은지 확인합니다. (solution check)

5. 만약 같지 않다면, 위 과정 (1 ~ 4) 를 같을 때까지 , 혹은 돈이 바닥날 때까지 반복합니다. ( 돈이 바닥나는 경우 주어야 하는 돈을 줄 수 없습니다 .. )

 

 

이 거스름돈 문제에서, 만약 줄 수 있는 거스름돈의 종류가 10, 50 이라면 Greedy Algorithm 을 통해 구한 답은 항상 최적의 값입니다.  하지만, 만약 종류가 [10, 30, 40, 50] 이라면 그렇지 않습니다.

 

예를 들어 줘야하는 액수가 70원, 줄 수 있는 동전이 10원, 30원, 40원, 50원 일때의 Greedy Algorithm 을 통해 해를 구해보겠습니다.

 

1. 한번에 줄 수 있는 가장 큰 지폐는 50원 입니다. 50원을 추가했을 때 70원을 넘지 않으므로, 줄 동전 set 에 포함시킵니다.

2. 아직 줄 동전 set의 합과 줘야하는 액수가 같지 않기 때문에 다시 동전을 바라봅니다.

3. 40, 30 원을 준다면 줘야하는 동전을 초과합니다.

4. 10원을 더 줘도 줄 동전 set 가 줘야하는 동전의 액수를 넘지 않기 때문에 10원을 set 에 포함시킵니다.

5. 아직 줄 동전 set의 합과 줘야하는 액수가 같지 않기 때문에 다시 동전을 바라봅니다.

4. 10원을 더 줘도 줄 동전 set 가 줘야하는 동전의 액수를 넘지 않기 때문에 10원을 set 에 포함시킵니다.

5. 줄 동전 set 는 50원, 10원, 10원 이며 더한 값이 줘야 하는 동전과 값이 같기 때문에 과정을 종료합니다.

 

 

Greedy Algorithm 으로 구한 최적 해는 50, 10, 10 이지만 실제 최적 해는 40, 30 이므로 이 경우 Greedy Algorithm 을 통한 해는 최적해가 아닙니다. (not Globally optimal)