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

오늘의 문제 선정 이유

 

AI, React, 대규모 오픈소스처럼 복잡한 기술도 결국 작은 상태를 쌓아 해결하므로, 오늘은 DP의 가장 기본인 계단 오르기를 선택했습니다.

문제 설명

물류 자동화 서비스를 만드는 팀에서 창고 로봇의 이동 경로를 단순화해 분석하려고 합니다.

로봇은 바닥에서 시작해 정확히 n칸 위의 플랫폼까지 올라가야 합니다.
한 번에 할 수 있는 이동은 다음 두 가지뿐입니다.

• 1칸 올라가기

 

• 2칸 올라가기

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

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

• 1 + 1 + 1

 

• 1 + 2

 

• 2 + 1

입출력 예시

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

[text]입력: n = 5
출력: 8
설명: 마지막 이동이 1칸인 경우와 2칸인 경우를 나누어 세면 총 8가지입니다.

[text]입력: n = 1
출력: 1
설명: 1칸 오르는 방법 하나만 가능합니다.

제약 조건

• 1 <= n <= 45

 

• 시간 제한: 1초

 

• 정답은 32비트 정수 범위 안에 들어옵니다.

풀이 접근법

핵심 아이디어

이 문제는 매번 이전 결과를 다시 쓰는 구조라서 DP로 푸는 것이 가장 자연스럽습니다.
n칸에 도달하는 방법은 n-1칸에서 1칸 올라오거나, n-2칸에서 2칸 올라오는 두 경우뿐입니다.

단계별 풀이 과정

1. dp[i]를 i칸에 도달하는 방법의 수라고 정의합니다.
2. dp[1] = 1, dp[2] = 2를 초기값으로 둡니다.
3. i >= 3부터는 dp[i] = dp[i-1] + dp[i-2]로 계산합니다.
4. 최종적으로 dp[n]을 반환합니다.

코드 풀이

Python

 

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

    # dp[i]: i칸에 도달하는 방법의 수
    dp = [0] * (n + 1)
    dp[1] = 1
    dp[2] = 2

    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    return dp[n]


# 예시 실행
if __name__ == "__main__":
    print(solution(3))  # 3
    print(solution(5))  # 8

JavaScript

 

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

  // dp[i]: i칸에 도달하는 방법의 수
  const dp = new Array(n + 1).fill(0);
  dp[1] = 1;
  dp[2] = 2;

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

  return dp[n];
}

// 예시 실행
console.log(solution(3)); // 3
console.log(solution(5)); // 8

시간·공간 복잡도

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

 

• 공간 복잡도: O(n) — dp 배열에 1부터 n까지의 값을 저장합니다.

틀리기 쉬운 포인트

• dp[0]부터 억지로 시작하다가 초기값을 꼬이게 만드는 경우가 많습니다. 이 문제는 dp[1], dp[2]를 먼저 두는 편이 더 안전합니다.

 

• n = 1, n = 2를 별도로 처리하지 않으면 인덱스 오류가 날 수 있습니다.

 

• 경우의 수 문제에서 순서를 구분하는지 놓치기 쉽습니다. 1+2와 2+1은 서로 다른 방법입니다.

유사 문제 패턴

• fibonacci 수열 문제: 현재 값이 이전 두 값의 합으로 결정되는 대표 패턴입니다.

 

• house robber: 현재 집을 털지 말지 선택하며 이전 상태를 활용하는 DP 문제입니다.

 

• min cost climbing stairs: 계단을 오르되 경우의 수가 아니라 최소 비용을 구하는 응용 문제입니다.