[정글 베이직27]동적 프로그래밍 - 계단 오르기 (상향식 / Bottom-up)

작은 문제부터 차례대로 쌓아 올리며 n번째 계단까지 가는 방법의 수를 구하는 Bottom-up DP 대표 문제

문제 한눈에 보기

문제	한 번에 1칸 또는 2칸씩 올라갈 때, n번째 계단까지 가는 방법의 수 구하기
부분 문제	dp[i] = i번째 계단까지 오르는 방법 수
점화식	dp[i] = dp[i-1] + dp[i-2]
예시	n = 4 → 5

핵심 1

현재 계단에 도착하는 마지막 동작은 1칸 또는 2칸 뿐이다.

핵심 2

그래서 현재 값은 이전 두 값의 합이 되어 피보나치와 비슷한 구조가 된다.

핵심 3

Bottom-up은 3부터 n까지 순서대로 dp를 채워 나가는 방식이다.

왜 점화식이 이렇게 나올까?

i번째 계단에 도착하려면 마지막에 두 가지 방법만 가능하다.

• i-1번째 계단에서 1칸 올라오기
• i-2번째 계단에서 2칸 올라오기

따라서 dp[i] = dp[i-1] + dp[i-2] 가 된다.

최종 코드

def climb_stairs(n):
    if n == 1:
        return 1
    if n == 2:
        return 2

    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]

한 줄씩 설명

줄	코드	설명
1	def climb_stairs(n):	n번째 계단까지 가는 방법 수를 구하는 함수다.
2-5	if n == 1: return 1 if n == 2: return 2	특별한 경우를 먼저 처리한다. 1칸은 1가지, 2칸은 2가지다.
7	dp = [0] * (n + 1)	dp[1]부터 dp[n]까지 사용하기 위해 미리 칸을 만든다. [] * (n+1) 은 빈 리스트라서 안 된다.
8-9	dp[1] = 1 dp[2] = 2	초기값 설정이다. 이 두 값이 있어야 dp[3]부터 계산할 수 있다.
11	for i in range(3, n + 1):	작은 문제부터 차례로 계산한다. 처음 계산이 필요한 값은 3부터다.
12	dp[i] = dp[i-1] + dp[i-2]	현재 계단의 방법 수를 이전 두 계단 방법 수의 합으로 계산한다.
14	return dp[n]	최종 정답 반환.

계산 흐름 예시

dp[1] = 1 dp[2] = 2 dp[3] = dp[2] + dp[1] = 3 dp[4] = dp[3] + dp[2] = 5

그래서 n=4일 때 답은 5가 된다.

dp[0]은 왜 안 쓰나?

리스트 인덱스는 0부터 시작하지만, 여기서는 dp[i]를 i번째 계단과 맞춰 쓰는 방식이다. 그래서 dp[0]은 자리만 있고 실제 계산에는 쓰지 않는다.

시간복잡도

1부터 n까지 한 번씩 계산하므로 O(n)

공간복잡도

dp 배열을 사용하므로 O(n)

한 문장 정리

현재 계단의 답은 이전 두 계단의 답의 합이라는 점만 잡으면, Bottom-up DP로 매우 깔끔하게 풀 수 있다.