Greedy Approach(탐욕적 접근)

Basic Concept

---

Charles Dicken’s classic character Ebenezer Scrooge may well be the most greedy person ever, fictional or real. Recall that Scrooge never considered the past or future. Each day his only drive was to greedily grab as much gold as he could. After the Ghost of Christmas Past reminded him of the past and the Ghost of Christmas Future warned him of the future, he changed his greedy ways.

A greedy algorithm proceeds in the same way as Scrooge did. That is, it grabs data items in sequence, each time taking the one that is deemed best according to some criterion, without regard for the choices it has made before or will make in the future.

 

👉 본문에서는 찰스 디킨스의 소설에 나오는 스크루지라는 인물을 탐욕적인 방법과 연결시켜 설명하고 있다. 탐욕적인 방법은 과거나 미래를 고려하지 않고, 현재의 그 순간에서 최선을 결정한다는 점에서 스크루지의 방법과 같다.

 

 

Coin Change Problem

---

A simple example illustrates the greedy approach. Joe, the sales clerk, often encounters the problem of giving change for a purchase. Customers usually don’t want to receive a lot of coins. For example, most customers would be aggravated if he gave them 87 pennies when the change was $0.87. Therefore, his goal is not only to give the correct change, but to do so with as few coins as possible.

 

👉 정확하게 거스름돈을 건네주면서 가능한 코인을 적게 주는 것이 이 문제의 핵심이다. 보통의 고객은 잔돈으로 많은 동전을 받기를 꺼려한다. 잔돈을 거슬러주거나 받을 때 우리는 무의식적으로 탐욕적인 방법을 이미 사용하고 있는 것이다.

 

Algorithm Design

The following is a high-level algorithm for this procedure. In the feasibility check, when we determine that adding a coin would make the change exceed the amount owed, we learn that the set obtained by adding that coin cannot be completed to give a solution to the instance. Therefore, that set is unfeasible and is rejected. An example application of this algorithm appears in the below.

 

Example A greedy algorithm for giving change. The amount owed is 36 cents.

동전 종류	¢25 (quarter)	¢10 (dime)	¢5 (nickel)	¢1 (penny)
Joe가 보유한 코인	1개	2개	1개	2개

 

Step 1 Grap quarter

 

Step 2 Grab first dime

 

Step 3 Reject second dime

 

Step 4 Reject nickel

 

Step 5 Grab penny

 

👉 위의 예제는 주어진 문제에 대하여 탐욕적인 접근 방법을 잘 보여주고 있다. 36센트를 맞춰야 하므로 먼저 가장 큰 25센트를, 그 다음엔 10센트를, 마지막으로 1센트를 잡음으로써 최적의 해답에 도달한다. 
(￠36 = ￠25 ＋ ￠10 ＋ ￠1)

 

Pseudocode

while (there are more coins and the instance is not solved)
{
    // selection procedure
    Grab the largest remaining coin; 

    // feasibility check
    if (adding the coin makes the change exceed the amount owed)
        reject the coin;                
    else
        add the coin to the change;
        
    // solution check
    if (the total value of the change equals the amount owed)
        the instance is solved;
}

 

Drawbacks

Again, the algorithm is called “greedy” because the selection procedure simply consists of greedily grabbing the next-largest coin without considering the potential drawbacks of making such a choice. There is no opportunity to reconsider a choice. Once a coin is accepted, it is permanently included in the solution; once a  coin is rejected, it is permanently excluded from the solution. This procedure is very simple, but does it result in an optimal solution? 

 

Example The greedy algorithm is not optimal if a 12-cent coin is included. The amount owed is 16 cents.

동전 종류	¢12	¢10 (dime)	¢5 (nickel)	¢1 (penny)
Joe가 보유한 코인	1개	1개	1개	4개

 

Step 1 Grap 12-cent coin

Step 2 Reject dime

Step 3 Reject nickel

Step 4 Grap four pennies

 

👉 12센트짜리가 포함된 상태로 16센트를 거슬러줘야 한다. 탐욕 알고리즘으로 얻어진 해답은 ￠16 = ￠12 ＋ ￠1 ＋ ￠1 ＋ ￠1 ＋ ￠1로 동전의 개수가 5개이다. 하지만 최적의 해답은 ￠16 = ￠10 ＋ ￠5 ＋ ￠1이며 동전의 총 개수가 3개 임을 알 수 있다.

결론적으로 탐욕 알고리즘은 항상 최적의 해를 보장하지 못한다. 따라서 알고리즘으로 부터 얻은 결과가 최적의 해답인지를 반드시 검증해야 한다.

 

 

The Greedy Approach

---

Like dynamic programming, greedy algorithms are often used to solve optimization problems. However, the greedy approach is more straightforward. In dynamic programming, a recursive property is used to divide an instance into smaller instances. In the greedy approach, there is no division into smaller instances. A greedy algorithm arrives at a solution by making a sequence of choices, each of which simply looks the best at the moment. That is, each choice is locally optimal. The hope is that a globally optimal solution will be obtained, but this is not always the case. For a given algorithm, we must determine whether the solution is always optimal.

1. A selection procedure chooses the next item to add to the set. The selection is performed according to a greedy criterion that satisfies some locally optimal consideration at the time.
2. A feasibility check determines if the new set is feasible by checking whether it is possible to complete this set in such a way as to give a solution to the instance.
3. A solution check determines whether the new set constitutes a solution to the instance.

 

👉 탐욕 알고리즘은 동적계획법과 마찬가지로 최적화 문제를 해결하는데 사용될 수 있다. 이 방법은 결정을 해야 할 때마다 그 순간에 가장 좋다고 생되는 것을 해답으로 선택함으로써 최종적인 해답에 도달한다.

그 순간의 선택은 그 당시에는 최적이다(locally optimal). 하지만 최적이라고 생각했던 해답들을 모아 최종적인 해답을 만들었다고 해서, 그 해답이 궁극적으로 최적이라는 보장은 없다(globally optimal). 따라서 탐욕 알고리즘이 항상 최적의 해답을 주는지를 반드시 검증해야 한다.