Greedy Algorithm(탐욕 알고리즘)

1. 정의

   • 탐욕 알고리즘은 매 단계에서 정한 기준에 따라 한 선택을 확정하고 이전 선택을 되돌리지 않는다. 문제에 따라 정확한 최적 알고리즘일 수도 있고, 반례가 있는 근사 방법일 수도 있다. 먼저 선택 규칙을 세우고, 그 규칙이 최적해를 놓치지 않는지 증명하거나 반례를 찾아야 한다.

2. 동적 계획법과 탐욕 알고리즘의 차이

   • 동적 계획법은 여러 가능한 선택의 부분 문제 값을 저장해 비교한다. 탐욕법은 지금 한 선택만 남기므로 상태가 작아질 수 있다. 어느 쪽이 더 빠른지와 최적해를 보장하는지는 문제의 구조와 증명에 달려 있다. 모든 동적 계획법이 효율적이거나 모든 탐욕법이 근사인 것은 아니다.

3. 동작과정

   1. 동적 계획법처럼 대상 문제가 최적 부분 구조를 갖고 있어야한다.
   2. 해 선택 : 현재 상태에서 부분 문제의 최적 해를 구한 뒤, 이를 부분해 집합(Solution Set)에 추가
   3. 실행 가능성 검사 : 새로운 부분해 집합이 실행가능한지를 확인, 문제의 제약 조건을 위반하지 않는지 검사
   4. 해 검사 : 새로운 부분해 집합이 문제의 해가 되는지를 확인, 아직 전체 문제의 해가 완성되지 않았다면 1.의 해 선택부터 다시 시작

4. 거스름돈 줄이기

   • 물건 가격이 1200원이고 고객이 1000원 지폐 두 개를 지불하면 거스름돈 800원을 고객에게 줘야 한다. 이때 100원짜리 8개를 줄 수도 있지만 동전의 개수를 최소한으로 하려면 500원 짜리 한개와 100원 짜리 3개를 줘야한다.

   • 알고리즘

     1. 해 선택 : 가장 좋은 해를 선택. 단위가 큰 동전으로만 거스름 돈을 만들면 동전의 개수가 줄어듬. 그러므로 현재 고를 수 있는 가장 단위가 큰 동전을 하나 골라 거스름돈에 추가

     2. 실행 가능성 검사 : 거스름돈이 손님에게 내드려야 할 액수를 초과하는지 검사. 초과한다면 마지막에 추가한 동전을 거스름돈에서 빼고 1.로 돌아가 현재보다 한 단계 작은 단위의 동전을 추가

     3. 해 검사 : 거스름돈 문제의 해는 당연히 거스름돈이 손님에게 내드려야하는 액수와 일치하는 것으로 액수가 일치하지 않으면 1.을 다시 돌아가서 추가할 동전 선택

public class GreedyAlgorithm {
	private int[] coinUnits;
	private int[] change;

	public static void main(String[] args) {
		GreedyAlgorithm al = new GreedyAlgorithm();

		al.coinTest();
	}
	void coinTest() {
		Scanner scan = new Scanner(System.in);
		System.out.print("동전의 가짓수를 입력 : ");
		int unitCount = scan.nextInt();
		coinUnits = new int[unitCount];
		change = new int[unitCount];

		for (int i =0; i<unitCount; i++) {
			System.out.print("[" + i+"] 번째 동전 단위를 입력 : ");
			coinUnits[i] = scan.nextInt();
			if (coinUnits[i] <= 0 || (i > 0 && coinUnits[i] >= coinUnits[i-1])) {
				throw new IllegalArgumentException("동전 단위는 양수이며 큰 순서로 입력해야 합니다");
			}
		}
		System.out.print("물건 가격 입력 : ");
		int price = scan.nextInt();

		System.out.println("손님이 지불한 금액 : ");
		int pay = scan.nextInt();
		getChange(price,pay,unitCount);
		printChange(unitCount);
	}
	/**
	 * 거스름돈 계산을 위한 func 선언
	 * @param price
	 * @param pay
	 * @param coinUnits
	 * @param change
	 * @param size
	 */
	void getChange(int price, int pay, int size) {
		if (pay < price) throw new IllegalArgumentException("지불액이 가격보다 작습니다");
		int changeAmount = pay - price;

		for (int i=0; i< size; i++) {
			change[i] = countCoins(changeAmount, coinUnits[i]);
			changeAmount = changeAmount - (coinUnits[i] * change[i]);
		}
		if (changeAmount != 0) throw new IllegalArgumentException("주어진 동전으로 거슬러 줄 수 없습니다");
	}

	/**
	 * 거스름돈 계산을 위한 func 구현
	 * @param amount
	 * @param coinUnit
	 * @return
	 */
	int countCoins(int amount, int coinUnit) {
		return amount / coinUnit;
	}

	/**
	 * 결과출력
	 * @param coinUnits
	 * @param change
	 * @param size
	 */
	void printChange (int size) {
		for(int i =0; i<size; i++) {
			System.out.printf("%8d원 : %d개\n", coinUnits[i], change[i]);
		}
	}
}

800원의 거스름돈을 돌려줘야 하는 상황에서 400원자리 동전이 있다고 치면 400원 짜리 2개를 주면되지만, 위 알고리즘 대로 하면 500원짜리 한개와 100원짜리 3개를 주게된다. 그러므로 거스름돈을 만드는 탐욕 알고리즘은 항상 최적이지 않다. 거스름돈 알고리즘 처럼 항상 최적의 결과를 보장하지 못한다는 것도 탐욕 알고리즘의 중요한 속성

이 반례의 동전은 {500, 400, 100}이다. “가장 큰 동전을 먼저 고른다”는 규칙으로 800원을 만들면 500+100+100+100으로 4개이고, 가능한 다른 해 400+400은 2개다. 코드가 잘못 계산한 것이 아니라 선택 규칙 자체가 최소 개수를 보장하지 않는 것이다. 입력 동전은 큰 단위부터 넣어야 하고, 지불액이 가격보다 작은 경우와 동전으로 정확히 만들 수 없는 잔액도 검사해야 한다. countCoins는 한 단위가 몇 개 들어가는지 나눗셈으로 구하므로 동전 종류가 d개라면 위 구현의 계산 단계는 O(d)다.

언제 탐욕 선택을 믿을 수 있는가

탐욕 선택의 정당성을 보이려면 보통 교환 논증을 쓴다. 어떤 최적해가 탐욕적으로 고른 첫 선택을 포함하지 않더라도, 그 첫 선택으로 바꾸어도 해의 품질이 나빠지지 않음을 보인다. 그런 다음 남은 부분 문제에도 같은 논리를 적용한다. 이 교환이 불가능하면 국소적으로 좋아 보이는 선택이 나중의 선택을 막을 수 있다.

예를 들어 겹치지 않는 회의의 개수를 최대화할 때는 종료 시각이 가장 빠른 회의를 먼저 고르는 규칙을 쓴다. 첫 회의를 끝나는 시각이 더 늦은 회의로 고른 최적해가 있다면, 그 첫 회의를 더 빨리 끝나는 회의로 바꿔도 뒤의 회의들은 여전히 시작할 수 있다. 그러므로 이 규칙을 포함한 최적해가 존재한다. 남은 회의에 같은 선택을 반복하면 된다.

import java.util.Arrays;

int[][] meetings = {{1, 4}, {2, 3}, {3, 5}, {4, 6}};
Arrays.sort(meetings, (a, b) -> Integer.compare(a[1], b[1]));
int lastEnd = Integer.MIN_VALUE;
int count = 0;
for (int[] meeting : meetings) {
    if (meeting[0] >= lastEnd) {
        count++;
        lastEnd = meeting[1];
    }
}
System.out.println(count); // 2

정렬 후 첫 회의는 [2,3], 다음으로 시작 시각 3인 [3,5]를 고를 수 있다. 끝과 시작이 같은 회의를 겹치지 않는 것으로 정의했으므로 >=를 사용했다. 그런 규칙이 아니라면 비교 연산자를 바꿔야 한다. 정렬은 O(n log n), 한 번의 순회는 O(n)이다. 같은 종료 시각인 회의들의 순서는 정답 개수에 영향을 주지 않는다.

탐욕법을 고를 때는 후보 정렬 기준, 선택 후 유지되는 제약, 첫 선택을 포함하는 최적해가 존재한다는 근거, 반례를 찾을 작은 입력을 순서대로 점검하자. 위 동전 예제와 회의 예제의 차이는 구현 문법이 아니라 그 선택을 교환해도 남은 해를 유지할 수 있는지에 있다.