어려움
Climbing Stairs
코드 라인과 단계 ID를 동기화하고, 변수/포인터/배열·행렬·그래프 엔티티의 상태 스냅샷을 단계마다 갱신한다.
입력
1함수 계단오르기(n):2 방법[0] = 1, 방법[1] = 13 반복 k = 2 … n:4 방법[k] = 방법[k-1] + 방법[k-2]5 반환 방법[n]
변수
- 방법[0]
- 1
- 방법[1]
- 1
1 / 30칸·1칸에 오는 방법은 각각 1가지입니다.
n칸에 오는 방법 = (한 칸 전) + (두 칸 전) — 바닥부터 쌓아 올리는 피보나치형 DP.
왜 헷갈리는가
재귀로 풀면 같은 계단을 지수적으로 다시 계산한다(O(2^n)). '이미 구한 값을 표에 적어 두는' DP로 O(n)이 되는데, 사실 앞의 두 값만 있으면 되므로 변수 두 개로도 충분하다.
핵심 아이디어
마지막 걸음은 1칸 아니면 2칸이다. 그래서 n에 오는 경우의 수는 (n−1에서 온 경우) + (n−2에서 온 경우)로 정확히 갈린다. 겹치는 하위 문제를 한 번만 계산해 표에 남긴다.
복잡도
시간 O(n)·공간 O(n)(표) 또는 O(1)(변수 두 개). 순진한 재귀는 O(2^n).
실무에서 어디에 쓰나
'겹치는 하위 문제 + 최적 부분구조'는 DP의 신호다. 이 문제는 DP 입문의 원형이다.
- 경로/경우의 수: 격자 이동 경로 수, 디코딩 방법 수 등의 기초형
- 메모이제이션: 반복 계산을 표로 접는 사고방식(캐시 설계에 직결)
- 점화식 모델링: 재무·확률의 순차 상태 전이(재귀식) 계산
- 성능: 지수 재귀를 선형으로 접는 전형적 최적화 패턴
흔한 실수
기저(0·1칸)를 잘못 잡기. 표 없이 순진한 재귀로 지수 시간 쓰기.
기억할 것
- 마지막 걸음이 1 또는 2 → 앞의 둘의 합.
- 겹치는 하위 문제 = DP 신호.
- 표 O(n) 또는 변수 O(1).
- DP·메모이제이션 입문의 원형.