정석 1D DP: 상태 한 차원

"가장 만만한 DP는 상태가 숫자 하나인 놈이야. 보통은 인덱스지. dp[i]는 '위치 i까지 고려한 최선의 답'이고, 앞 항목 몇 개로 지어져. 이 모양이 눈에 들어오기 시작하면, 같은 꼴의 문제 한 무더기가 통째로 일상이 돼."

1차원 상태

1D DP는 부분 문제가 숫자 하나로 식별되는 DP야. 보통은 배열 인덱스거나 남은 금액이지. dp[i]를 '첫 i개 원소를 고려한 답'이나 '금액 i를 만드는 답'으로 정의하고 앞선 dp 값 몇 개로 표현하면, 해법 전체가 배열을 왼쪽에서 오른쪽으로 채우는 루프 하나가 돼. 계단 오르기, 동전 교환, 도둑 문제가 다 1D DP야. 상태가 그저 '어디까지 왔어?' 하나거든.

도둑(House Robber): 깔끔한 점화식

정석 문제야. 값어치가 적힌 집들이 한 줄로 서 있고, 인접한 두 집은 못 털어. 전리품을 최대로 만들어 봐. 통찰은 집마다 하나씩 내리는 선택이야. 집 i를 건너뛰면 최선은 dp[i-1]이고, 털면 i-1은 포기해야 하니 최선은 nums[i] 더하기 dp[i-2]야. 그래서 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 알고리즘: 보석

Kadane 알고리즘은 비어 있지 않은 최대 합 연속 부분배열을 O(n) 시간, O(1) 공간에 찾아내. 그러니 입력도 비어 있지 않다고 계약해 두거나, 빈 입력의 동작을 따로 계약해야 해. 상태 best_ending_here는 현재 위치에서 끝나는 최대 합이고, 매 단계에서 이전 구간을 연장할지 여기서 새로 시작할지를 골라.

피파의 고백

최대 부분배열 문제에 제대로 막혔었어. 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).

Exercise

도둑 문제를 [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) 공간.

1차원 상태

도둑(House Robber): 깔끔한 점화식

Kadane 알고리즘: 보석

피파의 고백

Code

External links

Exercise

Progress

댓글 0