그리디 알고리즘

매 순간마다 최적의 선택을 하는 알고리즘
예를 들어 거스름돈을 동전으로 줄 때를 가정해보면, 가장 적은 수의 동전갯수로 거스름돈을 주려면 그리디 알고리즘은 매 순간마다 가장 큰 동전을 사용한다.

public static int minCoins(int[] coins, int target) {
    Arrays.sort(coins); // 동전들을 오름차순으로 정렬
    int count = 0;
    for (int i = coins.length - 1; i >= 0; i--) { // 큰 수부터
        while (target >= coins[i]) {
            target -= coins[i]; // 남은 거스름돈 차감
            count++;
        }
    }
    return count;
}