그리디(탐욕법) 알고리즘에 대해 알아보자!

 

그리디 알고리즘이란?

<출처: https://yganalyst.github.io/assets/images/algorithm/concept_greedy_1.png>

• 그리디 알고리즘이란 우리말로 탐욕법, 탐욕 알고리즘, 욕심쟁이 알고리즘 등 여러가지 말로 불립니다.
  이는 눈 앞에 있는 것이 더 좋아보이면 그것을 추구하는 알고리즘입니다. 대표적인 예시를 들어보겠습니다.
  
  
• <예시> 
  : 상품에 대한 가격이 매개변수로 주어집니다. 그리고 서로 다른 금액의 동전이 들어있는 1차원 배열이 주어집니다. 상품을 주어진 배열의 동전으로 계산하려고 할 때 지불해야하는 동전의 개수의 최솟값을 리턴해야 합니다.

void Start()
    {
        int[] coins = { 10, 500, 50, 100 };
        Debug.Log(Greedy_Price(1990, coins));
    }
    public int Greedy_Price(int price, int[] coins)
    {
        int answer = 0;
        
        Array.Sort(coins);
        
        for (int i = coins.Length - 1; i >= 0; i--)
        {
            int cntCoin = price / coins[i];
            price -= cntCoin * coins[i];
            answer += cntCoin;

            Debug.Log(coins[i] + " = " + cntCoin + "개");
        }

        return answer;
    }

• 이렇게하면 500원을 최대한 사용하는 경우의 지불한 동전의 개수를 알 수 있습니다. 이렇게 그리디 알고리즘은 근시안적인 방법으로, 매순간 최적이라고 생각되는 값을 선택하는 알고리즘입니다.
  
  
• 그러나 현실적으로 동전이 그럴수는 없지만 만약에 주어진 동전이 10,80,100원인 경우 160원의 상품을 구매한다고 하면??
  위 코드처럼 진행한다면 100원 1개, 10원 6개로 총 7개의 동전을 지불하게 됩니다. 하지만 100원 0개, 80원을 2개로 총 2개의 동전을 지불하면 이전보다 더 적은 개수의 동전으로 상품을 구입할 수 있게 됩니다.
  
  
• 제가 생각하는 그리디 알고리즘은 퀵 정렬과 같이 불안정한 방법입니다. 매순간 선택한 최적의 값이 전체 결과의 최적의 값과 다를 수 있다고 생각하기 때문입니다. 하지만 그리디 알고리즘으로 풀었을 때 문제의 최적의 해를 보장하는 경우에는 그 어떤 알고리즘보다 빠른 방법이라고 생각합니다.

<참고자료1>

https://www.youtube.com/watch?v=_IZuE7NIeW4&pp=ygUW6re466as65SUIOyVjOqzoOumrOymmA%3D%3D

 

 

<참고자료2>

https://geukggom.tistory.com/173

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