탐욕 알고리즘(Greedy Algorithm)

탐욕 알고리즘(Greedy Algorithm)

• 탐욕적이다 => 근시안적으로 의사 결정을 내리지만 최선이길 바라는 알고리즘입니다.
• 즉, 각 단계에서 최선의 선택을 하는 알고리즘
• 굳이 최적의 답을 구하려고 노력하지 않고 적당히 괜찮은 답을 찾으려고 합니다.

구성 요소

• 해 선택(Selection Procedure) : 현재 상황에서 가장 최선의 후보를 선택
• 적절성 검사(Feasibility Check) : 선택된 후보가 답이 될 수 있는지 제약 사항 검사
• 해 검사(Solution Check) : 현재까지 선택된 해가 문제의 정답이 되었는지 검사하고 정답이 아니라면 다시 시작

장점

최적의 답을 구하는 알고리즘보다 계산이 단순하고 시간이 적게 걸립니다.

단점

항상 최적의 답을 구해주는 것은 아니기때문에 상황에 맞게 적절히 사용해야합니다.

예시)

동전 거스름돈

// cost : 거스름돈
// coin : 동전 종류
// count : 거스름돈 동전 {종류 : 갯수}

function changeCoin(cost, coin) {
  count = {}
  while(cost>0) {
    for(var i=0; i<coin.length; i++) {
      if(cost/coin[i] >= 1) {
        count[coin[i]] = Math.floor(cost/coin[i])
        cost = cost%coin[i]
      }
    }
  }
  return count
}

console.log(changeCoin(570,[100, 50, 10]))
// { '10': 2, '50': 1, '100': 5 }

 

최적의 답을 구하지 않는 예시

조건 : 최소한의 동전 개수를 이용하여 거스름돈을 만들어라

function changeCoin(cost, coin) {
  count = {}
  while(cost>0) {
    for(var i=0; i<coin.length; i++) {
      if(cost/coin[i] >= 1) {
        count[coin[i]] = Math.floor(cost/coin[i])
        cost = cost%coin[i]
      }
    }
  }
  return count
}

console.log(changeCoin(800,[500, 160, 100, 10]))

// changeCoin함수 실행 결과
// { '10': 4, '100': 1, '160': 1, '500': 1 }

// 최적의 답
// { '100': 3, '500': 1 }

탐욕 알고리즘을 이용한 정답 :  7개 

최적의 정답 : 4개

 

결론

상황에 맞게 잘 쓰자