그리디 알고리즘 (Greedy Algorithm)

April 04, 2021

그리디 알고리즘 (Greedy Algorithm)

그리디 알고리즘, 탐욕 알고리즘 이라고도 부른다. 그리드 알고리즘 정의는 아래와 같다.

정의

최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각 되는것을 선택해 나가는 방식이다.

구현

만약 10, 7, 5, 1 로 구성되어 있는 동전들로 14를 교환해준다고 했을 때 그리디 알로리즘을 사용하면 10-1개 1-4개로 구성될 것이다. 왜냐하면 그리디 알고리즘은 해당순간에 가장 최선의 해를 내는 알고리즘이기 때문이다. 하지만 전체적으로 봤을 때 최선의 해라고 볼 수 없다. 왜냐하면 7-2개로 구성하는 것이 가장 최선의 해답이기 때문이다. 아래 코드를 보면 알겠지만 매 순간 최선의 선택을 했다고해서 종합적으로 봤을 때에 최선의 선택이라고는 볼 수 없다.

N 거스름돈을 “10000, 5000, 1000, 500, 100, 50, 10 동전” 들로 줄수 있는 solution 을 그리드 알고리즘을 활용 하여 구현하라.

function solution(value) {
  let moneys = [10000, 5000, 1000, 500, 100, 50, 10]
  let won = Math.floor(value / 10) * 10
  let i = 0
  let counts = []

  while (true) {
    if (won >= moneys[i]) {
      let count = Math.floor(won / moneys[i])
      won = won - moneys[i] * count
      counts[i] = count
    } else {
      counts[i] = 0
    }

    i++
    if (won === 0) {
      for (let j = 0; j < moneys.length - i; j++) {
        counts.push(0)
      }
      break
    }
  }

  moneys.map((money, index) => {
    console.log(`${money.toLocaleString()}${counts[index]}`)
  })
}

solution(51865)

// 10,000원 5개
// 5,000원 0개
// 1,000원 1개
// 500원 1개
// 100원 3개
// 50원 1개
// 10원 1개

데모

https://codepen.io/pen/?template=yLgbWPj


Written by Jeon Byung Hun 개발을 즐기는 bottlehs - Engineer, MS, AI, FE, BE, OS, IOT, Blockchain, 설계, 테스트