1. 동전 교환

dfs때 풀었던 알고리즘인데 동전의 갯수가 많아지고 거슬러야 할 돈이 커지면 그 유명한 stack overflow가 나게 된다. 이때 필요한게 다이나믹 알고리즘이다.

2. 접근 방법

우선 거스름돈 숫자를 길이로 하는 다이나믹 배열을 만든다. 예를 들어 20원을 바꿔줘야한다고 했을때 0부터 거스름돈 까지 바꿔줄 수 있는 경우를 순서대로 찾아간다. 이때 다음 숫자의 거스름돈은 그 전의 숫자의 거스름돈의 경우의 수에서 누적하여 계산한다.

이때 동전의 크기에서 부터 시작한다. 그리고 올라가면서 1씩 더하고 기존의 있던 값보다 작으면 할당한다.

다시 말해, 지금 1원밖에 없고 6원을 바꿔줘야하는 위치에 있으면 5원을 바꾸어줄때 발생되는 최소 동전의 갯수에다가 1을 더하면 된다. 지금 가지고 있는게 2원이고 바꿔줘야하는 돈이 6원이라면 4원을 바꾸어줄때 발생되는 최소 동전의 갯수에다가 1을 더하면 된다. 2원이고 4원을 바꿔줘야할때 [2,2] 이므로 6원은 여기다가 2원짜리 동전 하나만 더 하면 되기 때문.

말로는 도저히 무슨말인지 이해하기 힘들 수 있다. 그래서 그림으로 그려보았다.

1원을 가지고 있을때 2원을 바꾸어주어야 하는 경우/ 1,2원을 가지고 있을때 8원을 바꾸어주어야 하는 경우/ 1,2,5원을 가지고 있을때 14원을 바꾸어주어야 하는 경우를 뽑아서 그림에 명시해놓았다.

그럼 코드로 표현해보자.

• pseudo code
  • 거스름돈을 길이로 하는 다이나믹 배열을 만든다
  • 이중포문을 만든다.
  • coin을 차례로 선택하고 선택된 coin이 0원 부터 거스름돈까지 최소한으로 쓰일 수 있는 갯수를 구한다.
    • 그리고 현재 선택된 coin수 부터 다이나믹을 루프한다.(왜냐면 그 이전의 거스름돈은 현재코인으로 바꿔줄 수 없으므로)
    • 현재 coin의 크기만큼 배열에서 그 전으로 돌아가서 할당된 값을 본다. 그리고 그 값에 1을 더해서 값이 적으면 현재 배열에 할당한다.

function dynamicCoinChanger(coins, changes) {
  let dy = Array.from({ length: changes + 1 }, () => 1000);

  dy[0] = 0;

  for (let i = 0; i < coins.length; i++) {
    for (let j = coins[i]; j < dy.length; j++) {
      dy[j] = Math.min(dy[j - coins[i]] + 1, dy[j]);
    }
  }

  return dy[changes];
}

dynamicCoinChanger([1, 2, 5], 15);

// 3 [ 5,5,5]

직관적으로 이해하기는 좀 힘들 수 있겠지만 그림그려보고 계속 코드를 작성하다보면은 익숙해진다.

오케이 끝!