오르막 계단 문제: 해결 방법 및 피보나치 수와 관련된 이유

오늘의 알고리즘은 Climbing Stairs problem입니다.

You are climbing a stair case. It takes n steps to reach to the top. Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?
Note: Given n will be a positive integer.

예를 들어 입력이 2인 경우(계단에 2개의 계단이 있음) 정상에 오르는 데는 2가지 뚜렷한 방법이 있습니다. 한 번에 한 계단씩 오를 수도 있고 두 계단을 동시에 오를 수도 있습니다.



이것은 재귀, 메모이제이션, 동적 프로그래밍을 포함하여 해결할 수 있는 많은 방법이 있는 문제 중 하나이지만 제가 가장 좋아하는 솔루션은 피보나치 수와 관련이 있습니다. 이 게시물에서는 피보나치 수의 정의, 이 문제와의 관련성 및 알고리즘을 해결하는 방법에 대해 설명합니다.

피보나치 수

그들은 무엇인가?

피보나치 수(피보나치 수열이라고도 함)는 재귀 방정식으로 정의되는 일련의 수입니다.

Fn = Fn-1 + Fn-2

시퀀스는 F0 = 0 및 F1 = 1로 시작합니다. 즉, F2 = F1 + F0 = 1 + 0이므로 F2 = 1입니다. 그런 다음 F3 = F2 + F1 = 1 + 1이므로 F3 = 2입니다. 시퀀스 무한히 계속됩니다: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34...

피보나치 수here에 대한 자세한 내용을 읽을 수 있습니다.

피보나치 수가 계단 문제와 관련된 이유는 무엇입니까?

계단 문제의 예상 출력에 대한 몇 가지 예를 살펴보겠습니다. n = 0부터 시작할 수 있습니다. 즉, 계단의 단계가 0입니다. 이 계단을 오르는 방법은 0개이므로 n = 0일 때 출력 = 0입니다.



n = 1일 때 계단은 1단입니다. 이 계단을 오르는 방법은 하나이므로 n = 1일 때 출력 = 1입니다.



n = 2일 때 계단에는 2개의 단계가 있습니다. 한 번에 1개 또는 2개의 계단을 오를 수 있으므로 이 계단을 오르는 방법은 2가지가 있습니다. 따라서 n = 2일 때 출력 = 2입니다.



n = 3일 때 계단에는 3개의 단계가 있습니다. 이 계단을 오르는 방법은 3가지가 있습니다.



n = 4(출력 = 5)일 때 이 작업을 계속할 수 있습니다...



... 및 n = 5(출력 = 8).



출력에 패턴이 있습니까?



출력에서 피보나치 수열을 볼 수 있습니다! n을 증가시킬 때마다 계단을 오르는 방법의 수는 이전 두 방법의 합입니다. 즉 n에 도달할 때까지 각 계단에서 피보나치 수를 풀면 계단 문제를 풀 수 있습니다.

알고리즘 해결

출력에서 패턴을 인식했으므로 이제 알고리즘을 풀 수 있습니다. 시작하려면 몇 가지 기본 사례를 작성해야 합니다. n이 0, 1, 2일 때 계단을 오르는 방법의 수는 0, 1, 2(순서대로)입니다. 따라서 n이 그 숫자 중 하나라면 그냥 n을 반환하면 됩니다.

function climbStairs3(n) {
  if (n < 3) return n;
  //...
}

first 와 second 라는 두 개의 상수를 초기화해야 합니다. first를 1로 설정하고 second를 2로 설정하는 것으로 시작합니다. 이 숫자를 사용하여 현재 사용 중인 숫자를 더하고 계속 변경할 것입니다.

function climbStairs3(n) {
  if (n < 3) return n;
  let first = 1;
  let second = 2;
  //...
}

이제 숫자 2에서 시작하여 n에 도달할 때까지 한 번에 숫자 하나씩 증가하는 for 루프를 가질 수 있습니다. for 루프 내에서 current 및 first 의 합계를 저장할 second 라는 새 변수를 시작합니다. 그런 다음 first를 equal second로, second를 equal current로 이동할 수 있습니다.

for 루프가 끝나면 second 숫자가 무엇이든 반환하려고 합니다.

function climbStairs3(n) {
  if (n < 3) return n;
  let first = 1;
  let second = 2;
  for (let i = 2; i < n; i++) {
    const current = first + second;
    first = second;
    second = current;
  }

  return second;
}

--

질문이나 다른 해결 방법이 있으면 알려주세요!