JavaScript 백트래킹으로 계단 오르기 문제 해결하기 – 모든 점프 순서 구현 방법

계단 오르기 문제는 알고리즘 학습에서 가장 널리 알려진 재귀·백트래킹 연습 문제 중 하나입니다. 이 글에서는 JavaScript를 이용해 계단을 오르는 모든 가능한 점프 순서를 백트래킹(backtracking)으로 구현하는 방법과, 메모이제이션(memoization)을 활용해 총 경우의 수를 구하는 방법까지 함께 살펴보겠습니다.

문제 정의

n개의 계단이 있는 계단을 오른다고 가정해 봅시다. 운동 효과를 위해 한 번에 여러 칸씩 뛰어 오르려고 합니다.

한 번의 점프로 최대 k칸을 오를 수 있으며, 이때 k는 계단 수와 무관하게 항상 1 또는 2입니다.

우리가 구해야 할 것은 계단 꼭대기까지 오르기 위해 취할 수 있는 모든 가능한 점프 순서이며, 결과는 정렬된 상태로 반환해야 합니다.

예시

예를 들어 n = 4, k = 2인 경우를 보겠습니다.

climbingStaircase(4, 2)

이때 기대되는 출력은 다음과 같습니다.

[[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2]]

각 배열은 계단을 오르는 하나의 점프 시퀀스를 의미합니다. 예를 들어 [1, 2, 1]은 한 칸, 두 칸, 한 칸씩 뛰어 올라 4계단을 모두 오르는 경로입니다.

방법 1 – 백트래킹으로 모든 점프 순서 구하기

백트래킹은 가능한 선택지를 하나씩 시도해 보고, 더 이상 진행할 수 없거나 목표에 도달하면 이전 상태로 되돌아가 다른 선택지를 탐색하는 기법입니다. 계단 문제에서는 각 단계에서 1칸부터 k칸까지의 점프를 순서대로 시도하면 됩니다.

const climbingStaircase = (n, k) => {
  const result = [];
  const path = [];

  const backtrack = (remaining) => {
    // 남은 계단이 없으면 완성된 경로를 결과에 저장
    if (remaining === 0) {
      result.push([...path]);
      return;
    }
    // 1칸부터 남은 계단 또는 k칸 중 작은 값까지 시도
    for (let step = 1; step <= Math.min(k, remaining); step++) {
      path.push(step);          // 선택
      backtrack(remaining - step); // 탐색
      path.pop();               // 선택 취소 (백트래킹)
    }
  };

  backtrack(n);
  return result;
};

console.log(climbingStaircase(4, 2));
// [[1, 1, 1, 1], [1, 1, 2], [1, 2, 1], [2, 1, 1], [2, 2]]

작동 원리를 정리하면 다음과 같습니다.

1. 현재 남은 계단 수(remaining)가 0이면 하나의 유효한 경로가 완성된 것이므로 결과 배열에 저장합니다.
2. 그렇지 않으면 1부터 min(k, remaining)까지의 각 점프 폭을 차례대로 시도합니다.
3. 점프를 선택한 뒤 재귀 호출로 나머지 계단을 탐색하고, 탐색이 끝나면 pop()으로 선택을 되돌려 다음 후보를 시도합니다.

점프 폭을 오름차순(1 → k)으로 시도하기 때문에 별도의 정렬 없이도 결과가 자연스럽게 사전순으로 생성됩니다.

방법 2 – 메모이제이션으로 총 경우의 수 구하기

모든 경로가 아니라 오를 수 있는 방법의 개수만 필요하다면, 점화식을 이용한 동적 계획법(DP)이 훨씬 효율적입니다. f(n) = f(n-1) + f(n-2)라는 관계를 재귀로 구현하되, 이미 계산한 값을 Map에 캐싱하여 중복 연산을 제거합니다.

const n = 4;

const climbStairs = (n) => {
  if (n == 0) return 0;
  let memory = new Map();
  let recur = (left) => {
    if (memory.has(left)) return memory.get(left);
    if (left <= 0) return 0;
    if (left == 1) return 1;
    if (left == 2) return 2;
    memory.set(left, recur(left - 2) + recur(left - 1));
    return memory.get(left);
  };
  return recur(n);
};

console.log(climbStairs(n));

출력 결과

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

5

n = 4일 때 총 5가지 방법으로 계단을 오를 수 있으며, 앞서 백트래킹으로 구한 5개의 경로와 정확히 일치합니다.

정리

모든 경로 자체가 필요하다면 백트래킹으로 시간 복잡도 O(2^n) 수준의 전수 탐색을 수행해야 하고, 경로의 개수만 필요하다면 메모이제이션을 활용한 DP로 O(n) 시간에 답을 구할 수 있습니다. 두 접근 방식을 함께 익혀두면 유사한 구조의 조합 탐색 문제(코인 교환, 문자열 분할 등)를 해결할 때 큰 도움이 됩니다.