[알고리즘] 16. 그리디 알고리즘

1. 정의

탐욕 알고리즘!!

500, 100, 50, 10 (800원)

500 1개 100 3개

500 1개 100 2개 50 개 10 개

2. 커스터 마이징 이유 (오류)

500, 400, 10 (800원)

500 1개, 10원 30개

400 2개

3. 다이나믹 프로그래밍 (기법)

작은 문제부터 해결해 나가는 프로그래밍
Divide And Conquer와 비슷할 수 있으나, 반복 문제가 계속 나온다는 점과
반복 문제는 항상 같은 결과가 나온다는 점을 활용하여 해결하는 프로그래밍

Memoization을 활용하여 계산 결과를 저장하고 사용

4. 노가다

1. 그리디 알고리즘으로 800원의 최소 동전 개수 구하기

• 500원, 100원, 50원, 10원 동전이 있음
• 500원과 100원만 사용하면 최소 개수가 구해짐 : 그리디 알고리즘의 대표적 문제
• 가장 큰 수부터 나눈 나머지를 활용해 최소 개수를 계산
• 문제점 : 단위 별로 중간/최소 금액이 없을 경우 해당 알고리즘으로 해결할 수 없을 수 있음

public class Ex01 {

    public static void main(String[] args) {

        // greedy algorithm
        // 최소 동전의 개수
        int[] coins = {500, 100, 50, 10};
        int price = 800;
        int change = 0;

        int[] counts = new int[coins.length];

        // hard coding

        for (int i = 0; i < coins.length; i++) {
            // 1회만 price로 카운트 추가
            if (i == 0) {
                counts[i] = price / coins[i];
                change = price % coins[i];
            } else {
                counts[i] = change / coins[i];
                change = change % coins[i];
            }
        }


        System.out.println("동전 개수 : ");

        for (int k = 0; k < coins.length; k++)
            System.out.println(coins[k] + "원 = " + counts[k]);


    }
}

2. 동전의 종류 변경

• 500원, 400원, 10원
• 종류가 바뀌면서 그리디 알고리즘이 적용되지 않음
• 800원을 줘야 하는데 500원을 먼저 줄 경우 최소 개수가 맞지 않음
• 다른 동전으로 줄 때의 경우를 생각하며 모든 경우를 테스트해보고, 최적의 결과를 비교를 통해 얻어야 함
• 비교를 위해서는 결과 저장이 필요 (Memoization)
• 개수를 세고 값을 저장하는 작은 과정을 반복
• 해당 과정을 반복할 때 서로 다른 예상값이 나오면 안 됨 (Dynamic Programming)
• 값 자체가 달라야 한다는 뜻이 아닌, 똑같은 계산 과정을 통해 답이 나올 수 있어야 함

import java.util.HashMap;
import java.util.Map;

public class Ex02 {

    public static void main(String[] args) {

        // greedy algorithm : error
        // 동전의 변화
        int[] coins = {500, 400, 10};
        int price = 800;
        int change = 0;

        int[] counts = new int[coins.length];

        Map<Integer, Integer[]> result = new HashMap<>();

        // hard coding
        /*
         * 똑같이 수행을 했는데 오류 발생
         * 최소 동전은 400원 2개가 제일 적은데, greedy 알고리즘으로는 10원이 30개가 생겨버림
         * 수행 결과를 저장 후 비교할 비교군이 필요
         * 또한, 결과들을 단계를 올려가며 모두 독립 시행이 필요
         * */

        for (int k = 0; k < coins.length; k++) {
            // 초회
            for (int i = k; i < coins.length; i++) {
                // 1회만 price로 카운트 추가
                if (i == k) {
                    counts[i] = price / coins[i];
                    change = price % coins[i];
                } else {
                    counts[i] = change / coins[i];
                    change = change % coins[i];
                }
            }
            // 첫 계산 결과 저장
            // counts 저장 필요
            result.put(k, new Integer[]{counts[0], counts[1], counts[2]});
            // counts 초기화
            counts = new int[coins.length];
        }

        // 결과 비교
        int minCount = 0;
        int correctIndex = 0;

        for (int i = 0; i < coins.length; i++) {
            if (minCount == 0) {
                minCount = result.get(i)[0] + result.get(i)[1] + result.get(i)[2];
            } else {
                if (result.get(i)[0] + result.get(i)[1] + result.get(i)[2] < minCount) {
                    minCount = result.get(i)[0] + result.get(i)[1] + result.get(i)[2];
                    correctIndex = i;
                }
            }
        }

        // 정답이었던 배열 꺼내기
        Integer[] correctCounts = result.get(correctIndex);

        System.out.println("동전 개수 : ");

        for (int k = 0; k < coins.length; k++)
            System.out.println(coins[k] + "원 = " + correctCounts[k]);
    }
}