1. 그리디 알고리즘(탐욕법)

개념

• 정의: 현재 상황에서 지금 당장 좋은 것만 고르는 방법
• 언제 사용?: 여러가지 선택지가 있고, 선택지를 골라서 최적의 방법을 찾는 문제에서 생각해봐야함
• 핵심: 단순히 가장 좋아 보이는 것만 선택해도 최적의 해가 도출되는지를 검토해야함
• 예시: 루트 노드부터 거쳐 가는 노드 합이 최대가 되도록 하는 해 찾기

그리디 알고리즘을 선택하여 가장 큰 노드만 찾아서 탐색을 하도록 진행하면 최적해가 나오는지 검토

그리디 기법	정답
5 -> 10 -> 4 = 19	5 -> 7 -> 9 = 21

 

해당 문제는 그리디가 아님

일반적인 상황에서 그리디는 최적의 해를 보장할 수는 없음

하지만 코테에서는 대부분의 그리디 문제는 탐욕법으로 얻은 해가 최적의 해가 되는 상황을 만듬

 

 

문제

거스름 돈

 

최적의 해를 구하기 위해서 가장 큰 화폐 단위부터 돈을 거슬러 줌

 

정당성 분석

가장 큰 화폐 단위부터 돈을 거슬로 주면 왜 최적의 해가 보장이 될까?

• 큰 단위가 항상 작은 단위의 배수이므로 == 작은 단위를 조합해도 다른 해가 나올 수 없기 때문
• 만약, 화폐 단위가 500원, 400원, 100원 인 경우를 가정
  • 작은 단위인 400원이 큰 단위인 500원의 배수가 아니므로, 작은 단위를 조합하면 다른 해가 탄생
  • ex) 800원

 

코드

시간 복잡도: 동전의 개수(k) 만큼 반복 -> O(k) -> n의 크기와 무관

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();

        // 큰 단위 화폐부터 차례로 확인
        int[] coins = {500, 100, 50, 10};

        int count = 0;
        for(int coin : coins){
            count += n / coin; //해당 화폐로 거슬러 줄 수 있는 동전 개수 세기
            n = n % coin;
        }

        System.out.println(count);

    }
}