[알고리즘/이것이코딩테스트다] 그리디 알고리즘

[그리디 알고리즘]

이 알고리즘은 국내에서 "탐욕법"으로 소개된다.

- 단순하지만 강력한 문제 해결 방법

- 현재 상황에서 지금 당장 좋은 것만 고르는 방법

- 매 순간 가장 좋아보이는 것으로 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다

 

[거스름돈 계산/JAVA] 그리디 문제를 대표하는 문제

(ex) 500원,100원,50원,10원짜리 동전이 존재한다고 할 때, 손님에게 거슬러줘야 할 돈이 N일 때 동전의 최소 갯수는?

package CodingTest;
 
import java.util.Scanner;
 
/*
 * 거스름돈 동전의 최소갯수
 * */
 
public class Test {
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int money = sc.nextInt(); //손님한테 받는 돈
        int count = 0 ; //동전의 갯수
        
        int coin_type[] = {500,100,50,10};
        
        for(int i = 0 ; i<coin_type.length  ; i++) {
            count += money / coin_type[i];
            money %= coin_type[i];
        }
        
        System.out.print(count);
    }
}
 

=> 이 문제에선 가장 큰 화폐 단위부터 돈을 거슬러주는게 핵심!! 

 

이처럼 대부분의 그리디 알고리즘 문제에서는 문제풀이를 위한 최소한의 아이디어를 떠올리고 이것이 정당한지 검토할 수 있어야 답을 도출 할 수 있다

 

 

 

* 출처: 이것이 코딩테스트다