JavaScript로 풀어보는 계단 오르기 문제: 피보나치 수열의 활용

문제 정의

n개의 계단이 있고, 한 사람이 계단 아래에서 꼭대기까지 올라가려고 합니다. 이 사람은 한 번에 1칸 또는 2칸씩만 오를 수 있다고 가정합니다. 이때 꼭대기까지 도달할 수 있는 모든 방법의 수를 구하는 것이 이 문제의 목표입니다.

즉, 계단의 개수를 나타내는 숫자 n을 입력받아, 계단을 오를 수 있는 경우의 수를 계산하여 반환하는 JavaScript 함수를 작성해야 합니다.

접근 방식

이 문제는 잘 알려진 피보나치 수열과 밀접한 관련이 있습니다. n번째 계단에 도달하는 방법은 다음 두 가지 경우의 합과 같습니다.

• (n-1)번째 계단에서 1칸 오르는 경우
• (n-2)번째 계단에서 2칸 오르는 경우

따라서 f(n) = f(n-1) + f(n-2)라는 점화식이 성립하며, 이는 피보나치 수열과 동일한 패턴입니다. 아래 코드에서는 값 두 개만 저장하는 배열을 사용해 반복문으로 해결하기 때문에, 이름은 재귀 함수처럼 지어졌지만 실제로는 시간 복잡도 O(n), 공간 복잡도 O(1)로 매우 효율적으로 동작합니다.

예제 코드

다음은 위 로직을 구현한 코드입니다.

const recursiveStaircase = (num = 10) => {
   if (num <= 0) {
      return 0;
   }
   const steps = [1, 2];
   if (num <= 2) {
      return steps[num - 1];
   }
   for (let currentStep = 3; currentStep <= num; currentStep += 1) {
      [steps[0], steps[1]] = [steps[1], steps[0] + steps[1]];
   }
   return steps[1];
};
console.log(recursiveStaircase());
console.log(recursiveStaircase(4));
console.log(recursiveStaircase(13));

실행 결과

콘솔에 출력되는 결과는 다음과 같습니다.

89
5
377

결과 해석

계단이 10개일 때는 89가지, 4개일 때는 5가지, 13개일 때는 377가지의 방법으로 꼭대기에 도달할 수 있습니다. 예를 들어 계단이 4개라면 (1,1,1,1), (1,1,2), (1,2,1), (2,1,1), (2,2)의 총 5가지 조합이 가능하다는 뜻입니다.