매주 제공되는 일련의 코딩 과제 및 인터뷰 관련 콘텐츠인 Code Review의 또 다른 주에 다시 오신 것을 환영합니다. 지난주에 우리는 재귀에 대해 논의하기 시작했습니다. 놓친 경우 - 지난 주 기사를 확인하십시오. 또한, 새로운 뉴스레터를 공개했습니다! 귀하의 이메일here을 알려주시면 귀하를 "최초로 알 수 있는"목록에 추가하겠습니다.

해결책

이 솔루션에는 재귀가 포함됩니다! 보다 "동적 프로그래밍"접근 방식으로 문제를 해결한 경우 아래에 해결 방법을 설명하십시오.

알고리즘 문제를 해결하는 데 도움이 되는 것은 잠시 멈추고 내 두뇌가 이 문제를 어떻게 해결할지 생각하는 것입니다. 특정 액면가의 동전으로 일정 금액을 거스름돈으로 바꾸는 방법을 세어야 한다면 어떻게 될까요?

1센트와 2센트의 가치가 있는 동전으로 5센트를 벌어야 한다고 가정해 봅시다. 나는 아마도 2센트 동전 하나를 가지고 시작하여 내가 원하는 총 5센트에서 2센트를 빼고 나머지 3센트로 작업할 것입니다. 2센트짜리 동전을 하나 더 가져와 나머지 3센트에서 빼면 내가 원하는 5센트를 만드는 데 필요한 1센트가 남습니다. 이 경우 1센트. 그렇게 하면 5센트가 되고 2센트와 1센트로 5센트를 만드는 한 가지 방법입니다. 그리고 나는 모든 방법을 찾을 때까지 그렇게 동전 목록을 계속 내려갈 것입니다. 코드로 변환하는 방법? 음, 내 총 남은 센트가 0일 때 방법을 찾은 것 같죠? 그것은 기본 사례처럼 들립니다. 그리고 우리가 원하는 총계를 마이너스 영역으로 넘어가면 그것은 방법이 아닙니다. 그것은 또한 기본 사례처럼 들립니다.

// see if you can spot the bug before I complete this function below!
function coins (amount) {
 const coinsArr = [ 1, 2 ]
 if (amount === 0) return 1
 if (amount < 0) return 0

 let numberOfWays = 0
 for (let i = 0; i < coinsArr.length; i++) {
   numberOfWays += coins(amount - coinsArr[i])
 }
 return numberOfWays
}

기본 사례 이후에 기본적으로 동전 배열을 반복하여 나머지 금액을 변경하려고 합니다.

걸어가다

이 재귀 트리를 따를 수 있도록 몇 가지 입력을 살펴보겠습니다. 먼저 amount = 4 로 함수를 호출합니다. 첫 번째 동전 1부터 시작하여 현재 금액인 4에서 빼서 3을 얻습니다. 그런 다음 해당 숫자로 coins를 다시 호출합니다. 그런 다음 양 3으로 coins 함수를 다시 입력하고 첫 번째 동전 1부터 다시 시작합니다. 3에서 1을 빼고 동전을 2로 다시 호출합니다. 1에서 1을 빼고 0을 얻을 때까지 계속합니다. 첫 번째 기본 사례를 선택하고 numberOfWays 변수에 1을 추가합니다. 이것이 1,1,1,1 방식입니다. 우리는 (양이 1인) for 루프로 돌아가서 2를 빼고 -1을 얻습니다. 이것은 우리를 다른 기본 사례로 가져오고 0을 반환합니다. 등등. 이것은 아래 트리로 표시됩니다.



아직 발견하지 못하셨나요?

맞습니다. 동일한 동전의 다른 순열로 인해 일부 조합을 여러 번 계산하고 있습니다. 1,1,2, 1,2,1 및 2,1,1은 우리의 목적을 위해 모두 동일한 조합입니다. 그렇다면 coins 함수를 호출할 때마다 각 for 루프를 다시 시작하지 않는 방법은 무엇입니까? 물론 우리가 원하는 코인을 전달하세요! 또 다른 좋은 팁 - 함수 서명에 대해 면접관과 이야기하십시오. 추가 매개변수가 언제 필요하거나 필요할지 알 수 없습니다. 일반적으로 이것은 면접관과 좋은 대화 포인트가 될 수 있습니다. 부끄러워하지 마세요!

코드는 다음과 같습니다.

function coins (amount, idx) {
 const coinsArr = [ 1, 2 ]
 if (amount === 0) return 1
 if (amount < 0) return 0

 let numberOfWays = 0
 for (let i = idx; i < coinsArr.length; i++) {
   numberOfWays += coins(amount - coinsArr[i], i)
 }
 return numberOfWays
}

다음은 이를 시각화하는 데 도움이 되는 트리입니다.



모두 수고하셨습니다! 다음 주에 제가 가장 좋아하는 사이드 프로젝트Breadwinnerss를 구축한 방법에 대해 자세히 설명하겠습니다.