그리디 (Greed) 알고리즘

탐욕법으로 매순간 주어지는 상황에 가장 답이 될것같은 해를 선택하는 방식의 알고리즘

 

수행과정

① 현재 상태에서 가장 좋은 해를 선택

② 선택된 해가 문제의 조건에 벗어나진 않는지 확인

③ 현재까지의 선택한 해(집합) 이 전체적인 문제를 해결할수 있는지 확인하며,

 해결되지 않을것같다면 ① 로 다시 되돌아간다.

 

위의 표처럼 각 화폐로 800원을 만들되, 가장 적은 수량의 화폐로 800원을 만들어야한다라고 가정해보자.

가장 큰 단위의 화폐부터 확인해보면,

 

800원을 만들수있는 가장큰 단위의 화폐는 500원으로 확인된다.

그리디한 방식으로 바로 500원을 선택해준다.

이후 만들어야 하는 금액은 300원으로 500원으로는 300원을 초과하기에 적합하지 않다.

다음으로 큰화폐를 조회하며 탐색을 이어간다.

 

문제 https://www.acmicpc.net/problem/11047

11047번: 동전 0

 

풀이

int[] input = Array.ConvertAll(Console.ReadLine().Split(' '),int.Parse);

int target = input[1];
int[] coins = new int[input[0]];

for (int i = 0; i < coins.Length; i++)
{
    coins[i] = int.Parse(Console.ReadLine());
}

int idx = coins.Length-1;
int count = 0;

while (true)
{
    if(target == 0 || idx < 0)
        break;

    if(coins[idx] > target)
    {
        idx--;
        continue;
    }

    while (true)
    {
        if(coins[idx] > target)
            break;

        target -= coins[idx];
        count++;
    }
    
    idx--;    
}

System.Console.WriteLine(count);

 

미흡하거나 개선될수있는 부분이 있으면 답글남겨주세요