Ch.10 다이나믹 프로그래밍
1D DP — Climbing Stairs, House Robber
계단 오르기가 피보나치?
계단을 1칸 또는 2칸씩 오를 수 있을 때, n번째 계단까지 가는 방법의 수는? 이 단순한 문제가 면접 단골 1D DP 문제입니다.
점화식을 어떻게 세우고, dp 배열을 어떻게 채울까?
dp[i] = dp[i-1] + dp[i-2] — 한 줄의 점화식이 문제를 풀어줍니다.
핵심 개념
점화식
dp[i]를 이전 값들로 표현하는 관계식
1D DP
1차원 배열 하나로 해결하는 DP 문제
핵심 내용
Climbing Stairs (LeetCode #70) n계단을 1칸 또는 2칸씩 오르는 방법의 수
점화식 도출: i번째 계단에 도달하려면: • (i-1)번째에서 1칸 올라오거나 • (i-2)번째에서 2칸 올라오거나 → dp[i] = dp[i-1] + dp[i-2] 기저 사례: dp[0] = 1, dp[1] = 1
이건 피보나치 수열과 완전히 같은 구조입니다!
세 가지 버전으로 구현해봅시다
# 버전 1: Bottom-Up (dp 배열)
def climbStairs(n: int) -> int:
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1], dp[2] = 1, 2
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]# 버전 2: 공간 최적화 O(1)
def climbStairs(n: int) -> int:
if n <= 2:
return n
prev2, prev1 = 1, 2
for i in range(3, n + 1):
curr = prev1 + prev2
prev2 = prev1
prev1 = curr
return prev1# 버전 3: Top-Down (lru_cache)
from functools import lru_cache
def climbStairs(n: int) -> int:
@lru_cache(maxsize=None)
def dp(i):
if i <= 2:
return i
return dp(i-1) + dp(i-2)
return dp(n)세 버전 모두 시간 O(n). 공간은 버전 2가 O(1)로 최적
House Robber (LeetCode #198) 인접한 집을 동시에 털 수 없을 때 최대 금액
문제 설명: 일렬로 늘어선 집들, 각 집에 금액이 있음 인접한 두 집을 연속으로 털면 경보 발생 경보 없이 털 수 있는 최대 금액은? 예: [2, 7, 9, 3, 1] → 2 + 9 + 1 = 12
i번째 집에서의 선택: 털거나, 안 털거나
점화식: dp[i] = max( dp[i-1], # i번째 집을 안 턴다 dp[i-2] + nums[i] # i번째 집을 턴다 ) 기저 사례: dp[0] = nums[0] dp[1] = max(nums[0], nums[1])
코드를 구현하고 배열을 추적합니다
def rob(nums: list[int]) -> int:
if not nums:
return 0
if len(nums) == 1:
return nums[0]
dp = [0] * len(nums)
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
return dp[-1]
# nums = [2, 7, 9, 3, 1]
# dp = [2, 7, 11, 11, 12]
# 답: 12 (2 + 9 + 1)# 공간 최적화 버전
def rob(nums: list[int]) -> int:
if not nums:
return 0
prev2, prev1 = 0, 0
for num in nums:
curr = max(prev1, prev2 + num)
prev2 = prev1
prev1 = curr
return prev1선택/비선택 패턴은 1D DP의 핵심 패턴입니다. 많은 면접 문제가 이 구조를 공유합니다
House Robber에서 nums = [1, 2, 3, 1]일 때 최대 금액은?
Climbing Stairs의 점화식은 피보나치와 동일한 구조다
1D DP 기본 정복!
핵심 용어
점화식
dp[i]를 이전 값들로 표현하는 관계식
1D DP
1차원 배열 하나로 해결하는 DP 패턴
정리 노트
1D DP — Climbing Stairs, House Robber
Climbing Stairs
- 점화식
- dp[i] = dp[i-1] + dp[i-2] (피보나치)
- 복잡도
- 시간 O(n), 공간 O(1) (최적화 시)
House Robber
- 점화식
- dp[i] = max(dp[i-1], dp[i-2] + nums[i])
- 패턴
- 선택/비선택 — 많은 DP 문제의 기본 구조
1D DP 문제를 만나면 '이전 1~2개 값에 의존하는 점화식'을 먼저 찾으세요!
시각 자료
핵심 정리
- 1Climbing Stairs = 피보나치 변형
- 2House Robber = 선택/비선택 패턴
- 3공간 최적화: dp 배열 → 변수 2개
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작