[Algorithm] Greedy Algorithm(탐욕 알고리즘)

🎯 목표 : 탐욕 알고리즘을 이해하고 예제 문제를 풀수 있다.

📒 Greedy Algorithm

📌 탐욕 알고리즘

• 알고리즘 문제 해결을 위해 재귀 호출과 똑같이 여러 개의 조각으로 문제를 쪼개고 각 단계별 답의 한 부분을 만들어 간다.
• 모든 선택지를 고려하고 각 단계별로 지금 당장 가장 좋은 방법만을 선택하도록 설계한다.
• 지금 당장의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지 고려하지 않는다.
• 실제로 탐욕 알고리즘으로 구현한 문제 해결 방법이 직관적이지 않기 때문에 실수에 유의해야하고 문제 해결 과정에서 알고리즘의 정당성을 증명하는 과정은 필히 연습 해 봐야될 과제다.

---

📌 조건

• 탐욕적 선택 속성 - 앞의 선택이 이후의 선택에 영향을 주지 않는다.
• 최적 부분 구조 - 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.
• 위의 조건이 성립하지 않더라도 근사 알고리즘으로 사용이 가능할수도 있고, 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있다.
• 최적 해답에 가까운 해를 구할 수 있는지 보장하기 위해 정당성을 증명해야 한다.

---

📌 예제

• 탐욕 알고리즘의 대표적인 예로 거스름돈의 동전 개수를 최소한으로 거슬러주는 경우를 찾는 문제가 있다.
• 500, 100,50,10,5,1 동전이 무한정으로 있다 가정하고, 거슬러 줘야될 돈에 대한 최소한의 동전의 갯수를 구하는 예제를 작성했다.
• 거슬러 줘야 될 돈이 4,000원이라 가정하면, 500원짜리 8개를 이용해 거슬러 주는 것이 가장 최소의 동전의 갯수로 거슬러 주는 경우다. 4,170원이라고 가정하면, 500원짜리 8개 100원짜리 1개 50원짜리 1개 10원짜리 두개를 거슬러 주는 것이 가장 최적해로 볼수 있다.

---

📌 예제 코드

    public int changesCoin(int changesMoney) {
        int [] coin = new int[]{500,100,50,10,5,1};
        if(changesMoney%coin[0]==0) return k/coin[0];
        int change = changesMoney;
        int coinCount =0;
        for (int j : coin) {
            while ((change - j) >= 0) {
                change -= j;
                coinCount++;
            }
        }
        return coinCount;
    }

• 거슬러 줘야될 돈을 매개 변수로 받는다.
• 인자로 들어온 금액이 가장 가치가 큰 동전이 500원으로 나누어 떨어지면 해당 갯수를 반환해준다.
• 그렇지 않다면, 동전들의 배열만큼 반복을하며, 가장 큰 금액 500원으로 나누어 남은 금액을 다시 change에 정의해주고, 몫을 coinCount에 정의해준다.
• 다음 금액인 100원으로 나누어 주고 몫과 나머지를 각 변수에 정의해준다. 위 과정을 반복 하다보면 나머지가 0이 되는 경우가 오게되고, 그 경우까지 카운팅 된 동전의 갯수가 최적해라고 할수 있다.
• 이와 같은 문제 구조를 매트로이드라 한다, 탐욕 알고리즘을 사용 하더라도 언제든지 최적해를 찾아 낼수 있다.