[JS] 코딩 테스트 문제 : 동전 교환 [배낭(KnapSack) 알고리즘]

문제 : 동전 교환(냅색 알고리즘)

문제 설명

다음과 같이 여러 단위의 동전들이 주어져 있을때 거스름돈을 가장 적은 수의 동전으로 교환해주려면 어떻게 주면 되는가? 각 단위의 동전은 무한정 쓸 수 있다.

▣ 입력설명

첫 번째 줄에는 동전의 종류개수 N(1<=N<=12)이 주어진다. 두 번째 줄에는 N개의 동전의 종류가 주어지고, 그 다음줄에 거슬러 줄 금액 M(1<=M<=500)이 주어진다.

각 동전의 종류는 100원을 넘지 않는다.

▣ 출력설명

첫 번째 줄에 거슬러 줄 동전의 최소개수를 출력한다.

▣ 입력예제 1

3
1 2 5
15

▣ 출력예제 1

3

설명 : 5 5 5 동전 3개로 거슬러 줄 수 있다.

오답 노트

function solution(m, coin) {
  let answer = 0;
  let answerArr = [];
  sortArr = coin.sort((a, b) => b - a);

  for (const c of sortArr) {
    let quotient = Math.floor(m / c);
    if (quotient > 0) {
      m = m - quotient * c;
      answer += quotient;
      answerArr.push(quotient);
    } else answerArr.push(0);
  }

  console.log("코인당 거슬러준 개수: ", answerArr);
  return answer;
}

let arr = [1, 2, 5];
//  let arr = [1, 3, 4]; // 오류가 생기는 예시
console.log(solution(15, arr));

풀이

그리디 방식을 적용한 풀이

1. 주어진 여러 단위의 동전들을 내림차순 정렬 후 동전들을 반복하며 현재 금액(m)을 현재 단위 동전의 값을 나눠 몫을 구해 quotient 변수에 저장
2. 현재 동전 단위로 나눠 몫이 존재하는 경우 현재 금액에서 거스름돈 차감하고 거스러준 동전의 개수 answer 변수에 더해 저장
3. 최종적으로 거스러준 동전의 개수를 의미하는 answer 변수를 반환

문제점

가장 큰단위 기준으로 거스름돈을 주기 시작한 경우 최적해를 보장하지 않는 경우가 생깁니다.

예를 들어 동전 단위가 1원, 3원, 4원인 경우에 6원을 거슬러 줘야할 때 그리디 방식은 4원 1개 1원 2개를 거슬러 주어 총 3개의 동전을 거슬러 주지만 3원 동전 2개로 거슬러준다면 2개의 동전만으로 거슬러 줄 수 있습니다.

다른 해결 방법

배낭(KnapSack) 알고리즘 사용

function solution(m, coin) {
  let answer = 0; // 거슬러 줄 동전의 최소개수

  // 거슬러 줄 금액 + 1 길의 배열 선언 후 각각 1000 으로 초기화
  // 각각의 배열 인덱스 금액만큼 거슬러줄 동전의 개수를 배열에 저장해 사용 예정
  let dy = Array.from({ length: m + 1 }, () => 1000);
  dy[0] = 0;

  // ※ 풀이 방식
  // 주어진 여러 단위의 동전을 기준으로 1 ~ m 금액을 거슬러 줄 동전의 개수를 저장합니다.
  // 만약 이전에 다른 동전 단위로 저장한 동전의 개수 현재 단위의 동전으로 거슬러 줄 동전의 최소개수를 비교해 최소 값을 배열에 저장
  // 최종적으로 여러단위의 동전을 모두 확인과정을 마치면 1 ~ m 금액들은 모두 거슬러 줄 동전의 최소개수를 저장하게 됩니다.

  // 주어진 여러 단위의 동전들을 반복
  for (let i = 0; i < coin.length; i++) {
    // 현재 동전 단위 값부터 전체 금액까지 반복
    for (let j = coin[i]; j <= m; j++) {
      // 기존 배열의 값과 현재 동전 단위만큼 이전의 배열값에 + 1 값을 비교해 작은 값을 배열에 저장
      dy[j] = Math.min(dy[j], dy[j - coin[i]] + 1);
    }
  }

  // 배열의 마지막 값 즉 최종적으로 거슬러 줄 금액의 거슬러 줄 동전의 최소개수 정답 변수에 저장
  answer = dy[m];
  return answer;
}

let arr = [1, 2, 5];
//  let arr = [1, 3, 4]; // 오류가 생기는 예시
console.log(solution(15, arr));

풀이

배낭(KnapSack) 알고리즘을 활용한 접근방식

주어진 여러 단위의 동전을 기준으로 1 ~ m 금액을 거슬러 줄 동전의 개수를 배열에 저장합니다.
만약 이전에 다른 동전 단위로 저장한 동전의 개수와 현재 단위의 동전으로 거슬러 줄 동전의 최소 개수를 비교해 최소 값을 배열에 저장

최종적으로 여러 단위의 동전을 모두 확인 과정을 마치면 1 ~ m 금액들은 모두 거슬러 줄 동전의 최소 개수를 저장하게 됩니다.

1. 거슬러 줄 금액 + 1 길이의 배열 dy 선언 후 각각 1000 으로 초기화
2. 주어진 여러 단위의 동전들을 반복하고 그 안에서 현재 동전 단위 값부터 전체 금액까지 반복하며 기존 배열의 값과 현재 동전 단위만큼 이전의 배열값에 + 1 값을 비교해 최소 값을 배열에 저장
3. 배열의 마지막 값 즉 최종적으로 거슬러 줄 금액의 거슬러 줄 동전의 최소 개수를 정답 변수 answer에 저장 후 반환

---

참고

https://www.inflearn.com/course/lecture?courseSlug=%EC%9E%90%EB%B0%94%EC%8A%A4%ED%81%AC%EB%A6%BD%ED%8A%B8-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EB%AC%B8%EC%A0%9C%ED%92%80%EC%9D%B4&unitId=64177