[Algorithm] 08. Greedy Algorithm

1. Greedy Algorithm이란?

현재 상태에서 보는 선택지 중 최선의 선택지가 전체 선택지 중 최선의 선택지라고 가정하는 알고리즘

위의 트리구조를 봤을 때, 그리디 알고리즘의 경우는 그 단계단계마다 무조건 제일 큰 쪽, 즉 최선의 선택지를 선택하는 것을 확인할 수 있다.

핵심 이론은 다음과 같다.

1. Solution Procedure:현재 상태에서 가장 최선이라고 생각하는 해를 선택
2. Feasibility Check: 현재 선택한 해가 전체 문제의 제약 조건에서 벗어나지 않는지를 검사
3. Solution Check: 현재까지 선택한 해 집합이 전체 문제를 해결할 수 있는지 검사한다. 전체 문제를 해결하지 못할 시, 1로 돌아가 반복

2. 적용 예시

그리디 알고리즘의 대표적인 예시로는 거스름돈 문제가 있다.

마트에서 계산을 하는 점원이 되었다.
손님에게 거슬러줘야할 돈이 N원일 때 거슬러줘야 할 동전의 최소 개수를 구하라. 이때
거스름돈으로 사용할 동전은 500원, 100원, 50원, 10원으로 무한히 존재하고, N은 10의 배수로 가정

이때, 최소 개수를 구하기 위해서는 '가장 큰 화폐 단위부터' 돈을 거슬러 줘야 한다.
아래가 예시 코드이다.

import java.util.Scanner;

public class Main
{
	public static void main(String[] args) {
	    Scanner sc = new Scanner(System.in);
	    int total = sc.nextInt();
	    int minCoinCnt = 0;
	    int coins[] = {500, 100, 50, 10};
	    
	    for (int coin : coins){
	        minCoinCnt += (total/coin);
	        total %= coin;
	    }
		
		System.out.println("result = " + minCoinCnt);
	}
}