[Algorithm] 탐욕법 (그리디 알고리즘, Greedy) : Java

탐욕법 (Greedy)

탐욕법 (Greedy) 이란?

• 최적해를 구하는 데에 사용되는 근사적인 방법
• 여러 경우(분기점) 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택, 누적해가는 방법(재귀적)
• 즉, 전체를 고려하지 않고 그 순간에서의 최선을 선택하는 것
• 불완전한 방법이기 때문에, 두가지 조건(탐욕적 선택 조건, 최적 부분 구조 조건)을 만족하는 경우에만 최적의 답을 산출, 그 외엔 최적의 값이라곤 할 수 없다.
• 따라서, 선택들을 계속 수집해서 최종적인 해답을 얻었을 경우, 이 해답이 최적의 답이라는 보장은 없다.
• 탐욕법은 동적 계획법보다 수행시간이 훨씬 빠르기 때문에 유용하다.

* 탐욕적 선택 조건 (greedy choice property)

• 앞의 선택이 이후 선택에 영향을 주지 않는 경우
• 즉, 각 사건들이 서로 독립적일 때 잘 맞는다.

* 최적 부분 구조 조건 (optimal substructure)

• 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해인 경우

사용 조건

• 탐욕법을 사용해도 항상 최적해를 구할 수 있는 경우
• 시간이나 공간적 제약으로 인해 최적해 대신 근사해를 찾아서 해결하는 경우

위의 두 가지 조건 중 하나를 만족하면 탐욕법을 사용할 수 있다.

접근 방법

1. 문제의 답을 만드는 과정을 여러 조각으로 나눈다.
2. 각 조각마다 어떤 우선순위로 선택을 내려야 할지 결정한다. (작은 입력을 손으로 풀어본다.)
3. 이 선택이 safe move 인지 증명한다.
4. 어떤 방식이 동작할 것 같으면 다음 두 조건이 적용되는지 확인해본다. (탐욕적 선택 조건, 최적 부분 구조 조건)

* safe move 란?

• 선택 중 첫 번째로 선택한 것이 최적의 선택과 일치하는 경우

4번의 조건이 만족하지 않는 경우 탐욕법은 최적해를 구하지 못한다.

하지만 이러한 경우라도 탐욕법은 근사 알고리즘으로 사용 가능하다.

구현 예제

탐욕법의 대표적인 문제

• 거스름돈 문제
• 배낭 문제
• 활동 문제

거스름돈 문제

(ex) 최종적인 답이 가장 최적의 해답인 경우

 

 

출처 : BOJ 5585번 - 거스름돈

 

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

최소 개수를 구하려면 가장 큰 동전을 우선으로 거슬러주면 된다.

 

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//지불해야하는 돈
		int price = sc.nextInt();
		//거스름돈 배열
		int[] money = {500,100,50,10,5,1};
		//거슬러줘야할 돈
		int change = 1000 - price;
		//거스름돈 갯수
		int cnt = 0;
		
		for(int i=0; i<6; i++) {
			cnt += (change / money[i]);
			change %= money[i];
			if(change == 0) break;
		}
		
		System.out.print(cnt);
	}

 

결과는 4로 최적의 해를 구할 수 있다.

 

 

(ex) 최종적인 답이 최적의 해답이 아닌 경우

 

public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//지불해야하는 돈
		int price = sc.nextInt();
		//거스름돈 배열
		int[] money = {500,400,100,50,10,5,1};
		//거슬러줘야할 돈
		int change = 1000 - price;
		//거스름돈 갯수
		int cnt = 0;
		
		for(int i=0; i<6; i++) {
			cnt += (change / money[i]);
			change %= money[i];
			if(change == 0) break;
		}
		
		System.out.print(cnt);
	}

 

만약 잔돈을 800엔 거슬러 준다고 가정하고 동전에 400엔이 있다고 생각해보자.

최적의 답은 400엔 X 2로 동전의 개수는 2가 최적의 답이다.

하지만 위의 풀이(탐욕법)로 하면 큰 돈부터 거슬러주는 선택을 하게 된다.

따라서, 500엔 1개, 100엔 3개로 답이 4가 된다.

이 결과로 최적의 선택을 안하는 것을 알 수 있다.

즉, 탐욕법은 무조건 최적의 해답은 아니다.

참고

github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/Algorithm

JaeYeopHan/Interview_Question_for_Beginner

mygumi.tistory.com/121

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

jodu.tistory.com/45

Greedy algorithm - 탐욕 알고리즘

velog.io/@hanturtle/%ED%83%90%EC%9A%95%EB%B2%95Greedy

탐욕법(Greedy)

ko.wikipedia.org/wiki/%ED%83%90%EC%9A%95_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

탐욕 알고리즘 - 위키백과, 우리 모두의 백과사전

nuromancer1984.tistory.com/entry/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%9A%95-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[알고리즘] 탐욕 알고리즘, 그리디 알고리즘

hcn1519.github.io/articles/2017-01/greedy_algorithm

Greedy algorithm(탐욕 알고리즘)