Greedy

Greedy

최적의 해에 가까운 값을 구하기 위해 사용된다.
여러 경우 중 하나를 결정해야할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서 최종적인 값을 구하는 방식이다.

예제

1) 동전 문제

지불해야 하는 값이 4720원 일 때 1원,50원,100원,500원 동전으로 동전의 수가 가장 적게 지불하는 방법을 구하시오.

• 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현한다.

    public List<Integer> solution(int price, List<Integer> coinList) {
        int coinNum = 0;
        List<Integer> details = new ArrayList<>();

        for (Integer i : coinList) {
            coinNum = price / i;
            price -= coinNum * i;
            details.add(coinNum);
        }

        return details;
    }

    public static void main(String[] args) {
        final Coin T = new Coin();
        List<Integer> coinList = new ArrayList<>(Arrays.asList(500, 100, 50, 1));
        int number = 4720;

        System.out.println(T.solution(number, coinList));
    }

2) 부분 배낭 문제

무게 제한이 K인 배낭에 최대 가치를 가지도록 물건을 넣는 문제
각 물건은 무게(w)와 가치(v)로 표현될 수 있다.
물건은 쪼갤 수 있으므로 물건의 일부분이 배낭에 넣어질 수 있다.

    public double solution(int[][] knapsackList, double capacity) {
        double totalValue = 0.0;
        double fraction = 0.0;

        Arrays.sort(knapsackList, (o1, o2) -> (o2[1] / o2[0]) - (o1[1] / o1[0]));

        for (int[] knapsack : knapsackList) {
            if ((capacity - (double) knapsack[0]) > 0) {
                capacity -= knapsack[0];
                totalValue += knapsack[1];
                continue;
            }
            fraction = capacity / (double) knapsack[0];
            totalValue += (double) knapsack[1] * fraction;
            break;
        }
        return totalValue;
    }

탐욕 알고리즘의 한계

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