자바스크립트 5줄로 계단 문제를 해결하는 방법

알고리즘과 leetcode를 처음 사용하는 경우 계단 문제는 악명 높습니다!

계단 프로그래밍 챌린지가 무엇인가요?

간단히 말해서....
N 계단이 있는 계단을 상상해 보십시오. 한 번에 1, 2, 3단계를 걸을 수 있다면 계단 꼭대기에 도달할 수 있는 방법은 몇 가지입니까?

이런 문제를 처음 접하는 것은 확실히 두려운 일입니다. 수학 문제 자체로도 정말 어렵습니다.

몇 가지 분명한 경우가 있습니다. 한 번에 1걸음씩 N번 걸을 수 있습니다. N가 2로 나누어지면 2단계를 N/2번 수행할 수 있습니다. 또한 N가 3으로 나누어지면 3단계를 N/3번 수행할 수 있습니다.

그리고 그 사이에 모든 것이 있습니다. 🤔

좋은 소식은 모두가 좋아하는 알고리즘인 재귀를 사용하여 이 문제를 해결할 수 있는 정말 간단한 방법이 있다는 것입니다. 😨

구조에 대한 재귀

약속한 대로 여기에 5줄의 JavaScript 코드로 된 해결책이 있습니다...

// N is total number of steps in the staircase
// stepTaken is a counter for steps taken in each combination
function steps(N, stepsTaken = 0) {

  if (stepsTaken === N) return 1;
  else if (stepsTaken > N) return 0;

  return steps(N,stepsTaken + 1) + steps(N,stepsTaken + 2) + steps(N,stepsTaken + 3);
}

이런! 이것은 무엇을 의미 하는가??

*위의 코드가 혼란스러워도 당황하거나 기분 나빠하지 마세요. * 고등학교 CS 시간에 재귀를 처음 배운 이후로 오랫동안 재귀와 씨름했습니다. 확실히 까다 롭습니다. * 그러나 일단 이해하면 완전히 새로운 가능성의 세계가 열립니다!*

이 솔루션을 살펴보겠습니다.

위의 솔루션을 그대로 복사하고 떠날 생각이라면 요점을 놓치고 있는 것입니다. 무슨 일이 일어나고 있는지 이해하는 것이 매우 중요합니다.
function steps(N, stepsTaken = 0)는 단순한 재귀 카운터입니다.

살펴보겠습니다.

우리는 계단 맨 아래에 있습니다. 발걸음을 떼지 않았습니다. 그래서 stepsTaken = 0 .

3가지 가능성이 있습니다: 1보 이동, 2보 점프 또는 3보 도약.

이제 세 가지 가능성을 모두 고려해야 합니다. 계단과 자신을 2번 복제한다고 상상해 보십시오. 또한, 각자 자신만의 버전의 stepsTaken 변수를 휴대할 수 있습니다.
귀하와 귀하의 클론은 각각 다음 '문' 중 하나를 통과합니다(각각 다른 문을 통과해야 함).

steps(N,stepsTaken + 1)
steps(N,stepsTaken + 2)
steps(N,stepsTaken + 3)

선택한 문을 통과하면 개인stepsTaken 카운터가 1, 2 또는 3씩 증가합니다(통과한 문에 따라). 그런 다음 즉시 3개의 문이 더 표시됩니다.

steps(N,stepsTaken + 1)
steps(N,stepsTaken + 2)
steps(N,stepsTaken + 3)

다시, 자신을 2번 복제하고 각각 이 문steps 중 하나를 통과합니다. 귀하의 stepsTaken 카운터는 다시 1, 2 또는 3씩 증가합니다. 이는 다음까지 계속됩니다.

  if (stepsTaken === N) return 1;
  else if (stepsTaken > N) return 0;

넘어진 경우stepsTaken > N, 계단 조합은 계단을 오르는 고유한 방법의 합계에 포함되지 않습니다.

그러나 if (stepsTaken === N) , 빙고 🤩 당신은 계단을 오르는 합법적인 콤보를 찾았고 당신return 1은 계단을 오르는 방법의 수에 추가합니다.

이제 stepsTaken 계단의 꼭대기에 도달하기 위해 N의 가능한 조합 수를 세는 방법은 단순히 모든 가능성을 추가하는 것입니다.

return steps(N,stepsTaken + 1) + steps(N,stepsTaken + 2) + steps(N,stepsTaken + 3);

if (stepsTaken === N) return 1 및 경로가 유효하지 않은 경우(오버스텝) 각각 0이 반환되는 각각의 적법한 단계 콤보를 기억하십시오: else if (stepsTaken > N) return 0 .

여러분 중 일부는 다음과 같이 질문할 수 있습니다. 좋습니다. 이것은 우아하지만 시간 복잡도 측면에서 매우 비효율적이지 않습니까?

예, 매우 높은 시간 복잡도입니다. 하지만 그것을 획기적으로 개선하는 비결이 있습니다 ➡️ How to Solve the Staircase Problem with JavaScript using Memoization

이것이 의미가 있기를 바랍니다. 질문이 있으면 아래에 의견을 말하십시오.

이 기사가 마음에 드셨다면 제 블로그Indepth JavaScript에서 더 많은 정보를 얻으실 수 있습니다. 🤓