Greedy Algorithm

탐욕 알고리즘, 욕심쟁이 알고리즘 등으로도 불리지만 가능하면 영문명인 그리디 알고리즘이라고 하자. 

Greedy 알고리즘은 위의 '탐욕'이라는 키워드 대로 선택의 순간이 주어질 때마다 당장 눈앞에 보이는 최적의 상황만을 따라가서 최종적인 답에 도달하는 방법을 말한다. 

Greedy 알고리즘으로 문제를 해결하기 위해서는 대략 3 단계별로 구분할 수 있다. 

1. 선택 절차(Selection Procedure)
   - 현재 상태에서의 최적의 해답을 선택한다
   
   
2. 적절성 검사(Feasibility Check)
   - 선택된 답이 문제의 조건을 충족하는지 검사한다.
   
   
3. 해답 검사(Solution Check)
   - 문제가 해결되었는지 검사하고, 해결되지 않았다면 다시 1번인 선택 절차로 돌아가 과정을 반복한다. 

 

---

 

말로만 보면 모든 상황에서 가장 이상적인 알고리즘 같지만 다음의 두 가지 조건을 충족하는 상황이 아니라면, 최적의 결과를 만들지 않는다. 

• 탐욕적 선택 속성(Greedy Choice Property)
  - 앞의 선택이 이후의 선택에 영향을 주지 않는다.
• 최적 구분 구조(Optimal Substructure) 
  - 문제에 대한 최종 해결 방법은, 부분 문제에 대한 최적 문제 해결 방법으로 구성된다. 
  - 즉, 부분적으로 문제를 나눴을때 각 부분에서 최적의 결과를 내야지 최종 결과 또한 최적의 결과가 나온다.

위 조건이 충족하지 않는 상황에서는 그리디 알고리즘으로 최적해를 구할 수 없지만, 그리디 알고리즘은 어느 정도 최적에 가까운 근삿값을 빠르게 구할 수 있다. 이 특성을 이용해서, 그리디 알고리즘을 근삿값을 구하는 알고리즘으로 사용할 수 있다. 

---

그리디 알고리즘의 예시중 하나로, 동전 교환 문제가 있다. 

가게에서 물건을 계산하는 상황에서 거스름 돈의 동전 개수를 최소화해서 받고 싶다고 할 때는, 가장 단위가 큰 동전에서 줄 수 있을 만큼 주고, 다음 단위의 동전, 최종적으로 가장 작은 단위의 동전으로 거슬러 줄 수 있다.

아래의 코드는 실행은 잘 되지만.. 코드가 길어서 그리 좋은 코드는 아니라고 생각한다. 

동전 단위를 배열에다가 집어넣고 반복문으로 처리하는게 더 좋을 듯. 

class Greedy2 {
    public int partTimeJob(int k) {
        // TODO:
        int left = k;
        int coin = 0;       // 해당 동전 개수
        int totalCoins = 0; // 동전 총 개수

        coin = left/500;
        totalCoins += coin;
        left = left - (500*coin);
        if(left == 0) return totalCoins;

        coin = left/100;
        totalCoins += coin;
        left = left - (100*coin);
        if(left == 0) return totalCoins;

        coin = left/50;
        totalCoins += coin;
        left = left - (50*coin);
        if(left == 0) return totalCoins;

        coin = left/10;
        totalCoins += coin;
        left = left - (10*coin);
        if(left == 0) return totalCoins;

        coin = left/5;
        totalCoins += coin;
        left = left - (5*coin);
        if(left == 0) return totalCoins;

        coin = left/1;
        totalCoins += coin;
        left = left - (1*coin);


        return totalCoins;
    }
}