70. Climbing Stairs

이 글은 Obsidian에서 마이그레이션되었으며, 그 과정에서 AI의 도움을 받았습니다. 오류나 누락된 내용이 있다면 댓글로 알려주세요!

문제

Climbing Stairs - LeetCode

계단을 한번에 1칸이나 2칸 올라갈 수 있을 때, n 칸까지 올라갈 수 있는 방법의 개수를 구하는 문제.

풀이 1

아이디어

Dynamic programming. 현재 계단에 도달하기 위해서는 1칸 전 계단에서 1칸 올라오거나 2칸 전 계단에서 2칸 올라와야 한다.

코드

function climbStairs(n: number): number {
    const memo = new Array < number > (n + 1).fill(0);
    memo[1] = 1;
    memo[2] = 2;

    for (let currStep = 3; currStep <= n; currStep++) {
        memo[currStep] = memo[currStep - 1] + memo[currStep - 2];
    }

    return memo[n];
}

시간 / 공간 복잡도

• 시간 복잡도: 계단의 개수(n)만큼 반복문을 돌므로 O(n)
• 공간 복잡도: memo 배열을 n + 1 크기로 생성하므로 O(n)