그리디 알고리즘 (Greedy Algorithm)

👩‍💻  그리디 알고리즘 (Greedy Algorithm) 이란?

매 순간 현재 기준으로 최선의 답을 선택해 나가는 기법

• 빠르게 근사치를 계산할 수 있다.
• 하지만 결과적으로 최적해가 아닐 수 있다.

 

✏️ 그리디 알고리즘 예시

1) Activity Select Problem

• N개의 활동과 각 활동의 시작/ 종료 시간이 주어졌을 때,
• 한 사람이 최대한 많이 할 수 있는 활동의 수 구하기

: 매 순간 선택할 수 있는 것 중에 최선을 선택!

 

 

✨but, 그리디 알고리즘은 항상 최적해를 주지 않는다. 아래의 사진이 그 예이다. 

따라서 그리디 알고리즘의 적용 조건을 살펴볼 필요가 있다.

 

 

✏️ 그리디 알고리즘 적용 조건

그리디 알고리즘은 빠르지만, 최적해를 보장하지는 못한다. 따라서 아래의 두 가지 조건에 해당하는 경우 적용 가능한 알고리즘이다.

1. 탐욕적 선택 특성 (Greedy choice property)
   • 지금 선택이 다음 선택에 영향을 주지 않을 때
2. 최적 부분 구조 (Optimal substructure)
   • 전체 문제의 최적해는 부분 문제의 최적해로 이루어짐

위의 "최적 부분 구조" 를 만족하는지 구별하는 예를 위의 거스름돈 문제로 살펴보면,

거스름돈 890을 동전의 개수가 가장 적게 하기 위해서 동전 종류가 10,50,100,500 원이 있다면 이것은 최적 부분 구조를 만족한다.

왜냐하면 100원으로 500원을 이룰 수 있기 때문이다. (10원과 50원도 마찬가지로 100,500원을 이룰 수 있다.)

따라서 이러한 문제는 그리디 알고리즘을 사용할 수 있다.

 

하지만, 동전의 종류가 10,50,100,400,500원이 있다면 위의 예에서 본 것과 같이 그리디 알고리즘이 최적해를 갖지 못한다.

이것은 400원으로 500원을 이루지 못하지 때문이다. 따라서 이러한 경우에는 최적 부분 구조를 만족하지 못하는 경우라고 볼 수 있다.

 

다른 예를 살펴보자.

가장 보편적인 그리디 알고리즘의 예시인 Activity Select Problem에서도 그리디 알고리즘의 사용 조건을 보자면

정렬이 되지 않은 표에서는 2-3시 수업보다 1-5시 수업이 먼저이므로 탐욕적 선택 특성(지금 선택이 다음 선택에 영향을 주지 않음)을 만족하지 못한다.

하지만, 종료 시간 기준으로 정렬한다면 탐욕적 선택 특성을 만족한다. ***

 

 

✏️  Greedy Algorithm 문제 풀이

 

1) Activity Select Problem

import java.util.ArrayList;

class Activity{
	String name;
    int start;
    int end;
    
    public Activity(String name, int start, int end){
    	this.name = name;
        this.start = start;
        this.end = end;
    }
}

public class Main{
	public static void selectActivity(ArrayList<Activity> list){
    	Collection.sort(list, (x1, x2) -> x1.end - x2.end); // 종료시간 기준으로 정렬
        
        int curTime = 0;
        ArrayList<Activity> result = new ArrayList<>();
        for(Activity item : list){ // 빨리 종료되는 순으로 정렬되어 있으므로, 빨리 종료되는 것 먼저 나와서 비교됨
        	if(curTiem <= item.start){
            	curTime = item.end;
                result.add(item);
            }
        }
        
        for(Activity item : result){
        	System.out.print(item.name + " ");
        }
        System.out.println();
    }
}

 

 

2) 거스름돈 문제

public class Main2{

	public static void getChangeCoins(int receivedMoney, int price){
    	final int[] coins = {500, 100, 50, 10, 5, 1};
        HashMap<Integer, Integer> result = new HashMap<>();
        
        int change = receivedMoney - price;
        int cnt = 0;
        
        for(int i=0; i < coins.length; i++){
        	if(change < coins[i]){
            	continue;
            }
            int q = change / coins[i];
            result.put(coins[i], result.getOrDefault(coins[i], 0) + q);
            
            change %= coins[i];
            cnt += q;
        }
        System.out.println("거스름돈 동전 개수 : " + cnt);
        for(Map.Entry<Integer, Integer> cur : result.entrySet()){
        	System.out.println(cur.getKey() + " : " + cur.getValye());
        }
    }
    
}