자바스크립트 코딩테스트 강좌, 계단 수 구하기

안녕하세요, 오늘은 자바스크립트 코딩테스트 준비에 유용한 알고리즘 문제 중 하나인 “계단 수 구하기”를 풀어보겠습니다. 이 문제는 동적 프로그래밍(Dynamic Programming)과 조합적으로 접근할 수 있는 흥미로운 문제입니다. 이 글에서는 문제 설명, 풀이 과정, 그리고 최적화 방안을 포함하여 자세히 설명하겠습니다.

문제 설명

계단 수는 n 자리 수 중, 인접한 두 자리의 차이가 1인 수를 의미합니다. 예를 들어, 123, 321과 같이 인접한 자리의 숫자 차이가 1일 경우 이 수는 계단 수입니다. 주어진 n에 대해 n 자리 계단 수를 구하는 프로그램을 작성하세요.

입력

정수 n (1 ≤ n ≤ 1000)

출력

n 자리의 계단 수의 개수를 1,000,000,000으로 나눈 나머지를 출력합니다.

문제 풀이 전략

이 문제를 해결하기 위해서는 동적 프로그래밍 접근 방식을 사용할 수 있습니다. 계단 수는 다음과 같이 상태를 정의하여 해결할 수 있습니다:

dp[i][j]: i자리 계단 수 중, j로 끝나는 수의 개수

계단 수를 구성하는 규칙을 다음과 같이 세울 수 있습니다:

j가 0일 때(0으로 시작하는 수 없음): dp[i][0] = dp[i-1][1]
j가 9일 때: dp[i][9] = dp[i-1][8]
그 외의 경우: dp[i][j] = dp[i-1][j-1] + dp[i-1][j+1]

동적 프로그래밍 테이블 초기화

이제 dp 테이블을 초기화해보겠습니다. 1자리 수의 경우, 숫자는 0부터 9까지 가능하므로 dp[1][0] 부터 dp[1][9]까지 각각 1로 초기화합니다.

풀이 코드


function countStairNumbers(n) {
    const MOD = 1000000000;
    const dp = Array.from({ length: n + 1 }, () => Array(10).fill(0));

    // 1자리 수 초기화
    for (let j = 0; j < 10; j++) {
        dp[1][j] = 1;
    }

    // dp 테이블 채우기
    for (let i = 2; i <= n; i++) {
        for (let j = 0; j < 10; j++) {
            if (j > 0) dp[i][j] += dp[i - 1][j - 1]; // j-1에서 이동
            if (j < 9) dp[i][j] += dp[i - 1][j + 1]; // j+1에서 이동
            dp[i][j] %= MOD; // modulo 연산
        }
    }

    // n자리 모든 계단 수의 합
    let result = 0;
    for (let j = 0; j < 10; j++) {
        result += dp[n][j];
    }

    return result % MOD;
}

// 함수 호출 예시
console.log(countStairNumbers(3)); // 24

시간 복잡도

위 코드의 시간 복잡도는 O(n)이며, 공간 복잡도는 O(n)입니다. 각 자리 수의 조합을 통해 결과를 도출하기 때문에 n이 커질수록 시간과 공간을 효율적으로 사용할 수 있습니다.

최적화 방안

현재 구현된 코드에서 메모리 사용량을 줄이기 위해 dp 배열을 2차원에서 1차원으로 변경할 수 있습니다. 각 i에 대해 이전의 dp 상태만 필요하기 때문에, 이를 이용해 최적화할 수 있습니다.


function countStairNumbersOptimized(n) {
    const MOD = 1000000000;
    const dp = Array(10).fill(0);
    const temp = Array(10).fill(0);

    // 1자리 수 초기화
    for (let j = 0; j < 10; j++) {
        dp[j] = 1;
    }

    for (let i = 2; i <= n; i++) {
        for (let j = 0; j < 10; j++) {
            temp[j] = 0;
            if (j > 0) temp[j] += dp[j - 1]; // j-1에서 이동
            if (j < 9) temp[j] += dp[j + 1]; // j+1에서 이동
            temp[j] %= MOD; // modulo 연산
        }
        for (let j = 0; j < 10; j++) {
            dp[j] = temp[j]; // 다음 단계로 업데이트
        }
    }

    // n자리 모든 계단 수의 합
    let result = 0;
    for (let j = 0; j < 10; j++) {
        result += dp[j];
    }

    return result % MOD;
}

마치며

이번 글에서는 “계단 수 구하기” 문제를 통해 자바스크립트로 동적 프로그래밍을 활용하여 문제를 해결하는 방법을 배웠습니다. 초기화, dp 테이블 구성, 그리고 최적화 과정을 자세히 설명하였으며, 다양한 테크닉을 사용하여 알고리즘의 효율성을 높일 수 있는 방법도 소개하였습니다. 알고리즘 문제를 풀 때는 항상 다양한 접근 방식을 고민하고 최적화할 방안을 모색해 보세요. 감사합니다!