[Greedy Algorithm] 욕망의 알고리즘

서광채·2022년 5월 2일
3
post-thumbnail

💡 Greedy Algorithm탐욕 알고리즘이란?

😈 현재 상황에서 가장 좋은 것(최선의 선택)을 고르는 알고리즘을 말한다.

그리디 알고리즘은 동적 프로그래밍을 간단한 문제 해결에 사용하면 지나치게 많은 일을 한다는 것을 착안하여 고안되었다.동적 프로그래밍을 대체하는 것은 아니고 같이 쓰이며 서로 보완하는 개념이다.

탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 이렇게 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적해를 보장해주는 것은 아니다.


❓ 여기서 가장 좋은 것(최선의 선택)이란?

순간마다 하는 선택이 최선이면, 결과도 최선 아닌가?? → 아닙니다

그리디 알고리즘이 추구하는 가장 좋은 것에 대해 예시를 들어 알아보자.

우리가 시작 부분에서 시작해서 지나간 Path의 돈을 받는 문제?로또? 아무튼 있다고 가정하면, 가능한 가장 큰 돈을 얻는 경로를 이용하길 원할 것이다.

우리는 가장 좋은 결과가 “시작 - 5백만원 - 5조”를 거치는 Path가 가장 큰 돈을 얻을 수 있다는 것을 알 수 있다. (벼락부자 ㄱㅇㄷ)

하. 지. 만. 그리디 알고리즘을 사용한다면 시작 지점의 바로 앞만 보고, 5천만원을 선택하게 된다. 결론적으로 이 ... 미련한 그리디 알고리즘은 “시작 - 5천만원 - 5천원”이란 Path가 가장 좋은 것이라고 판단한다.

이처럼 그리디 알고리즘은 순간의 가장 좋은 결과를 선택하는 방식이다.


🚩 그리디 알고리즘 문제 해결 과정

  1. 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다.
  2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다.
  3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

🧩 그리디 알고리즘 조건

그리디 알고리즘을 사용하기 위해 필요한 조건은 2가지가 있다.

1. 탐욕적 선택 속성(Greedy Choice Property)

: 탐욕적인 선택은 항상 안전하다는 것이 보장되어야 한다. 여기서 “안전하다”라는 것은 이 선택으로 인해 전체 문제의 최적해를 반드시 도출할 수 있어야 한다는 것이다.

엥 뭔소리야. 위에서는 그리디 알고리즘을 사용해 결과를 도출하면 최적해가 나오는 건 아니라며?
그리디 알고리즘을 사용하면 무조건 최적해가 나오는 것은 아니다. 하지만 그리디 알고리즘을 사용해 푸는 문제가 나왔을 때 이 조건이 만족되느냐를 생각해보고 충족될 때 그리디 알고리즘을 사용하는 것이다.
즉, 그리디 알고리즘을 사용했을 때 최적해(가장 좋은 결과)가 나올 수 있는 문제에 이를 사용할 수 있다는 것.

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

: 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다는 조건이다. 이 말은 전체 문제의 안에는 여러 단계가 존재하고, 이 여러 단계 내의 각 단계에 대해 최적해가 도출되어야 한다는 것이다.

그리디 알고리즘에서 고려해야 하는 상황은 값들이 서로 영향을 주면 안된다는 것을 염두에 두어야 한다.

쉽게 풀어 아까 본 예시로 설명해보자면, 그리디 알고리즘이 도출한 최종 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탐욕-알고리즘-구현하기

profile
근거있는 자딘감

1개의 댓글

comment-user-thumbnail
2022년 5월 4일

욕망의 서광채 잘보고 갑니다 ^^*

답글 달기