Greedy algorithm - 탐욕 알고리즘

소개

최적해를 구하는 데에 사용되는 근사적인 방법, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해나가는 방식이다.
여기서 중요한 것은 선택들을 계속 수집해서 최종적인 해답을 얻었을 경우 이 해답이 최적의 답이라는 보장은 없다. 

탐욕 알고리즘은 동적알고리즘이 지나치게 많은 일을 한다는 것에 착안되어 만들어진 알고리즘이다.

적용이 잘되는 경우

1. Greedy Choice Property (탐욕 선택 조건)

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

2. Optimal Substructure (최적 부분 구조 조건)

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

대표적인 해결 문제

1. 배낭 문제

2. 동전 문제

3. 활동 문제 등

소스코드 

import java.util.Arrays;

public class KnapackProblem {
	public static void main(String[] args) {
		int permitWeight = 20;
		int resultValue = 0;
		int[][] jewels = {
			// value, weight
			, , , 
		};
		
		//보석의 가치 별로 정렬
		Arrays.sort(jewels, (cur, prev) -> {
			int prevValue = (prev[0] / prev[1]);
			int curValue = (cur[0] / cur[1]);
			return prevValue - curValue;
		});
		
		for(int i=0; i<jewels.length; i++) {
			//1. 한도 무게가 남아 있고,
			if(permitWeight > 0) {
				int[] curJewel = jewels[i]; //현재 보석
				int v = curJewel[0]; //현재 보석의 가치
				int w = curJewel[1]; //현재 보석의 무게
				//1.1 보석의 무게가 한도 무게보다 작다면
				if(permitWeight >= w) {
					permitWeight -= w;
					resultValue += v;
				} else { //1.2 보석의 무게가 한도 무게보다 크면 다음번 보석으로 넘어간다. 
					continue;
				}
			} else {
				break;
			}
		}
		
		System.out.println(resultValue);
	}
}

우선 무분별하게 나열되어 있는 보석들을 무게당 가치의 비율로 정렬을 한다. 이렇게 되면 배낭의 무게가 허용할 때까지 순서대로 넣기만 하면 최적의 가치를 가진 배낭을 만들 수 있게 된다.

문제점

탐욕 알고리즘은 소개 부분에서 설명 한 것처럼 작은 사건들의 최적의 값을 모았을 경우 이 결과가 문제 전체에 대해서는 최적의 해가 되지 못한다고 하엿는데 위에서 작성한 소스 코드에서도 똑같이 발생한다. 예를 들어 배낭의 무게가 20으로 주어진다면 최고의 배낭 가치는 100이지만 탐욕 알고리즘의 결과는 70이라는 결과를 나타내게 된다. 

이와 같이 탐욕 알고리즘은 문제에 대한 근사치를 구할 때 유용하며 정확한 값을 찾는 문제에서는 다소 위험 할 수 있다. 

참고 자료

위키백과 - 탐욕알고리즘

https://www.zerocho.com/category/Algorithm/post/584ba5c9580277001862f188

https://m.blog.naver.com/PostView.nhn?blogId=twoa0&logNo=220984166738&proxyReferer=https%3A%2F%2Fwww.google.co.kr%2F