[알고리즘] 자바에서의 그리디(탐욕) 알고리즘

그리디(탐욕) 알고리즘

- 다익스트라 알고리즘과 같은 고급 그래프 탐색 알고리즘에서 그리디(탐욕) 알고리즘을 사용하고 있기 때문에 미리 익혀놓고 넘어가는 것이 좋다.

- 최적의 해에 가까운 값을 구하기 위해 사용된다.

- 여러 경우 중 하나를 결정해야 할 때마다, 매순간 최적이라고 생각되는 경우를 선택하는 방식으로 진행해서, 최종적인 값을 구하는 방식이다.

- 전체에서 가능한 경우의 수를 모두 따져가며 최적의 해를 찾는 것이 아니라, 각 단계를 거칠 때마다 현재 단계를 기준으로 가장 최적의 경우가 무엇인지를 판별해서 선택하는 것이다.

- 그렇기 때문에 최적의 해에 가까운 값을 구할수는 있겠지만, 그것이 반드시 최적의 해라고 말할 수는 없다.

 

탐욕 알고리즘의 한계

- 탐욕 알고리즘은 근사치 추정에 활용된다.

- 반드시 최적의 해를 구할 수 있는 것은 아니기 때문이다.

- 최적의 해에 가까운 값을 구하는 방법 중의 하나이다.

 

탐욕 알고리즘 문제를 해결하는 방법

1. 선택 절차 (Selection Procedure) : 현재 상태에서의 최적의 해답을 선택한다.

2. 적절성 검사 (Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사한다.

3. 해답 검사 (Solution Check) : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

 

탐욕 알고리즘 예시 문제 1

- 동전 문제

1. 지불해야 하는 값이 4720원 일 때 1원, 50원, 100원, 500원 동전으로 최소 갯수만큼 지불하시오.

2. 가장 큰 동전부터 최대한 지불해야 하는 값을 채우는 방식으로 구현이 가능하다.

3. 탐욕 알고리즘으로 매순간 최적이라고 생각되는 경우를 선택하면 된다.

 

- GreedyExample1

import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;

public class GreedyExample1 {
	public static void main(String[] args) {
		Integer [] coinArray = {500, 100, 50, 1};
		int value = 4720;
		int totalCoinCount = 0;
		HashMap<Integer, Integer> details = new HashMap<Integer, Integer>();
		
        // 값이 큰 동전부터 사용하기 위해 내림차순 정렬
		Arrays.sort(coinArray, Collections.reverseOrder());
		
		for(int coin : coinArray) {
			int coinNum = value / coin; // 현재 코인 기준 value 값을 채울 수 있는 최대 갯수
			totalCoinCount += coinNum;
			value -= coinNum * coin;
			details.put(coin, coinNum);
		}
		
		System.out.println("총 동전 갯수 : " + totalCoinCount);
		System.out.println("동전 별 사용갯수 : ");
		Object[] keyArray = details.keySet().toArray();
		for(int i = 0; i < details.size(); i++) {
			System.out.println(keyArray[i] + "원 : " + details.get(keyArray[i]));
		}
		
	}
}

 

탐욕 알고리즘의 예시 문제 2

- 부분 배낭 문제

1. 무게 제한이 k 인 배낭에 최대 가치를 가지도록 물건을 넣는 문제

2. 물건은 쪼갤 수 있으므로 물건의 일부분이 배낭에 넣어질 수 있다, 그래서 Fractional Knapsack Problem 으로 부른다.

3. Fractional Knapsack Problem 의 반대로 물건을 쪼개서 넣을 수 없는 배낭 문제도 존재한다.(0/1 Knapsack Problem)

4. 각 단계별로 가장 적은 무게로 가장 높은 가치를 뽑아낼 수 있는 경우를 판단해야 한다.

 

- GreedyExample2

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;

public class GreedyExample2 {
	public static void main(String[] args) {
		HashMap<Integer, List<Double>> details = new HashMap<Integer, List<Double>>();
		
		int[][] dataArray = {{10,10},{15,12},{20,10},{25,8},{30,5}};
		
		Arrays.sort(dataArray, new Comparator<int[]>() {

			// 무게 대비 가중치가 높은 순으로 내림차순 정렬
			@Override
			public int compare(int[] o1, int[] o2) {
				if((o1[1] / o1[0]) == (o2[1] / o2[0])) {
					return o1[0] - o2[0];
				}
				else {
					return o1[0] - o2[0];
				}
			}
		});
			
		int totalValue = 0;
		double capacity = 30;
		for(int i = 0; i < dataArray.length; i++) {
			
			List<Double> list = new ArrayList<Double>();

			// 배낭의 최대 용량이 무게 단위 별 최대 가치를 가지고 있는 물건의 무게보다 크다면
			if(capacity - dataArray[i][0] >= 0) {
				capacity -= dataArray[i][0]; // 물건을 쪼개지 않고 통째로 배낭에 넣는다.
				totalValue += dataArray[i][1];
				list.add((double)dataArray[i][1]);
				list.add(1.0); // 여기서 1은 물건이 쪼개지지 않고 통재로 배낭에 들어갔다는 뜻이다.
				details.put(dataArray[i][0], list);
			}
			else { // 물건을 쪼개야 하는 경우
				// 현재 배낭 용량 / 무게 - 물건을 얼마나(물건에서 몇 퍼센트를 쪼갤지) 쪼개서 넣어야 할지 계산한다.
				// 물건을 쪼개서 넣고 나면 어차피 배낭의 남은 용량은 0 이기 때문에 용량에서 무게를 빼는 코드는 제외
				double fraction = capacity / dataArray[i][0];
				
				// 쪼개지는 용량 * 물건의 가치(쪼개서 넣어지는 가치 만큼만 추가)
				totalValue += dataArray[i][1] * fraction;
				list.add((double)dataArray[i][1]);
				list.add(fraction);
				details.put(dataArray[i][0], list);
				break; // 뒤에 물건이 더 있다고 해도 더 이상은 배낭에 물건이 들어갈 용량이 없기 때문에 반복문 종료
			}	
		}
		
		System.out.println(totalValue);
		
		Object[] keyArray = details.keySet().toArray();
		Arrays.sort(keyArray);
		for(int i = 0; i < keyArray.length; i++) {
			List<Double> list = details.get(keyArray[i]);
			System.out.println(keyArray[i] + list.toString());
		}
	}
}