"제일 친근한 DP 는 상태가 숫자 하나야 — 보통 인덱스. dp[i] 는 '위치 i 까지 전부 고려한 최선 답' 이고, 앞 항목 몇 개로 지어져. 그 모양이 보이면, 문제 가문 전체가 일상이 돼."
1차원 상태
1D DP 는 부분 문제가 숫자 하나로 식별되는 거 — 보통 배열 인덱스, 또는 남은 금액. dp[i] 를 '첫 i 원소 고려' (또는 '금액 i 만들기') 부분 문제의 답으로 정의하고, 앞 dp 값 몇 개로 표현해. 그러면 전체 해법이 배열을 왼쪽에서 오른쪽으로 채우는 단일 루프야. 계단 오르기, 동전 교환, 도둑이 다 1D DP — 상태가 그냥 '얼마나 왔어?' 야.
도둑 (House Robber): 깔끔한 점화식
정석: 값 있는 집 한 줄; 인접한 두 집 못 털어; 전리품 최대화. 통찰은 집별 선택 — 집 i 에 대해, 그걸 건너뛰거나 (그럼 최선이 dp[i-1]) 그걸 털거나 (그럼 최선이 nums[i] 더하기 dp[i-2], i-1 은 그럼 건너뛰어야 하니). 그래서 dp[i] = max(dp[i-1], dp[i-2] + nums[i]). 그 한 줄이 문제 전체를 잡고, 앞 두 항목에만 의존하니, 변수 둘로 공간-최적화돼. 대부분 1D DP 가 정확히 이 맛이야: dp[i] 를 앞 칸 몇 개에 관련짓는 짧은 점화식.
1D DP 는 상태를 숫자 하나 (보통 배열 위치) 로 인덱싱해. dp[i] 를 i 까지 최선 답으로 정의, 앞 항목 몇 개에 대한 짧은 점화식으로 — 예: 도둑의 dp[i] = max(dp[i-1], dp[i-2] + nums[i]). 왼쪽에서 오른쪽 채움; 변수 몇 개로 공간-최적화.
Kadane 알고리즘: 보석
가장 우아한 1D DP 는 최대-합 연속 부분배열의 Kadane 알고리즘이야. 상태: best_ending_here = 현재 위치에서 끝나는 가장 큰 부분배열 합. 각 원소에서 선택 하나 — 이전 run 을 연장 (best_ending_here + x) 하거나 여기서 새로 시작 (x), 더 큰 쪽 — 하고 본 최선을 추적해. O(n), O(1) 공간, 단일 패스. "여기서 끝나는 최선" 이 외울 가치 있는 사고 패턴이야: 많은 배열 DP 가 상태를 '정확히 인덱스 i 에서 끝나는 최선 해법' 으로 정의하고, 모든 i 에 대해 최대를 취해 깨져.
피파의 고백
최대 부분배열이 날 막았어 — 모든 O(n²) 부분배열을 확인하고 있었어. 아빠가 구절 하나 줬어: "여기서 끝나는 최선." 모든 부분배열 대신, 현재 자리에서 끝나는 최선만 추적하고, 연장하거나 재시작해. 갑자기 단일 패스, O(n). 그 '여기서 끝나는 최선' 재구성이 다른 어떤 단일 아이디어보다 많은 배열 DP 를 풀어줬어 — '모든 부분배열 고려' 를 '원소당 지역 선택 하나' 로 바꿔.
Code
도둑과 Kadane 알고리즘·python
# 도둑: 최대 전리품, 인접 두 집 안 됨. dp[i] 가 dp[i-1], dp[i-2] 로.
def rob(nums):
prev2, prev1 = 0, 0 # dp[i-2], dp[i-1] (공간-최적화)
for x in nums:
# 집 건너뛰기 (prev1) 또는 털기 (x + prev2)
prev2, prev1 = prev1, max(prev1, prev2 + x)
return prev1
print(rob([2, 7, 9, 3, 1])) # 12 (집 2, 9, 1 털기)
# Kadane: 최대-합 연속 부분배열, O(n), '여기서 끝나는 최선'.
def max_subarray(nums):
best_ending_here = best_overall = nums[0]
for x in nums[1:]:
# 이전 run 연장, 또는 x 에서 새로 시작 — 더 큰 쪽
best_ending_here = max(x, best_ending_here + x)
best_overall = max(best_overall, best_ending_here)
return best_overall
print(max_subarray([-2, 1, -3, 4, -1, 2, 1, -5, 4])) # 6 (run [4,-1,2,1])
# 무차별은 모든 O(n^2) 부분배열 확인; Kadane 은 원소당 선택 하나 -> O(n).
도둑을 [2, 7, 9, 3, 1] 에 손으로 추적해, 각 단계 dp[i] = max(dp[i-1], dp[i-2] + nums[i]) 를 계산해. 최종 답이 뭐고 어느 집을 털어? 그다음 점화식이 왜 앞 *두* dp 값만 필요하고, 그게 어떻게 O(1) 공간을 가능케 하는지 설명해.
Hint
dp: 2, 7, max(7,2+9)=11, max(11,7+3)=11, max(11,11+1)=12 → 답 12 (값 2, 9, 1 집). dp[i-1] 이랑 dp[i-2] 만 필요한 이유는 i 털면 i-1 금지지만 i-2 허용; 더 오래된 건 참조 안 하니, 롤링 변수 둘이면 충분 → O(1) 공간.
Progress
Progress is local-only — sign in to sync across devices.