[JAVA] Greedy 알고리즘

Greedy(탐욕) 알고리즘은 직전에 다뤘던 동적 계획법과 대조되는 개념으로, 큰 문제를 쪼갠 부분 문제를 전부 검토하여 정답을 도출하는 것이 아니라, 풀이를 진행하는 순간순간마다 최적이라고 생각하는 정답을 도출해내는 방법이다. 

즉, 모든 경우의 연산을 전부 수행하여 "완전한 정답"을 찾기보다는 각 상황마다 최적이라고 생각하는 연산만 골라 수행하여 좀 더 빠르게 "근사치"를 찾는 기법이라고 할 수 있다.

 

예를 들어보면,

출처는 더보기

https://velog.io/@cyranocoding/%EB%8F%99%EC%A0%81%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming%EA%B3%BC-%ED%83%90%EC%9A%95%EB%B2%95Greedy-Algorithm-3yjyoohia5#:~:text=com%2Fgreedy.php-,Greedy%20Algorithms

 

다음의 각 노드에서 값이 가장 큰 경우를 좇아 가장 큰 값을 구하려고 하지만, 실제 가장 큰 값과 Greedy Way를 따라 구한 근사치가 차이가 난다.

이렇게 항상 "근사치 = 원하는 결과 값"을 만족하는 것은 아니기 때문에 특정 상황에만 제한적으로 사용하는 알고리즘이다. 

하지만 이러한 단점을 극복하는 Greedy의 가장 큰 장점은 계산 속도에 있다. 그래서 Greedy 방법이 통하기만 한다면 해당 문제에서는 최적해를 빠르고 효율적으로 도출해낼 수 있다.

 

이런 Greedy 알고리즘을 활용한 쉬운 예제를 하나만 보면,

 

- Coin Exchange

  -> 10원, 50원, 100원, 500원, 1000원이 있을 때, 8,750원를 교환할 수 있는 최소 동전 개수를 구하라.

가장 간단하게 생각해볼 수 있는 방법은 가장 큰 금액의 잔돈부터 차례로 계산하는 것이다. 그리고 이는 실제로 문제의 최적해이다.

 

---

 

int coins[] = { 10, 50, 100, 500, 1000 };

public int coinExchange() {
	int money = 8250; // 교환할 돈
	int changes = 0; // 동전 개수
	
    for (int i = coins.length - 1; i >= 0; i--) { //가장 큰 단위부터 Coin을 한개씩 넣어보며 진행
		while (money >= coins[i]) { //해당 단위로 더 이상 쪼갤 수 없을 때까지 진행
			money -= coins[i];
			changes++;
		}
	}
	return changes;
}

위와 같이 가장 큰 단위의 돈부터 진행하여 최적해를 구할 수 있다. 

 

이렇게 어떤 문제를 해결하기 위한 부분 문제를 최적해를 구하기 위한 조건이나 가정을 먼저 세운 뒤 이를 기반으로 푸는 기법은 대부분 Greedy 알고리즘이라고 볼 수 있다.