[JAVA] 그리디 알고리즘(Greedy)의 개념

그리디 알고리즘은 단어 그대로 탐욕법(욕심쟁이) 알고리즘입니다.

여기서 탐욕적이란 말은 '현재 상황에서 지금 당장 좋은 것만 고르는 방법' 을 의미합니다.

매순간 가장 좋아보이는 것을 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 교려하지 않습니다.

 

그리디 알고리즘을 모든 알고리즘 문제에 적용시킬 수는 없지만, 탐욕적으로 문제에 접근했을 때 정확한 답을 찾을 수 있다는 보장이 있을 때에는 매우 효과적이고 직관적 입니다.

 

그리디 알고리즘을 대표하는 문제인 거스름돈 문제를 예로 들어 보겠습니다.

 

거스름돈

당신은 음식점의 계산을 도와주는 점원이다. 카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10월짜리 동전이 무한히 존재한다고 가정한다. 손님에게 거슬러 줘야 할 돈이 N원일 때 거슬러 줘야 할 동전의 최소 개수를 구하라.

단, 거슬로 줘야 할 돈 N은 항상 10의 배수이다.

 

풀이

import java.util.Scanner;

public class ChangeMoney {
	
	public static int changeMoney(int N) {
		int [] change = {500,100,50,10};
		int cnt=0;
		
		for (int i = 0; i < change.length; i++) {
			cnt+=N/change[i];
			N%=change[i];
		}
		return cnt;
	}
	
	public static void main(String[] args) {
		System.out.println("얼마를 거슬러 줘야 합니까?");
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		System.out.println("거슬러 줘야할 동전의 최소 개수는 : "+changeMoney(n)+"개 입니다.");
	}
}

 

핵심은 가장 큰 화폐 단위부터 돈을 거슬러 주는 것입니다.

먼저 500원부터 거슬러 줄 수 있을만큼 거슬러주고 그다음 100원 50원 10원순으로 거슬러준다면 최소의 동전 개수로 

모두 거슬러 줄 수 있습니다.