DP1D: 198. House Robber

LeetCode/주제별 보충

DP1D: 198. House Robber

hyunkookim 2024. 11. 7. 16:30

문제

198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.

Example 1:

Input: nums = [1,2,3,1]
Output: 4
Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3).
Total amount you can rob = 1 + 3 = 4.

Example 2:

Input: nums = [2,7,9,3,1]
Output: 12
Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1).
Total amount you can rob = 2 + 9 + 1 = 12.

Constraints:

1 <= nums.length <= 100
0 <= nums[i] <= 400

문제 설명

1. 입력

nums: 각 집에 있는 돈의 양을 나타내는 정수 배열.
- 예: nums = [2, 7, 9, 3, 1]에서
  - 집 1에는 2,
  - 집 2에는 7,
  - 집 3에는 9가 있습니다.

2. 규칙

연속된 집은 털 수 없다.
- 두 인접한 집을 털면 경찰이 알림을 받습니다.
- 예: 집 1과 집 2를 동시에 털 수 없습니다.

3. 목표

최대 금액을 얻기 위해 털어야 할 집들을 선택합니다.
단, 위의 규칙을 준수해야 합니다.

예제

예제 1:

plaintext

코드 복사

Input: nums = [1, 2, 3, 1] Output: 4

가능한 선택:
- 집 1과 집 3을 턴다면 1+3=41 + 3 = 4 (최대 금액).
- 집 2와 집 4를 턴다면 2+1=32 + 1 = 3 (최대 금액 아님).

예제 2:

plaintext

코드 복사

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

가능한 선택:
- 집 1, 집 3, 집 5를 털면 2+9+1=122 + 9 + 1 = 12 (최대 금액).
- 집 2와 집 4를 털면 7+3=107 + 3 = 10 (최대 금액 아님).

문제 해결의 핵심 아이디어

이 문제는 **동적 계획법(DP)**으로 해결할 수 있습니다.

1. 문제 분할

각 집에서 가능한 최대 금액은 현재 집을 털거나, 털지 않는 경우 중 최대값으로 결정됩니다.
상태 점화식:
- dp[i] = max⁡(dp[i−1], dp[i−2] + nums[i])
  - dp[i−1]dp[i-1]: 현재 집을 털지 않는 경우.
  - dp[i−2]+nums[i]dp[i-2] + nums[i]: 현재 집을 털고, 두 번째 이전 집의 최대 금액을 더하는 경우.

2. 초기값 설정

dp[0] = nums[0]: 첫 번째 집의 돈이 최대 금액.
dp[1] = max⁡(nums[0], nums[1]): 첫 번째 또는 두 번째 집 중 더 많은 돈.

3. 결과

dp[−1]: 마지막 집까지 고려했을 때의 최대 금액.

제약 조건

nums의 길이:
- 최소 1개에서 최대 100개.
각 집의 돈의 양:
- 0부터 400까지.

위 조건으로 인해 DP를 사용하는 방법이 효율적입니다. O(n)의 시간 복잡도로 문제를 해결할 수 있습니다.

Code

class Solution:
    def rob(self, nums: List[int]) -> int:
        rob1, rob2 = 0, 0
        # [rob1, rob2, n, n+2, ...]
        # rob1: 두 번째 이전 집까지의 최대 금액
        # rob2: 바로 이전 집까지의 최대 금액
        # 초기 상태: rob1 = 0, rob2 = 0
        
        # 입력 예제: nums = [2, 7, 9, 3, 1]
        # 각 집의 돈(n)을 순회하면서 최적의 선택을 갱신
        for n in nums:
            # 현재 집(n)을 포함한 최대 금액과 포함하지 않은 최대 금액 중 더 큰 값을 선택
            temp = max(n + rob1, rob2)

            # rob1을 rob2로 업데이트 (현재 집의 두 번째 이전 금액으로 이동)
            rob1 = rob2
            # rob2를 temp로 업데이트 (현재 집까지의 최대 금액)
            rob2 = temp

            # 상태를 출력하는 주석 (nums = [2, 7, 9, 3, 1]에 따른 동작 과정):
            # 현재 rob1과 rob2의 값을 따라가며 이해할 수 있음.
            # print(f"Current house value: {n}, rob1: {rob1}, rob2: {rob2}")

        # rob2에는 마지막 집까지 고려한 최대 금액이 저장되어 있음
        return rob2

        # === 동작 과정: nums = [2, 7, 9, 3, 1] ===
        # 초기 상태:
        # rob1 = 0, rob2 = 0

        # 첫 번째 집 (n = 2):
        # temp = max(2 + rob1, rob2) = max(2 + 0, 0) = 2
        # rob1 = rob2 = 0
        # rob2 = temp = 2
        # 첫 번째 집까지의 최대 금액은 2.

        # 두 번째 집 (n = 7):
        # temp = max(7 + rob1, rob2) = max(7 + 0, 2) = 7
        # rob1 = rob2 = 2
        # rob2 = temp = 7
        # 두 번째 집까지의 최대 금액은 7.

        # 세 번째 집 (n = 9):
        # temp = max(9 + rob1, rob2) = max(9 + 2, 7) = 11
        # rob1 = rob2 = 7
        # rob2 = temp = 11
        # 세 번째 집까지의 최대 금액은 11.

        # 네 번째 집 (n = 3):
        # temp = max(3 + rob1, rob2) = max(3 + 7, 11) = 11
        # rob1 = rob2 = 11
        # rob2 = temp = 11
        # 네 번째 집까지의 최대 금액은 11 (현재 집을 털지 않음).

        # 다섯 번째 집 (n = 1):
        # temp = max(1 + rob1, rob2) = max(1 + 11, 11) = 12
        # rob1 = rob2 = 11
        # rob2 = temp = 12
        # 다섯 번째 집까지의 최대 금액은 12.

        # 최종 반환값:
        # rob2 = 12
        # 마지막까지 고려한 결과로 최대 금액은 12.

참고 문제 풀이

https://youtu.be/73r3KWiEvyk?si=dz-HNvkF4gsIPi3m

============================================================================================

https://youtu.be/pEx5-hg4pr4?si=Y4qP2dyHkA60RhzD

재귀 : 시간: O(2^n), 공간 O(n) => time limit exceeded 시간 초과

class Solution:
    def rob(self, nums: List[int]) -> int:
        """
         O X ___
        [1,2,3,1]
        index 0 에 있는 집을 털었을때 최대 금액 = nums[0] + F(nums[2:])

         X _____
        [1,2,3,1]
        index 0 에 있는 집을 안 털었을때 최대 금액 = F(nums[1:])

        문제에서 요구하는 최대 금액 F(nums) = MAX(nums[0] + F(nums[2:]), F(nums[1:]))

        => 일반화
        F(start) = MAX(nums[start] + F(start+2), F(start+1))
        """
        # 재귀 함수로 구현(시간: O(2^n), 공간 O(n)) => time limit exceeded 시간 초과 
        def dfs(start): 
            if not start < len(nums): # start >= len(nums): 배열을 벋어난 경우
                return 0
            return max(nums[start] + dfs(start+2), dfs(start+1))
        return dfs(0)

메모리제이션 : 시간: O(n), 공간 O(n)

class Solution:
    def rob(self, nums: List[int]) -> int:
        """
         O X ___
        [1,2,3,1]
        index 0 에 있는 집을 털었을때 최대 금액 = nums[0] + F(nums[2:])

         X _____
        [1,2,3,1]
        index 0 에 있는 집을 안 털었을때 최대 금액 = F(nums[1:])

        문제에서 요구하는 최대 금액 F(nums) = MAX(nums[0] + F(nums[2:]), F(nums[1:]))

        => 일반화
        F(start) = MAX(nums[start] + F(start+2), F(start+1))
        """
        # # 재귀 함수로 구현(시간: O(2^n), 공간 O(n)) => time limit exceeded 시간 초과 
        # def dfs(start): 
        #     if not start < len(nums): # start >= len(nums): 배열을 벋어난 경우
        #         return 0
        #     return max(nums[start] + dfs(start+2), dfs(start+1))
        # return dfs(0)

        # 메모리제이션(시간: O(n), 공간 O(n))
        memo = {} # 해시 테이블
        def dfs(start): 
            if start in memo: # <- 해시 테이블을 통해, 중복연산을 모두 줄여줌
                return memo[start]

            if not start < len(nums): # start >= len(nums): 배열을 벋어난 경우
                # return 0
                memo[start] = 0
            else:
                memo[start] = max(nums[start] + dfs(start+2), dfs(start+1))

            return memo[start]

        return dfs(0)

DP로.. 시간: O(n), 공간 O(n)

class Solution:
    def rob(self, nums: List[int]) -> int:
        """
         O X ___
        [1,2,3,1]
        index 0 에 있는 집을 털었을때 최대 금액 = nums[0] + F(nums[2:])

         X _____
        [1,2,3,1]
        index 0 에 있는 집을 안 털었을때 최대 금액 = F(nums[1:])

        문제에서 요구하는 최대 금액 F(nums) = MAX(nums[0] + F(nums[2:]), F(nums[1:]))

        => 일반화
        F(start) = MAX(nums[start] + F(start+2), F(start+1))
        """
        # # # 재귀 함수로 구현(시간: O(2^n), 공간 O(n)) => time limit exceeded 시간 초과 
        # # def dfs(start): 
        # #     if not start < len(nums): # start >= len(nums): 배열을 벋어난 경우
        # #         return 0
        # #     return max(nums[start] + dfs(start+2), dfs(start+1))
        # # return dfs(0)

        # # 메모리제이션(시간: O(n), 공간 O(n))
        # memo = {} # 해시 테이블
        # def dfs(start): 
        #     if start in memo: # <- 해시 테이블을 통해, 중복연산을 모두 줄여줌
        #         return memo[start]

        #     if not start < len(nums): # start >= len(nums): 배열을 벋어난 경우
        #         # return 0
        #         memo[start] = 0
        #     else:
        #         memo[start] = max(nums[start] + dfs(start+2), dfs(start+1))

        #     return memo[start]

        # return dfs(0)
        dp = [0] * (len(nums)+1) # dp[0] 초기값 저장헤야 하므로
        dp[0] = 0
        dp[1] = nums[0]
        for n in range(2, len(nums)+1):
            dp[n] = max(nums[n-1] + dp[n-2], dp[n-1])
        return dp[-1] # dp의 맨 마지막값 반환

최종 변수 최적화. 시간: O(n), 공간 O(n)

class Solution:
    def rob(self, nums: List[int]) -> int:
        """
         O X ___
        [1,2,3,1]
        index 0 에 있는 집을 털었을때 최대 금액 = nums[0] + F(nums[2:])

         X _____
        [1,2,3,1]
        index 0 에 있는 집을 안 털었을때 최대 금액 = F(nums[1:])

        문제에서 요구하는 최대 금액 F(nums) = MAX(nums[0] + F(nums[2:]), F(nums[1:]))

        => 일반화
        F(start) = MAX(nums[start] + F(start+2), F(start+1))
        """        
        # dp[n-2], dp[n-1] 처럼 변수 2개만 더 있으면 되서, 저장공간 최적화 진행
        prev, curr = 0, 0 
        
        for num in nums:
            # num 을 사용할때는, num 과 prev(전전 단계 금액)을 사용
            # num 을 사용하지 않을때는, curr(전 단계 금액)을 사용
            prev, curr = curr, max(num+prev, curr)
        return curr

드디어 품 !!

class Solution:
    def rob(self, nums: List[int]) -> int:
        # 주어진 집들의 값을 복사하여 결과를 저장할 배열로 사용
        res = nums.copy()

        # 집이 한 채만 있을 경우, 그 집의 값을 반환
        if len(nums) == 1:
            return nums[0]

        # 집이 두 채만 있을 경우, 두 집 중 더 큰 값을 반환
        elif len(nums) == 2:
            return max(nums[0], nums[1])

        else:
            # 첫 번째 집을 털었을 때의 최대 값 설정
            res[0] = nums[0]
            # 두 번째 집까지 털었을 때의 최대 값 설정 (첫 번째와 두 번째 중 더 큰 값)
            res[1] = max(nums[0], nums[1])

            # 세 번째 집부터 마지막 집까지의 최대 값을 계산
            for i in range(2, len(nums)):
                # 현재 집을 털 경우와 털지 않을 경우 중 최대 값을 선택
                res[i] = max(nums[i] + res[i-2], res[i-1])

            # 마지막 집까지 털었을 때의 최대 값을 반환
            return res[len(nums) - 1]

시간 및 공간 복잡도

시간 복잡도: O(n)
- 리스트를 한 번 순회하며 최대 값을 계산합니다.
공간 복잡도: O(n)
- res 배열에 n개의 값을 저장합니다.

추가 문제들

이제 그냥 품

class Solution:
    def rob(self, nums: List[int]) -> int:
        if len(nums) == 1:
            return nums[0]
        elif len(nums) == 2:
            return max(nums[0], nums[1])
        else:
            maxRob = [0] * len(nums)
            maxRob[0] = nums[0]
            maxRob[1] = max(nums[0], nums[1])

            for i in range(2, len(nums)):
                maxRob[i] = max(nums[i] + maxRob[i-2], maxRob[i-1])
            return maxRob[len(nums)-1]

class Solution:
    def rob(self, nums: List[int]) -> int:
        n = len(nums)

        if n==1:
            return nums[n-1]
        elif n==2:
            return max(nums[n-1], nums[n-2])

        dp = [0] * n
        dp[0] = nums[0]

        for i in range(1, n):
            dp[i] = max(dp[i-1], dp[i-2]+nums[i])

        return dp[n-1]

'LeetCode > 주제별 보충' 카테고리의 다른 글

Tree: 1448. Count Good Nodes in Binary Tree (2)	2024.11.15
Tree: 104. Maximum Depth of Binary Tree (2)	2024.11.15
Bit: 338. Counting Bits (3)	2024.11.09
DP2D: 1143. Longest Common Subsequence (0)	2024.11.08
DP2D: 62. Unique Paths (0)	2024.11.08

현재글DP1D: 198. House Robber

hyunkookim 님의 블로그

hyunkookim 님의 블로그 입니다.

티스토리챌린지, 우선순위큐, dp, top150, leetcode75, monotonic stack, Two pointers, heap, Graphs, Coding Test, Backtracking, BFS, tree, dp2d, BST, dfs, array / string, LeetCode, 오블완, sorting,

Today :
Yesterday :

hyunkookim 님의 블로그