탐욕(그리디) 알고리즘(Greedy Algorithm)

이번에 배워볼 알고리즘은 탐욕(그리디) 알고리즘(Greedy Algorithm)이다. 탐욕 알고리즘도 다이나믹 프로그래밍처럼 알고리즘이라기보다는 문제를 해결하기 위한 기법이다. 탐욕이란 뜻은 다들 알고 있을 것이다. 탐욕 알고리즘은 말 그대로 미래는 생각하지 않고 현재 주어진 상황에서 최선의 선택을 하는 것을 의미한다.

​탐욕 알고리즘은 다이나믹 프로그래밍보다 빠른 시간 내에 정답에 가까운 근삿값을 구할 수는 있지만 구해낸 답이 다이나믹 프로그래밍처럼 항상 최적해를 보장해 주지 않는다.

왜냐하면 매 순간 최선의 선택이 최종적으로 최선의 선택이 된다고 보장할 수 없기 때문이다. 간단하게 지금 당장 100원을 주는 것과 1분 후 1억을 주는 상황이 있다고 생각해 보자. 만약 탐욕 알고리즘으로 접근한다면 우리는 지금 당장 0원보다 100원을 받는 것이 이득이기 때문에 100원을 받게 될 것이다. 하지만 최선의 선택은 1분 후 1억을 받는 상황이다.

​

최적해를 보장해 주지 않기 때문에 탐욕 알고리즘 또한 사용하기 위한 조건이 있다.

• 탐욕스런 선택 조건(Greedy Choice Property)​ : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
• 최적 부분 구조 조건(Optimal Substructure) : 문제에 대한 최적해가 부분 문제에 대해서도 역시 최적 해이다.

​

탐욕 알고리즘을 이해하고 최적해를 보장해 주지 않는다는 것을 보기 위해 흔히 사용하는 예시가 거스름돈 문제이다. 우리도 거스름돈 문제를 통해 이해해 보자. 거스름돈 문제는 간단하게 거스름돈의 종류가 몇 가지 있을 때 잔돈을 최소의 거스름돈을 사용하여 거슬러주는 문제이다. 다음과 같은 문제가 있다고 하자.

 

10, 50, 100, 500 총 4가지의 동전이 존재할 때 최소의 동전 개수를 사용해서 잔돈 1610원을 거슬러주자

 

탐욕 알고리즘은 현재 상황에서 최선의 선택을 하는 알고리즘이라고 하였다. 따라서 가장 큰 동전부터 사용해서 잔돈을 거슬러주면 된다. 위의 상황에서는 500원짜리 동전 3개, 100원짜리 동전 1개, 10원짜리 동전 1개, 총 5개의 동전을 사용해서 거슬러주게 된다.

다행히도 이 문제에서는 5개의 동전을 사용하는 것이 최적해이다. 하지만 탐욕 알고리즘은 항상 최적해를 보장해 주지 않는다고 하였다. 다른 예시를 통해 알아보자.

 

1, 3, 4, 6 총 4가지의 동전이 존재할 때 최소의 동전 개수를 사용해서 잔돈 20원을 거슬러주자

 

탐욕 알고리즘을 적용한다면 가장 큰 동전부터 사용해서 6원짜리 동전 3개, 1원짜리 동전 2개로 총 5개의 동전을 사용해서 거슬러주게 된다. 과연 이게 최적해일까?

6원짜리 동전 2개와 4원짜리 동전 2개로 총 4개의 동전을 사용해서 잔돈 20원을 거슬러줄 수가 있다. 이처럼 탐욕 알고리즘으로는 거스름돈 문제에서 항상 최적해를 구할 수가 없다.

이를 해결하기 위해선 다이나믹 프로그래밍처럼 다른 기법을 사용해야 한다. 우리는 이전에 다이나믹 프로그래밍을 배웠기 때문에 거스름돈 문제를 다이나믹 프로그래밍을 사용해서 풀어보자.

​

다이나믹 프로그래밍은 항상 최적해를 보장해 준다고 하였다. 따라서 우리는 다음과 같이 1차원 배열을 선언하여 가정할 수 있다.

dp[i] : i원을 거슬러주기 위해 사용되는 동전의 최소 개수

 

만약 i 원을 거슬러주기 위해 사용되는 동전의 최소 개수보다 (i - 동전 A) 원을 거슬러주기 위해 사용되는 최소 개수 + 1(동전 A 원을 한 번 거슬러줌)이 더 작다면 우리는 dp[i]를 갱신할 수 있다. 따라서 다음과 같은 점화식을 도출해낼 수 있다.

for i : 1원 to 6원 (4가지 동전)
    for j : 1원 to 20원 (잔돈)
        if (동전[i] >= 잔돈[j])
            dp[j] = min(dp[j], dp[j - 동전[i]] + 1)

 

거스름돈 문제를 탐욕 알고리즘 & 다이나믹 프로그래밍 기법을 사용하여 Java로 구현한 코드는 다음과 같다.

import java.util.Arrays;

public class Blog {

	static final int INF = (int)1e9;
	static int[] coin = {6, 4, 3, 1};
	static int count_Greedy, count_Dp;


	public static void main(String[] args) {
		System.out.println(getMinCoin_Greedy(0, 0, 20));
		System.out.println(getMinCoin_DP(20));
		System.out.println(count_Greedy + " vs " + count_Dp);
	}

	
	public static int getMinCoin_Greedy(int cnt, int coin_Index, int changes) {
		count_Greedy++;
		
		if (changes == 0) return cnt; //잔돈을 다 거슬러줬으면 사용한 개수 반환
		
		//현재 남은 금액에서 동전을 거슬러 줄 수 있다면
		if (changes - coin[coin_Index] >= 0) {
			return getMinCoin_Greedy(cnt + 1, coin_Index, changes - coin[coin_Index]);
		} 
		//거슬러 줄수없다면 더 작은 동전을 선택
		else {
			return getMinCoin_Greedy(cnt, coin_Index + 1, changes);
		}
	}

	public static int getMinCoin_DP(int changes) {
		int[] dp = new int[changes + 1]; //dp[i] : i원을 거슬러주기 위해 사용한 거스름돈 최소 갯수
		Arrays.fill(dp, INF); //dp배열 INF로 초기화
		dp[0] = 0;

		//모든 동전을 한번씩 사용하면서
		for (int i = 0; i < coin.length; ++i) {
			for (int j = coin[i]; j <= changes; ++j) {
				//현재 j원을 거슬러 주는 개수보다 j-coin[i]원을 거슬러 주는 개수 + coin[i]을 한 번 거슬러주는 회수가 더 작다면 갱신
				dp[j] = Math.min(dp[j], dp[j - coin[i]] + 1);
				count_Dp++;
			}
		}

		return dp[changes];
	}
}

 

두 방법의 결과를 보면 탐욕 알고리즘은 다이나믹 프로그래밍보다 빠른 성능을 가지지만 최종적으로 구한 값은 최적해에 가까운 값이지만 최적해는 아닌 것을 확인할 수 있다.