LeetCode DP 문제, House Robber Swift 알고리즘 풀이

문제 링크: LeetCode 198. House Robber
유형: Dynamic Programming (DP)

 

---

문제 요약

도둑이 일렬로 늘어선 집들을 털려고 합니다.
단, 인접한 두 집을 동시에 털 수는 없습니다.

각 집마다 돈의 양이 담긴 배열 nums가 주어졌을 때,
도둑이 털 수 있는 최대 금액을 반환해야합니다!

---

🔍 예시

Input: nums = [2,7,9,3,1]
Output: 12
// 2 + 9 + 1 = 12

---

💡 접근 방법

이 문제는 전형적인 Dynamic Programming(DP) 문제입니다.
핵심은 현재 집을 털지, 건너뛸지 선택하는 것인데요. 이를 점화식으로 정리해서 해결할 수 있습니다.

---

점화식 정의

dp[i] = 0번째부터 i번째 집까지 털었을 때 얻을 수 있는 최대 금액입니다.

이때 점화식에 활용되는 2가지 케이스는 아래와 같아요.

1. i번째 집을 털지 않는다.
   → 이전까지의 최대 금액은 그대로 유지된다 → dp[i-1]
2. i번째 집을 턴다.
   → i-1번째는 털 수 없으므로, dp[i-2] + nums[i]

따라서 점화식은 다음과 같습니다.

dp[i] = max(dp[i-1], dp[i-2] + nums[i])

---

구현 코드 (Swift)

class Solution {
    /// DP 를 활용해서 문제를 해결합니다. 
    /// dp[i] = 0...i 까지의 집에서 얻을 수 있는 최댓값
    func rob(_ nums: [Int]) -> Int {
        // 1) 집이 단 한개면 그 집의 돈만 털면 됩니다.
        if nums.count == 1 {
            return nums[0]
        }

        // 2) 집이 두개면 둘 중 돈 더 많은 곳을 털면 됩니다.
        if nums.count == 2 {
            return nums.max()!
        }

        // 3) dp는 0~i번째 집까지 털었을대 얻을 수 있는 최대 금액이 들어갑니다.
        var dp = [Int](repeating: 0, count: nums.count)

        // 3-1) 0, 1번째 케이스 최댓값을 미리 넣고,
        dp[0] = nums[0]
        dp[1] = nums[...1].max()!

        // 3-2) 점화식 적용
        for i in 2..<nums.count {
            dp[i] = max(dp[i-1], nums[i] + dp[i-2])
        }

        return dp.last!
    }
}

---

예시 시뮬레이션

입력:

nums = [2, 7, 9, 3, 1]

i	nums[i]	dp[i] 계산식	dp[i] 값
0	2	-	2
1	7	max(2, 7)	7
2	9	max(7, 9+2=11)	11
3	3	max(11, 3+7=10)	11
4	1	max(11, 1+11=12)	12

최종 결과: 12

---

시간 및 공간 복잡도

구분	복잡도	설명
시간 복잡도	O(n)	모든 집을 한 번씩 탐색
공간 복잡도	O(n)	DP 배열 사용 (공간 최적화 시 O(1) 가능)

---

+ 공간 최적화 버전

dp[i]는 dp[i-1]과 dp[i-2]만 참조하므로,
배열 대신 두 변수로 관리할 수도 있습니다. 이렇게 되면 공간복잡도를 O(1) 상수복잡도로 처리할 수 있습니다.

func rob(_ nums: [Int]) -> Int {
    if nums.count == 1 { return nums[0] }

    var prev2 = nums[0]
    var prev1 = max(nums[0], nums[1])

    for i in 2..<nums.count {
        let current = max(prev1, prev2 + nums[i])
        prev2 = prev1
        prev1 = current
    }

    return prev1
}

---

✨ 마무리

이 문제는 DP의 핵심 개념을 명확하게 연습하기 좋은 대표 문제였습니다.
“현재 최적의 선택은 이전 두 상태의 최적해로부터 결정된다”는 원리를 잘 활용해야했습니다.

DP문제는 평소 풀지 않으면 점화식이 생각나더라도 풀기 어려운 경우가 있기때문에 꾸준한 연습이 필요합니다.
지금까지 릿코드의 House Robber DP swift 언어 기반 알고리즘 풀이였습니다. 감사합니다!