그리디(Greedy) 알고리즘이란?

1. 탐욕 알고리즘 이란?

• Greedy algorithm 또는 탐욕 알고리즘 이라고 불리움
• 최적의 해에 가까운 값을 구하기 위해 사용됨
• 여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종적인 값을 구하는 방식

 

그리디 알고리즘은 항상 최적의 결과를 도출해내는 것은 아니지만 어느정도 최적의 해에 근접하게 구할 수 있다는 장점이 있다.

 

 

2. 탐욕 알고리즘 예

문제1: 동전 문제

• 지불해야 하는 값이 1260원 일 때 1원 50원 100원, 500원 동전으로 동전의 수가 가장 적게 지불하시오.
  • 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식이다.
  • 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 됨

 

가장 큰 동전부터 최대한 지불해야 한다는 것만 지킨다면 최적의 결과를 얻을 수 있다. 

 

출처 : https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221242106787&proxyReferer=https%3A%2F%2Fwww.google.com%2F

 

 

이렇게 동전을 큰 순서대로 내림차순 정렬(sort)를 시킨 후에 가장 큰 동전을 쓸 수 있는 만큼 사용한다.

 

 

출처 : https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221242106787&proxyReferer=https%3A%2F%2Fwww.google.com%2F

 

가장 큰 500원을 사용할 수 있는 만큼 사용한 후에 그 다음에 100원도 위와 똑같이 진행한다.

 

 

출처 : https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221242106787&proxyReferer=https%3A%2F%2Fwww.google.com%2F

 

그 다음에 50원도 똑같이 나눌 수 있는 만큼 나눈다. 

 

출처 : https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221242106787&proxyReferer=https%3A%2F%2Fwww.google.com%2F

 

출처 : https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221242106787&proxyReferer=https%3A%2F%2Fwww.google.com%2F

 

이렇게 500원 2개, 100원 2개, 50원 1개, 10원 1개를 이용해서 1260원을 만들 수 있다.

 

 

 

그러면 동전문제가 왜 탐욕 알고리즘 인가 ? 

이렇게 단순하게 거스름돈을 지불해야 하는 상황에서 큰 동전만을 생각하고 다른 동전은 생각하지 않기 때문에 매순간 최적이라고 생각되는 경우를 선택하는 탐욕 알고리즘이라고 할 수 있다.

 

 
public class Greedy {
    public static void main(String[] args) {
        int n = 1260;
        int count = 0;
 
        count += n / 500;  // 500원이 몇개 가능 한지 여부
        n %= 500;          // 500원 나눠진 개수 만큼 빼고 n에 저장
        count += n/ 100;
        n %= 100;
        count += n / 50;
        n %= 50;
        System.out.println(count);
    }
}

 

따라서 결과는 count = 6이 나오는 것을 알 수 있다. 

 

 

 

3. 탐욕 알고리즘의 한계

• 탐욕 알고리즘은 근사치 추정에 활용된다.
• 반드시 최적의 해를 구할 수 있는 것은 아니기 때문이다.
• 최적의 해에 가까운 값을 구하는 방법 중의 하나이다.

 

 

'시작' 노드에서 시작해서 가장 작은 값을 찾아 leaf node 까지 가는 경로를 찾을 시에

• Greedy 알고리즘 적용시 시작 -> 7 -> 12 를 선택하게 되므로 7 + 12 = 19 가 됨
• 하지만 실제 가장 작은 값은 시작 -> 10 -> 5 이며, 10 + 5 = 15 가 답

 

 

동전 문제에서의 한계 

예를들어 8 6 4 1원이 존재한다고 가정하고 10원을 만들 수 있는 최소 개수를 구하라는 문제가 있다고 해보자.

그러면 그리디(Greedy) 알고리즘을 이용하면 8 1 1 을 이용해서 3개를 이용할 것이다. 하지만 최소의 개수는 6 4로 2개이다. 이렇게 동전 문제에서도 그리디 알고리즘이 항상 최선의 경우는 아니라는 것은 알수있다.

 

하지만 여러 알고리즘에서 많이 쓰이기 때문에 잘 알아두도록 하자.

 

 

 

 

[출처] 

https://m.blog.naver.com/PostView.nhn?blogId=ndb796&logNo=221242106787&proxyReferer=https%3A%2F%2Fwww.google.com%2F

34. 그리디(Greedy) 알고리즘

[출처]

https://www.fastcampus.co.kr/dev_online_algo/

[올인원 패키지] 알고리즘/기술면접 완전 정복 Online | 패스트캠퍼스