CHAPTER 03 그리디

그리디 알고리즘이란 현재 상황에서 지금 당장 좋은 것만 고르는 문제해결 방법이다.

 

예제3-1

카운터에는 거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 가정한다.

손님에게 거슬러줘야할 돈이 N원일 때, 거슬러줘야 할 동전의 최소 개수를 구하라.

단, 거슬러줘야 할 돈 N은 항상 10의 배수이다.

const coin_types = [500, 100, 50, 10];
let money = 1260;
let result = 0;

coin_types.forEach((coin) => {
  result = result + Math.floor(money / coin);
  money = money % coin;
});
console.log(result);

이 문제를 풀면서 느낀점은 forEach 구문 자체가 for문 처럼 작동하는다는 것과, map과의 차이로 map은 배열을 반환하는 반면,

forEach는 새로운 배열을 반환하지 않는다. 또한 어떻게 money에 재할당을 하고 다시 for문을 돌리는 것처럼 작동한다는 것을 알게되었다. 어떻게 money에 어떻게 저장을 하면서 할까 생각했는데 저렇게 하는 거였다. 이번에 배운 점은 큰것부터 해보자 라는 아이디어였다.