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

그리디 알고리즘(탐욕법) : 최적의 해를 구하는 방법으로, 그 상황에서 가장 좋은 것만을 고르는 방법을 의미한다.

---

*그리디는 정당성 분석이 중요*
문제가 요구하는 최적의 해를 구할 수 있는지를 검토해야 한다. 
일반적으로 최적의 해를 구하지 못하는 경우가 더 많다.

예를 들어보자, 

그리디 알고리즘 적용시, 최적의 해

위 그림처럼 생긴 트리의 경우 그리디 알고리즘을 이용해 최적의 해를 구하면 주황색과 같이 72라는 결과가 나온다. 

하지만 위 트리의 경우, 최적의 해는 다음 그림의 파란색으로 110이다.

최적의 해

이와 같이 그리디 알고리즘을 이용해 최적의 해를 구하면 최적의 해가 아닐 수 있기 때문에 꼭 검증이 필요하다. 

---

그리디 알고리즘 예 - 거스름 돈 주기

거스름 돈 문제의 최적의 해는 가장 큰 화폐 단위부터 거슬러주면 되기 때문에 그리디 알고리즘을 사용하면 항상 최적의 해를 가진다. 

다음과 같이 동전이 있다고 생각해보자. 

이 동전들을 이용해서 600원의 거스름돈을 거슬러주는 최적의 해는 무엇일까?

위 그림과 같이 500원 1개와 100원 1개가 최적의 해 일 것이다. 

하지만 이는 동전 중 큰 단위가 항상 작은 단위 배수일때만 성립한다. 

 

만약, 동전 중 큰 단위가 항상 작은 단위의 배수가 아니라면 어떻게 될까?

다음 그림을 보자.

위 그림과 같이 동전의 단위가 500원, 400원, 100원, 75원, 50원이라면 1300원을 거슬러 줘야 하는 상황에 그리디 알고리즘을 적용하면 어떻게 나올까?

위 그림과 같이 500원 2개, 100원 3개로 나오는 것을 볼 수 있다. 

하지만, 이는 최적의 해가 아니다. 아래 그림을 보자. 

1300원을 거슬러주는 최적의 해는 위 그림과 같이 500원 1개, 400원 2개이다. 

---

그렇다면 동전의 큰 단위가 항상 작은 단위 배수일때의 코드를 보자.

 

public class Main {
 
    public static void main(String[] args) {
        int n = 600;
        int count = 0;
        int[] coinTypes = {500, 100, 50, 10};
        
        for (int i = 0; i < 4; i++) {
            int coin = coinTypes[i];
           count += n / coin;
            n %= coin;
        }
 
        System.out.println(count);
    }
 
}

---

<참조>
"이것이 취업을 위한 코딩 테스트다", "나동빈", https://www.youtube.com/watch?v=2zjoKjt97vQ&list=PLRx0vPvlEmdAghTr5mXQxGpHjWqSz0dgC&index=2