[코딩 테스트] 2026-04-27 — 동적 계획법(DP)

오늘의 문제 선정 이유

 

AI, 로드맵, 인터뷰 준비가 함께 주목받는 날이라 가장 자주 나오는 DP 입문 유형인 계단 오르기를 고르는 것이 실전적이다.

문제 설명

당신은 총 n칸의 계단을 올라가야 합니다.

한 번에 할 수 있는 행동은 두 가지입니다.

• 1칸 오르기

 

• 2칸 오르기

정확히 n칸에 도달하는 서로 다른 방법의 수를 구하세요.

예를 들어 n = 3이면 가능한 방법은 다음 3가지입니다.

• 1 + 1 + 1

 

• 1 + 2

 

• 2 + 1

정답은 3입니다.

함수는 정수 n을 입력받아 경우의 수를 반환해야 합니다.

입출력 예시

[text]입력: n = 2
출력: 2
설명: 가능한 방법은 [1+1], [2] 두 가지이다.

[text]입력: n = 4
출력: 5
설명: 가능한 방법은 [1+1+1+1], [1+1+2], [1+2+1], [2+1+1], [2+2] 이다.

[text]입력: n = 5
출력: 8
설명: 마지막 한 번의 이동이 1칸인지 2칸인지로 나누면 총 8가지가 된다.

제약 조건

• 1 <= n <= 45

 

• 시간 제한: 1초

 

• 추가 라이브러리 없이 구현 가능

 

• 재귀만으로 풀면 중복 계산이 많아질 수 있음

풀이 접근법

핵심 아이디어

이 문제는 n번째 계단에 도달하는 방법 수를 이전 상태로 나눌 수 있어서 DP로 푸는 것이 가장 자연스럽습니다.
n칸에 오기 직전은 n-1칸 또는 n-2칸뿐이므로, dp[n] = dp[n-1] + dp[n-2]가 됩니다.
이 구조가 피보나치 수열과 같아서, 반복문으로 빠르고 안정적으로 구현할 수 있습니다.

단계별 풀이 과정

1. 1칸일 때 방법 수는 1, 2칸일 때 방법 수는 2로 둡니다.
2. 3칸부터는 i-1칸에서 1칸 오르는 경우와 i-2칸에서 2칸 오르는 경우를 더합니다.
3. 마지막으로 n칸의 값을 반환합니다.

코드 풀이

Python

 

[python]def climb_stairs(n: int) -> int:
    # n이 1 또는 2면 바로 답을 반환
    if n == 1:
        return 1
    if n == 2:
        return 2

    # prev2 = dp[i-2], prev1 = dp[i-1]
    prev2 = 1
    prev1 = 2

    # 3칸부터 n칸까지 순서대로 계산
    for _ in range(3, n + 1):
        current = prev1 + prev2
        prev2 = prev1
        prev1 = current

    return prev1


# 예시 실행
if __name__ == "__main__":
    print(climb_stairs(2))  # 2
    print(climb_stairs(4))  # 5
    print(climb_stairs(5))  # 8

JavaScript

 

[javascript]function climbStairs(n) {
  // n이 1 또는 2면 바로 답을 반환
  if (n === 1) return 1;
  if (n === 2) return 2;

  // prev2 = dp[i-2], prev1 = dp[i-1]
  let prev2 = 1;
  let prev1 = 2;

  // 3칸부터 n칸까지 순서대로 계산
  for (let i = 3; i <= n; i++) {
    const current = prev1 + prev2;
    prev2 = prev1;
    prev1 = current;
  }

  return prev1;
}

// 예시 실행
console.log(climbStairs(2)); // 2
console.log(climbStairs(4)); // 5
console.log(climbStairs(5)); // 8

시간·공간 복잡도

• 시간 복잡도: O(n) — 3부터 n까지 한 번만 순회한다.

 

• 공간 복잡도: O(1) — 이전 두 상태만 저장한다.

틀리기 쉬운 포인트

• dp[n] = dp[n-1] + dp[n-2]는 맞지만, 시작값 dp[1] = 1, dp[2] = 2를 잘못 두면 전체 답이 틀어진다.

 

• 재귀로만 구현하면 같은 값을 여러 번 계산해서 비효율적이다.

 

• n = 1 같은 작은 입력을 따로 처리하지 않으면 index 에러나 잘못된 초기값 문제가 생길 수 있다.

유사 문제 패턴

• House Robber: 현재 집을 털지 말지 결정하면서 이전 상태를 누적하는 DP 문제.

 

• Min Cost Climbing Stairs: 계단을 오르되 경우의 수가 아니라 최소 비용을 구하는 변형 문제.

 

• Decode Ways: 문자열을 앞에서부터 해석하면서 이전 두 상태를 이용하는 DP 문제.