그리디(Greedy)알고리즘

(그리디 = 탐욕) 알고리즘

그리디 알고리즘은 매 순간 최선의 방법을 택하여 결과를 도출하는 알고리즘이다.

예시1)

가장 흔한 예시로 우리가 편의점 알바생 이라고 해보자.

손님이 구매한 물건 : 3570원

손님이 지불한 금액 : 5000원 지폐

알바생인 우리는 500원, 100원, 50원, 10원 동전을 무한대로 가지고 있다 라고 가정한다.

동전의 개수를 최소한으로 지불 하고 싶을 때 그리디 알고리즘 적으로 생각을 하면, 일단 최소한의 동전 개수로 지불하기 위해서 가장 값이 높은 500원 순으로 계산을 해야 할 것이다.

500원 2개, 100원 4개, 10원 3개가 최소한의 동전의 개수이다. 얼핏 보면 최고의 방법만 도출하는 알고리즘 같아 보인다.

하지만 그리디 알고리즘은 매 순간 최선의 방법만을 선택한다. 그리고 그 선택한 결과가 나중에 미칠 영향은 고려하지 않는다.

예시1 JS로 구현

let itemcost = 3570;                         //물건의 가격
let pay = 5000;                              //지불한 돈
let change = pay - itemcost                  //줘야하는 잔돈

function greedyCost (c) {             
		let 오백원 = 500;
		let 백원   = 100;
		let 오십원 = 50;
		let 십원   = 10;
		let result = {'500':0, '100':0, '50':0, '10':0};

		while(c != 0){
			if(c >= 오백원) {
				c -= 500;
				result[500]++;
			} else if (c >= 백원) {
				c -= 100;
				result[100]++;
			} else if (c >= 오십원) {
				c -= 50;
				result[50]++;
			} else if (c >= 십원) {
				c -= 10;
				result[10]++;
			} else {
				break;
			}
		}		
		
		if(c == 0){
			return result;
		} else {
			return false;
		}		
}

console.log(greedyCost(change))       //{500:2, 100:4, 50:0, 10:3}

---

예시2)

우리는 부자 집을 털러온 도둑이다. 목적은 가장 높은 값어치의 물건들을 훔치는 것 이다.우리가 가지고 온 가방에는 최대 30kg(부피는 고려 하지 않음)만 담을 수 있다.

부자 집의 금고에는 금괴, 은괴, 동괴가 있다. 이때 금괴, 은괴, 동괴의 양은 셀 수 없이 많다.

(가격과 무게는 말이 안되지만 예시로)

금괴는 개당 3000만원 무게는 5kg이다

은괴는 개당 2000만원 무게는 1kg이다

동괴는 개당 100만원 무게는 100g이다

이때 그리디 알고리즘적으로 생각을 하게 된다면 금괴 6개를 담은 1억 8천만의 값어치가 훔치게 된다.

왜냐하면 순간순간 우리의 목적인 3개중 가장 높은 값어치를 가진 금괴를 선택하게 되고 그것을 골랐을때 생기는 영향은 생각하지 않고 금괴만 훔치게 되는 것이다.

하지만 결과적으로 가장 높은 값어치는 그냥 은괴 30개를 훔쳐 6억을 얻는 결과가 가장 최고의 결과이다. 이처럼 그리디 알고리즘은 최고의 결과물을 주지는 않는다.

매순간 목적에 맞는 가장 최선의 방법을 선택하고 그 선택이 후에 미치는 영향은 계산하지 않는다. 따라서 위와 같은 경우에서 최적의 결과를 도출하기 위해서는 백트래킹이나 동적 계획법 알고리즘을 사용해야 한다.

예시2 JS로 구현

let bag = 35;

function steel (bag) {
		let result = {goldbar : 0, silverbar : 0, bronzebar : 0, result : 0};
		let goldbar = {weight : 5, price : 3000};
		let silverbar = {weight : 1, price : 2000}
		let bronzebar = {weight : 0.1, price : 100}
		
		while(bag != 0) {
			if(bag >= 5) {
				result.goldbar++;
				result.result+=goldbar.price;
				bag -= goldbar.weight;
			} else if (bag >= 1) {
				result.silverbar++
	 			result.result+=silverbar.price;
				bag -= silverbar.weight;
			} else if (bag >= 0.1) {
				result.bronzebar++;
				result.result+=bronzebar.price;
				bag -= bronzebar.weight;
			} else {
				break;
			}
		}
		return result;
}

console.log(steel(bag))    //{goldbar : 7, silverbar : 0, bronzebar : 0, result : 21000}

그리디 알고리즘은 간단하고 구현이 비교적 쉽다 라는 장점이 있지만 위에서 언급 한 것처럼 최적의 결과를 도출하지 못 할 수도 있다는 단점이 있다.