Greedy

Greedy(욕심쟁이)라는 말처럼 현재상태에서 최고의 선택만을 하는 것이다.
나중에 어떻게 되는지는 고려하지 않는다 지금 당장 좀 더 좋은 조건을 찾는 것이다.

장점

만들기가 쉽다. (특별히 고려할 것 없이 좋은거 고르면 된다.)
구상하기도 쉽다. (현재의 상태만 고려하면 된다.)
시간이 오래 걸리지 않는다. (현재 상태만 보기에 작동시간이 어지간하면 짧다.)

단점

멍청하다 (눈앞의 좋은 조건만 고르면 되니까 나중에 더 좋은 결과를 못 얻을 수 있다.)

다음은 거스름돈을 100원, 50원, 10원단위로 몇개를 어떻게 줘야할는 알려주는 함수이다.
100원으로 줄 수 있는 만큼 주고 100원보다 적은 금액은 50원, 10원을
100원과 같은 계산을 하여 100원은 몇개고, 50원은 몇개고, 10원은 몇개인지 알려준다.

function howToGiveChange(change) {
  let targetChange = change
  let coin100 = 0;
  let coin50 = 0;
  let coin10 = 0;

  while(parseInt(targetChange/100) > 0) {
    coin100++
    targetChange -= 100;
  }

  if (targetChange >= 50) {
      while(parseInt(targetChange/50) > 0) {
        coin50++
        targetChange -= 50;
      }
  }

  if (targetChange >= 10) {
      while(parseInt(targetChange/10) > 0) {
        coin10++
        targetChange -= 10;
      }
  }

  return `100원은 ${coin100}개, 50원은 ${coin50}개, 10원은 ${coin10}개 입니다.`
}

howToGiveChange(1940)

하지만 함정이 있다.
1,4,5원이 있을 경우 8원을 거슬러준다고하면,
5원짜리 1개, 1원짜리 3개가 될 것이다.
4원짜리 2개가 더 갯수가 적고 좋은 방법인데 말이다.

결론

욕심쟁이 알고리즘은 현재 상태에서 최선의 행동 만을 하는 알고리즘이다.
만들거나 생각하기가 쉽다는 장점이 있다.
오류가 생길 가능성이 높다.