그리디(Greedy) 알고리즘 :: 마이구미

이번 글은 그리디(Greedy) 알고리즘에 대해 다뤄본다.

그리디 알고리즘은 탐욕 알고리즘, 욕심쟁이 알고리즘으로도 불린다.

그리디 알고리즘은 간단히 정의하자면 아래와 같이 표현할 수 있다.

경우의 수가 존재할 경우, 경우를 선택해야할 때 최선이라고 생각하는 경우를 선택하는 알고리즘이다.

여기서 최선이라고 생각하는 경우가 무엇인가?

그것을 이해하면 그리디 알고리즘을 이해할 수 있다.

쉽게 말하면, 전체를 고려하지 않고, 그 순간에서의 최선을 말한다.

즉, 그때그때 더 좋아보이는 쪽을 선택하는 것이다.

그렇기에 최종적으로는 그 선택이 최적이라고 확신할 수 없다. (문제에 따라 최적이라고 확신할 수도 있다.)

예를 들어, 지금은 초코파이를 먹을 수 있지만, 10분 후면 랍스타를 먹을 수 있다.

그리디 알고리즘의 경우에는 현재에 최선을 다하기 때문에 초코파이를 먹어버리는 느낌이라고 할 수 있다.

그리하여 이름이 탐욕 알고리즘이라고 불리는 것이다.

이번에는 문제를 통해 이해할 수 있게 예를 들어보겠다.

대표적으로 거스름돈을 들 수 있다. (관련 문제 5585번 거스름돈)

타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 갯수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 갯수를 구하는 프로그램을 작성하시오.

거스름돈의 최소 갯수를 구하는 문제이다.

당연히 우리는 생각할 수 있다.

가치가 큰 돈을 우선적으로 주면 된다.

예를 들어, 잔돈을 800엔 받는다고 가정한다면,

최소 갯수의 거스름돈으로 500엔 1개와 100엔 3개로 총 4개로 거슬러 줄 수 있다.

그리디 알고리즘으로 표현하자면, 가치가 큰 돈부터 먼저 거슬러주는 선택을 하는 것이다.

int money = 1000 - sc.nextInt();
int[] array = {500,100,50,10,5,1};
int idx = 0;
int ans = 0;

while(money != 0) {

    int change = money / array[idx];

    money -= change * array[idx++];

    ans += change;
}
System.out.println(ans);

이번에는 그리디 알고리즘이 왜 최종적인 답이 최적이 아닌 경우를 살펴보자.

잔돈으로 400엔을 추가해보자.

int[] array = {500,400,100,50,10,5,1};

위와 같은 그리디 알고리즘으로, 잔돈을 800엔 거슬러주자.

500엔 1개와 100엔 3개 총 4개를 거슬러준다.

하지만 생각해보면 400엔 2개만 거슬러주면 총 2개로 거슬러줄 수 있다.

이렇게 모든 경우에 있어 최적이 아닌 것을 볼 수 있다.

그렇다면 왜 쓰는가? 의문이 들 수 있다.

원래의 거스름돈 문제는 그리디 알고리즘을 통해 해결할 수 있었다.

즉, 그리디 알고리즘은 무조건 최적이 아니라는 것이 아니다.

그리디 알고리즘을 통해서도 최적을 구할 수 있다면 훨씬 효율적으로 사용할 수 있는 알고리즘이다.

왜냐하면, 그때그때 최선을 선택하기 때문에 성능이 빠르기 때문에 실용적이다.

또한 최적을 구하지 못하더라도 근사 알고리즘으로 사용할 수도 있다.

이유 또한 성능이 빠르기 때문에 어느 정도 최적에 가깝게 구하는 근사적인 방법으로 사용 할 수 있다.

글에서 예제로 활용한 문제는 아래 Github URL에서 확인하길 바란다.

그리디 알고리즘 관련 문제들은 본인 블로그의 작성된 다른 글들에서 확인할 수 있다. (그리디 문제 카테고리 링크)

그리디 알고리즘 기본적인 문제 5585번 거스름돈, 11047번 동전 0

https://www.acmicpc.net/problem/5585

https://github.com/hotehrud/acmicpc/blob/master/Greedy/5585.java

https://www.acmicpc.net/problem/11047

https://github.com/hotehrud/acmicpc/blob/master/Greedy/11047.java