그리디 알고리즘

● 그리디 알고리즘
 - 각 단계에서 가장 최적인 선택을 하는 알고리즘
 - 각 단계의 최적인 선택이 최종적으로 최적인 선택이 아닐수도 있음

 

// 문제: 주어진 동전들로 특정 금액을 만드는데 필요한 최소 동전 수를 구하는 함수를 작성하세요.
public int MinCoins(int[] coins, int amount)
{
    Array.Sort(coins);
    int count = 0;

    for(int i = coins.Length - 1; i >= 0; i--)
    {
        while(amount >= coins[i])
        {
            amount -= coins[i];
            count++;
        }
    }

    if(amount > 0) return -1; 

    return count;
}

// 시간 복잡도는 O(n)
// 공간 복잡도는 O(1)