사용한 동전
만든 금액
가능한 최소

    동전(¢)

      동전 교환 문제 더 알아보기

      동전 교환 문제

      몇 가지 종류의 동전이 있을 때, 정확한 금액을 가능한 한 적은 동전으로 내려면 어떻게 해야 할까요? 그리고 낼 수 있는 방법은 모두 몇 가지일까요? 큰 동전부터 고르는 그리디 방법은 실제 화폐에서는 통하지만 어떤 동전 조합에서는 실패합니다. 모든 금액을 더 작은 금액에서 쌓아 올리는 표는 언제나 정답을 구합니다. 트레이의 동전을 탭하면 계산대에 올라가고, 계산대의 동전을 탭하면 다시 돌아옵니다. 미터가 목표 금액을 향해 채워집니다. 되도록 적은 동전으로 금액을 정확히 맞추세요. 최소 동전 수는 가장 좋은 답을, 그리디는 넘지 않는 가장 큰 동전을 항상 고를 때의 결과를 보여 주는데, 이것이 항상 최소는 아닙니다. 패널에서 동전(센트 단위)과 금액을 바꿀 수 있습니다. 표 보기에서는 동적 계획법이 최소 동전 수를 찾거나 금액을 만드는 방법의 수를 세는 과정을 보여 줍니다. 재생을 누르면 표가 채워지는 모습을 볼 수 있고, 단계와 뒤로를 누르면 한 단계씩 움직이며, 단계 슬라이더를 끌면 원하는 곳으로 이동합니다. 각 동전은 몇 번이든 쓸 수 있습니다. 표를 선택한 상태에서는 화살표 키로 한 단계씩 움직이고, 스페이스 바로 재생과 일시 정지를 하며, Home과 End로 처음과 끝으로 이동합니다.

      작동 원리

      1. 트레이의 동전을 눌러 금액을 정확히 맞추고, 미터가 센트 단위로 채워지는 모습을 확인하세요.
      2. 가능한 한 적은 동전을 써 본 뒤, 최소 동전 수 또는 그리디 버튼을 눌러 비교하세요.
      3. 표 보기를 열고 재생을 눌러 각 칸이 의존하는 더 작은 금액을 읽는 과정을 지켜보세요.

      최소 동전 수

      금액 0에는 동전이 필요 없습니다. 그보다 큰 각 금액에서는 그 금액보다 크지 않은 동전을 하나씩 시도합니다. 그 동전을 쓰고 남은 것은 이미 표에 있는 더 작은 금액이므로, 동전 하나를 더하면 후보가 됩니다. 가장 작은 후보가 칸에 들어가고, 그 후보를 만든 동전은 아래 행에 기록됩니다. 표가 다 채워지면 목표 금액부터 동전을 거꾸로 읽어 냅니다. 그 금액의 마지막 동전을 꺼내고, 남은 금액으로 가서 0이 될 때까지 반복합니다.

      방법의 수

      순서가 아니라 조합을 세기 위해 표는 행마다 동전을 하나씩 추가합니다. 각 칸은 그 행까지의 동전으로 자기 금액을 만드는 방법의 수를 셉니다. 가장 새로운 동전을 쓰지 않는 방법, 즉 위 칸에, 가장 새로운 동전을 적어도 한 번 쓰는 방법, 즉 같은 행에서 그 동전 값만큼 왼쪽에 있는 칸을 더합니다. 동전이 정해진 순서로 추가되므로 1 + 2와 2 + 1은 같은 방법이고 한 번만 셉니다.

      자주 묻는 질문

      그리디 방법은 왜 실패하나요?

      그리디는 항상 남은 금액을 넘지 않는 가장 큰 동전을 고르고 결코 다시 생각하지 않습니다. 동전 1, 3, 4로 금액 6을 만들 때 4를 고른 다음 1과 1을 고릅니다. 3 두 개면 충분한데 동전 세 개를 씁니다. 유로나 미국 달러 같은 동전 체계에서는 그리디가 마침 최적입니다. 이런 체계를 캐노니컬(정규) 동전 체계라고 합니다.

      방법의 수를 세는 것과 순서의 수를 세는 것은 어떻게 다른가요?

      방법은 1 + 2와 2 + 1을 같은 조합으로 보고, 순서는 따로 셉니다. 이 앱은 동전을 한 행씩 추가해 방법의 수를 셉니다. 순서를 세려면 대신 금액을 차례로 훑으면서 각 금액마다 모든 동전을 시도합니다.

      동전 교환 알고리즘은 얼마나 빠른가요?

      두 표 모두 동전 종류 수 곱하기 금액만큼의 단계가 걸립니다. 수천 정도의 금액이라면 빠르지만, 금액은 엄청나게 큰 수일 수도 있으므로 자릿수를 기준으로 재면 이 문제는 일반적으로 NP-난해입니다.

      금액을 만들 수 없으면 어떻게 되나요?

      그 칸은 ∞로 남습니다. 예를 들어 동전 2와 5로 금액 1과 3을 만들 때가 그렇습니다. 방법의 수 모드에서는 그 값이 그냥 0입니다.

      데이터가 어딘가로 전송되나요?

      아니요. 모든 계산은 브라우저에서 이루어지고, 마지막 설정은 이 브라우저의 로컬 저장소에 남습니다.

      시도해 볼 준비가 되셨나요?

      브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.

      편집기로 이동