그리디 알고리즘은 동적 프로그래밍을 간단한 문제 해결에 사용하면 지나치게 많은 일을 한다는 것을 착안하여 고안되었다.동적 프로그래밍을 대체하는 것은 아니고 같이 쓰이며 서로 보완하는 개념이다.
탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 이렇게 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적해를 보장해주는 것은 아니다.
순간마다 하는 선택이 최선이면, 결과도 최선 아닌가?? → 아닙니다
그리디 알고리즘이 추구하는 가장 좋은 것에 대해 예시를 들어 알아보자.
우리가 시작 부분에서 시작해서 지나간 Path의 돈을 받는 문제?로또? 아무튼 있다고 가정하면, 가능한 가장 큰 돈을 얻는 경로를 이용하길 원할 것이다.
우리는 가장 좋은 결과가 “시작 - 5백만원 - 5조”를 거치는 Path가 가장 큰 돈을 얻을 수 있다는 것을 알 수 있다. (벼락부자 ㄱㅇㄷ)
하. 지. 만. 그리디 알고리즘을 사용한다면 시작 지점의 바로 앞만 보고, 5천만원을 선택하게 된다. 결론적으로 이 ... 미련한 그리디 알고리즘은 “시작 - 5천만원 - 5천원”이란 Path가 가장 좋은 것이라고 판단한다.
이처럼 그리디 알고리즘은 순간의 가장 좋은 결과를 선택하는 방식이다.
그리디 알고리즘을 사용하기 위해 필요한 조건은 2가지가 있다.
: 탐욕적인 선택은 항상 안전하다는 것이 보장되어야 한다. 여기서 “안전하다”라는 것은 이 선택으로 인해 전체 문제의 최적해를 반드시 도출할 수 있어야 한다는 것이다.
엥 뭔소리야. 위에서는 그리디 알고리즘을 사용해 결과를 도출하면 최적해가 나오는 건 아니라며?
그리디 알고리즘을 사용하면 무조건 최적해가 나오는 것은 아니다. 하지만 그리디 알고리즘을 사용해 푸는 문제가 나왔을 때 이 조건이 만족되느냐를 생각해보고 충족될 때 그리디 알고리즘을 사용하는 것이다.
즉, 그리디 알고리즘을 사용했을 때 최적해(가장 좋은 결과)가 나올 수 있는 문제에 이를 사용할 수 있다는 것.
: 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다는 조건이다. 이 말은 전체 문제의 안에는 여러 단계가 존재하고, 이 여러 단계 내의 각 단계에 대해 최적해가 도출되어야 한다는 것이다.
그리디 알고리즘에서 고려해야 하는 상황은 값들이 서로 영향을 주면 안된다는 것을 염두에 두어야 한다.
쉽게 풀어 아까 본 예시로 설명해보자면, 그리디 알고리즘이 도출한 최종 Path는 “시작 - 5천만원 - 5천원”이다. 이 때 “5백만원” 아래의 “5조”라는 값이 있다고, Path를 변경할 수 없다는 것이다.
위의 조건들이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못한다. 하지만 그런 경우에도 탐욕 알고리즘은 근사 알고리즘으로 사용이 가능할 수 있으며, 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있다. 이 경우 역시 어느정도까지 최적해에 가까운 해를 구할 수 있는지를 보장하려면 엄밀한 증명이 필요하다.
한편, 어떤 특별한 구조가 있는 문제에 대해서는 탐욕 알고리즘이 언제나 최적해를 찾아낼 수 있다. 이 구조를 매트로이드라 한다. 매트로이드는 모든 문제에서 나타나는 것은 아니나, 여러 곳에서 발견되기 때문에 탐욕 알고리즘의 활용도를 높여준다.
1) 정리하자면, **탐욕 알고리즘**은 탐욕적 선택 속성, 최적 부분 구조라는 두 가지 조건을 만족할 때 최적의 결과(최적해~은)를 도출해낸다. 두 조건을 만족하지 않더라도 근사값을 빠르게 도출해내기에 탐욕 알고리즘은 **근사 알고리즘**으로 사용가능하다. 2) 탐욕 알고리즘을 적용해도 언제나 최적해를 구할 수 있는 문제(**매트로이드**)가 있고, 이러한 문제에 탐욕 알고리즘을 사용해서 빠른 계산 속도로 답을 구할 수 있다. 그래서 실용적으로 사용 가능하다.소령이는 다이어트를 성공하고 드디어 라면을 먹기 위해 마트로 갔다. 그 마트에는 코딩천재 찌니가 알바 대타를 뛰어주고 있었다. 소령은 라면을 여러 봉지 집어 들었고, 가격은 총 14,040원이 나왔다. 소령은 15,000원을 내밀며, 거스름돈은 동전의 개수를 최소한으로 하여 거슬러달라($)고 했다.
탐욕 알고리즘으로 동전의 개수를 헤아리는 일은 일반적으로 거스름돈으로 동전을 선택하는 방법과 동일하다. 우리는 가장 큰 단위의 돈부터 생각해야 할 것이다. 거스름돈 960원을 채우기 위해서 먼저 500원짜리 동전을 한 개 선택한다. 그 다음은 100원짜리 동전을 네 개 선택하고, 그 다음엔 50원짜리 동전과 10원짜리 동전을 각각 하나씩 선택할 것이다. 이렇게 가장 큰 단위부터 거슬러주고 나머지를 그 다음 단위의 화폐로 거슬러주는 해결 방법을 떠올릴 수 있다.
// count =0
//반복시작~(changes!==0)
//for(let coin of coinArr)
// coinArr = [500, 100, 50, 10] //changes = 960원(거스름돈)
// 960/500 -->( .xxx --> 내림) --> count = 1
// changes = 960-500*1개 = 460원
// count = count + Math.floor(460/100)
// changes = 460-100*4 = 60
// ...
// changes = changes-(coin*count)
//return count
// 최소 동전 개수 구하는 함수
function minimumCoinNumber(changes) {
let count = 0;
const coinArr = [500,100,50,10,5, 1];
for(let coin of coinArr){
count = count + Math.floor(changes/coin); //동전의 개수
changes = changes - item * Math.floor(changes/coin); // 남은 돈 계산
}
return count;
}
// 탐욕 알고리즘을 사용해도 최적해를 찾아낼 수 있으므로 **매트로이드 구조!**
황쥐는 이사를 위해 짐을 싸고, 서히를 시켜 짐을 넣을 박스를 사오게 했다. 박스를 사오고보니 이삿짐의 무게는 들쭉날쭉한데, 짐을 넣을 박스는 너무 작아서 한번에 최대 2개의 짐밖에 넣을 수 없었고 100kg의 무게 제한이 있었다. 황쥐의 이삿짐의 무게는 [70kg, 50kg, 80kg, 50kg]일 때, 황쥐는 최대한 적게 박스를 사용해 모든 짐을 옮기려고 한다.
탐욕적으로 생각해보면(는 순간만 보고 해결할 수 있는 최적의 방안을 생각해보면 ~ㅋㅋ), 최대 2개의 짐 밖에 넣을 수 없으므로 무거운 것, 가벼운 것 짝지어서 박스에 넣는 것을 떠올릴 수 있다. 그리고 박스의 무게 제한을 고려해 짝짓는 방법을 생각해볼 수 있다.
//stuff = [70, 50, 80, 50]
//최대 2개의 짐 밖에 넣을 수 없으므로 무거운짐-가벼운짐 짝지어서 박스에 넣기위해 정렬
//sortedStuff = [80, 70, 50, 50]
//limit = 100
//80 -->shift --> count!
//[70, 50, 50]
//70 -->shift --> count!
//[50, 50]
// 50+50 = 100
// shift, pop --> count!
// []
//반복의 조건: sortedStuff.length !==0
function movingStuff(stuff, limit) {
let count = 0;
let sortedStuff = stuff.sort((a, b) => b - a)
while (sortedStuff.length !==0) {
if (sortedStuff[0] + sortedStuff[sortedStuff.length-1] <= limit) {
count++
sortedStuff.shift();
sortedStuff.pop();
} else {
count++
sortedStuff.pop();
}
}
return count;
}
탐욕 알고리즘은 문제를 해결하는 과정에서 매 순간, 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식이다.
그러나 항상 최적의 결과를 보장하지 않기 때문에, 그리디 알고리즘을 사용해 답을 찾게 된다면, 그 답이 정당한지 마지막에 해답 검사 과정을 꼭 거쳐야 한다~
https://hanamon.kr/알고리즘-탐욕알고리즘-greedy-algorithm/
https://velog.io/@contea95/탐욕법그리디-알고리즘
https://www.zerocho.com/category/Algorithm/post/584ba5c9580277001862f188
https://velog.io/@devjade/JavaScript로-greedy-algorithm탐욕-알고리즘-구현하기
욕망의 서광채 잘보고 갑니다 ^^*