[Java Algorithm] 탐욕 알고리즘 (Greedy Algorithm)

💡 탐욕 알고리즘 이란?

탐욕 알고리즘은

(Greedy : 욕심이 많은, 탐욕스러운 의 뜻)을 가진 알고리즘 이며, 최적해를 구하는 데에 사용되는 근사적인 방법이다.

 

여러  경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다. 하지만 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.

위와 같이 시작지점에서 가장 큰 수를 찾는 문제가 있다고 가정해 보자.

 

우리는 10을 찾아가기 위해서 시작지점에서 1 -> 10 이라는 결과를 도출해 낼 테지만 그리디 알고리즘은 위와 같이 5 -> 4로 판단을 해버린다. 

 

따라서! 이러한 이유 때문에 그리디 알고리즘은 아래 설명할 탐욕 알고리즘을 적용하기 위한 조건을 모두 만족해야한다.

 

✏️ 요약 : 탐욕 알고리즘은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 알고리즘이다. 

 

 

---

💡 탐욕 알고리즘 문제를 해결하는 방법

1. 선택 절차 : 현재 상태에서 최적의 해답을 선택한다.

2. 적절성 검사 : 선택된 해가 문제의 조건을 만족하는지 검사한다.

3. 해답 검사 : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

 

---

💡 탐욕 알고리즘을 적용하기 위한 조건

탐욕스런 선택 조건과 최적 부분 구조 조건이라는 두가지 조건이 만족해야한다.

- 탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것

- 최적 부분 구조 조건은 문제에 대한 최적해가 부분 문제에 대해서도 역시 최적해라는 것

 

📌 위의 조건이 만족 하지 않을 때는 탐욕 알고리즘을 통해 최적 해를 구할 수 없다.

하지만 이러한 경우에 근사 알고리즘(Approximation Algorithm)을 통해 해를 구할 수 있다.

 

---

📍 근사 알고리즘(Approximation Algorithm) 이란?

최적화 문제에 대한 해의 근사값을 구하는 알고리즘이다.

근사 알고리즘은 가장 최적화되는 답을 구할 수는 없지만, 비교적 빠른 시간에 계산이 가능하며 어느 정도 보장된 근사해를 계산할 수 있다.

 

---

💻 탐욕 알고리즘의 예시 (잔돈 거스르는 문제)

마트에서 3,060원짜리 물건을 산 후 5,000원을 내밀며 거스름돈을 요청하였다.

 

❓ 이때 캐셔는 거스름돈을 어떻게 거슬러 주어야 할까?

 

❗️해답 

가장 가치가 높으 500원 5개를 먼저 거슬러 주고 잔액을 확인하고 

100원 4개, 50원 1개, 10원 1개의 순서대로 거슬러 준다.

 

package develope;

public class 거스름돈 {
    public static void main(String[] args) {
        int money = 3060;

        Solution_money sm = new Solution_money();

        for(int t : sm.solution(money)){
            System.out.println(t);
        }
    }
}

class Solution_money{
    public int[] solution(int money){
        int[] m = new int[4];
        int temp = money;
        
        m[0] = temp / 500;
        temp %= 500;

        m[1] = temp / 100;
        temp %= 100;

        m[2] = temp / 50;
        temp %= 50;

        m[3] = temp / 10;
        temp %= 10;

        return m;
    }
}