[LeetCode] House Robber - 완전 탐색에서 DP까지 이해하기

이번 주차에서 할당된 문제 중 정리해 봐야겠다고 생각한 문제는 House Robber다. 여러 방식으로 접근할 수 있고, DP로 개선해 나가는 과정과 공간 복잡도를 최적화하는 방식이 인상 깊었다. 그래서 이번 글에서는 이 문제를 나만의 방식으로 정리하면서 스터디 1주차를 마무리해 보려고 한다.

 

처음 봤을 때는 단순히 "인접한 집을 털면 안 된다"는 조건만 있는 문제처럼 보인다. 하지만 막상 모든 경우를 직접 탐색하려고 하면 생각보다 경우의 수가 빠르게 늘어난다.

 

그래서 이번 글에서는 처음에 완전 탐색 으로 접근한 뒤, 왜 시간 초과가 발생하는지 확인하고, 이를 메모이제이션 과 바텀업 DP로 개선하는 과정을 정리해보려고 한다.

 

 

문제 이해하기

문제 상황은 다음과 같다.

거리에 집들이 일렬로 있고, 각 집에는 일정 금액의 돈이 들어 있다. 도둑은 이 집들을 털려고 하지만, 인접한 두 집은 보안 시스템으로 연결되어 있다.

따라서 같은 날 밤에 인접한 두 집을 털면 경찰에 자동으로 신고된다.

 

입력으로는 각 집에 들어 있는 돈의 양을 나타내는 정수 배열 nums가 주어진다. 이때 인접한 집을 동시에 털지 않으면서 얻을 수 있는 최대 금액을 구하면 된다.

 

예를 들어 다음과 같은 배열이 있다고 하자.

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

이 경우 0번 집, 2번 집, 4번 집을 털면 다음과 같은 금액을 얻을 수 있다.

2 + 9 + 1 = 12

따라서 정답은 12가 된다.

핵심은 단순히 큰 금액의 집을 고르는 것이 아니라, 인접한 집을 고르지 않는 조건 안에서 최대 금액을 만드는 것이다.

 

 

처음 접근: 완전 탐색

처음에는 완전 탐색으로 접근해 보았다.

한 집을 털었다면 바로 다음 집은 털 수 없다. 따라서 현재 집을 턴 뒤에는 최소 두 칸 뒤의 집으로 이동해야 한다.

이때 다음 후보로는 현재 위치 + 2 또는 현재 위치 + 3 을 생각할 수 있다.

현재 집을 털었다면
다음에 볼 수 있는 집은 i + 2 또는 i + 3

 

여기서 i + 4를 바로 고려하지 않아도 되는 이유는, nums의 값이 음수가 아니기 때문이다. i + 4로 바로 가기 전에 i + 2를 추가로 털 수 있다면, 금액이 줄어들지 않는다. 그래서 다음 선택지는 i + 2, i + 3 정도만 고려해도 된다.

 

이를 바탕으로 코드를 작성하면 다음과 같다.

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

        if n == 1:
            return nums[0]

        max_money = 0

        def search_next_houses(last_house: int, current_money: int) -> None:
            nonlocal max_money

            for step in (2, 3):
                next_house = last_house + step

                if next_house >= n:
                    max_money = max(max_money, current_money)
                    return

                search_next_houses(next_house, current_money + nums[next_house])

        search_next_houses(0, nums[0])
        search_next_houses(1, nums[1])

        return max_money

 

이 코드는 가능한 경로를 재귀적으로 탐색한다.

 

예를 들어 0번 집에서 시작했다면, 그다음에는 2번 집 또는 3번 집으로 이동한다. 2번 집으로 갔다면 다시 4번 집 또는 5번 집을 확인한다. 이런 방식으로 더 이상 이동할 수 없을 때까지 탐색하고, 마지막에 max_money를 갱신한다.

 

하지만 이 방식은 문제가 있다.

한 번 호출될 때마다 다시 두 갈래로 나뉘기 때문에, 호출 수가 매우 빠르게 증가한다. 즉, 시간 복잡도가 지수적으로 커진다.

대략적으로 보면 다음과 같은 구조가 된다.

f(i)
 ├─ f(i + 2)
 └─ f(i + 3)

 

이런 재귀 구조는 입력 크기가 조금만 커져도 같은 계산을 반복하게 된다. 결국 Time Limit Exceeded가 발생할 수 있다.

 

또 하나 아쉬운 점은 함수가 값을 반환하는 구조가 아니라는 점이다. 현재 코드는 current_money를 계속 넘기고, 마지막에 전역처럼 사용하는 max_money를 갱신한다.

 

이 방식도 동작은 하지만, 메모이제이션을 적용하기에는 조금 불편하다. 특정 위치에서 시작했을 때 얻을 수 있는 최대 금액을 함수가 직접 반환하도록 바꾸는 편이 DP로 확장하기 좋다.

 

 

반환값 중심으로 바꾸기

이번에는 함수를 조금 다르게 정의해 보자.

기존에는 현재까지 훔친 금액을 current_money로 넘겼다. 하지만 이제는 다음과 같이 생각한다.

max_money_from(i)
= i번째 집을 털기 시작했을 때, 이후로 얻을 수 있는 최대 금액

 

즉, i번째 집에서 시작했을 때 얻을 수 있는 최대 금액을 반환하는 함수로 만드는 것이다.

그러면 함수 내부에서는 현재 집의 금액을 더한 뒤, 다음으로 갈 수 있는 i + 2, i + 3 중 더 좋은 선택을 고르면 된다.

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

        if nums_length == 1:
            return nums[0]

        def max_money_from(house_index: int) -> int:
            if house_index + 2 >= nums_length:
                return nums[house_index]

            if house_index + 3 >= nums_length:
                return nums[house_index] + nums[house_index + 2]

            return nums[house_index] + max(
                max_money_from(house_index + 2),
                max_money_from(house_index + 3)
            )

        return max(
            max_money_from(0),
            max_money_from(1)
        )

 

이제 max_money_from은 특정 인덱스에서 시작했을 때의 최대 금액을 반환한다.

예를 들어 max_money_from(2)는 2번 집을 턴다고 가정하고, 그 이후에 얻을 수 있는 최대 금액까지 포함해서 반환한다.

 

이전 코드보다 구조는 훨씬 좋아졌다. 하지만 아직 문제는 남아 있다.

여전히 같은 인덱스에 대한 계산이 여러 번 반복된다.

 

예를 들어 어떤 경로에서는 max_money_from(4)를 호출하고, 다른 경로에서도 다시 max_money_from(4)를 호출할 수 있다. 이때 결과는 항상 같다. 그런데 매번 다시 계산하고 있으므로 비효율적이다.

 

이런 상황에서는 메모이제이션 을 적용할 수 있다.

 

 

메모이제이션 적용하기

메모이제이션은 이미 계산한 결과를 저장해 두고, 같은 입력이 다시 들어오면 저장된 값을 바로 반환하는 방식이다.

현재 함수는 house_index 하나만 입력으로 받는다.

max_money_from(house_index)

 

따라서 house_index를 key로 사용해서 결과를 캐싱할 수 있다.

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

        if nums_length == 1:
            return nums[0]

        cache = {}

        def max_money_from(house_index: int) -> int:
            if house_index in cache:
                return cache[house_index]

            if house_index + 2 >= nums_length:
                result = nums[house_index]
            elif house_index + 3 >= nums_length:
                result = nums[house_index] + nums[house_index + 2]
            else:
                result = nums[house_index] + max(
                    max_money_from(house_index + 2),
                    max_money_from(house_index + 3)
                )

            cache[house_index] = result
            return result

        return max(
            max_money_from(0),
            max_money_from(1)
        )

이제 같은 house_index에 대해 다시 함수가 호출되면, 재귀를 더 진행하지 않고 cache에 저장된 값을 바로 반환한다.

이렇게 하면 각 인덱스에 대한 계산은 최대 한 번만 수행된다.

따라서 시간 복잡도는 nums의 길이를 n이라고 했을 때 O(n)이 되고, 공간 복잡도도 재귀 호출 스택에 의해 O(n)이 된다.

 

 

Bottom-up DP로 바꾸기

위 풀이는 재귀를 사용하는 Top-down 방식이다.

이번에는 재귀를 사용하지 않고, 반복문을 사용하는 Bottom-up 방식으로 바꿔보자.

 

먼저 dp 배열의 의미를 정의해야 한다.

dp[i] = i번째 집까지 고려했을 때 훔칠 수 있는 최대 금액

여기서 중요한 점이 있다.

i번째 집까지 고려한다는 말은 i번째 집을 반드시 턴다는 뜻이 아니다.

0번 집부터 i번 집까지의 범위 안에서, 조건을 지키며 얻을 수 있는 최대 금액이라는 뜻이다.

 

따라서 dp[i]를 구할 때는 두 가지 선택지가 있다.

 

첫 번째는 i번째 집을 터는 경우다.

이 경우 바로 이전 집인 i-1번째 집은 털 수 없다. 따라서 i-2번째 집까지의 최대 금액에 현재 집의 금액을 더해야 한다.

dp[i-2] + nums[i]

 

두 번째는 i번째 집을 털지 않는 경우다.

이 경우에는 i-1번째 집까지 고려했을 때의 최대 금액을 그대로 가져오면 된다.

dp[i-1]

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

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

 

i-3 이하의 경우를 따로 고려하지 않아도 되는 이유는, 이미 dp[i-2]와 dp[i-1] 안에 그 이전 선택들이 최적으로 반영되어 있기 때문이다.

이제 이 점화식을 코드로 옮기면 된다.

class Solution:
    def rob(self, nums: List[int]) -> int:
        # dp[i]: i번째 집까지 고려했을 때 훔칠 수 있는 최대 금액
        # dp[i] = max(dp[i-2] + nums[i], dp[i-1])

        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 - 2] + nums[i], dp[i - 1])

        return dp[-1]

이 방식은 재귀를 사용하지 않는다. 앞에서부터 차례대로 dp 값을 채워 나가고, 마지막에 dp[-1]을 반환한다.

 

시간 복잡도는 O(n)이다. 배열을 한 번 순회하기 때문이다.

공간 복잡도도 O(n)이다. dp 배열을 입력 크기만큼 만들기 때문이다.

 

 

공간 복잡도 줄이기

위 코드를 보면 dp[i]를 계산할 때 사용하는 값은 두 개뿐이다.

dp[i-2]
dp[i-1]

즉, 매번 전체 dp 배열이 필요한 것이 아니다.

현재 위치를 계산하기 위해서는 바로 전 값과 전전 값만 있으면 된다. 이 점을 이용하면 공간 복잡도를 O(n)에서 O(1)로 줄일 수 있다.

 

dp 배열 대신 두 변수로만 구현하면 아래와 같이 된다.

class Solution:
    def rob(self, nums: List[int]) -> int:
        # dp[i]: i번째 집까지 고려했을 때 훔칠 수 있는 최대 금액
        # dp[i] = max(dp[i-2] + nums[i], dp[i-1])

        if len(nums) == 1:
            return nums[0]

        # i = 2부터 계산할 것이므로 dp[0], dp[1]에 해당하는 값만 저장
        prev = nums[0]                 # dp[i-2]
        curr = max(nums[0], nums[1])   # dp[i-1]

        for i in range(2, len(nums)):
            new_curr = max(prev + nums[i], curr)  # dp[i]

            prev = curr
            curr = new_curr

        return curr

여기서 핵심은 이 부분이다.

new_curr = max(prev + nums[i], curr)

이는 기존 점화식과 같다.

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

그리고 계산이 끝난 뒤에는 다음 반복을 위해 값을 한 칸씩 밀어준다.

prev = curr
curr = new_curr

예를 들어 현재 i에 대해 new_curr를 계산했다면, 다음 반복에서는 방금 계산한 값이 dp[i-1] 역할을 해야 한다.

그래서 curr를 new_curr로 바꿔주는 것이다.

 

이제 시간 복잡도는 여전히 O(n)이지만, 별도의 dp 배열을 만들지 않으므로 공간 복잡도는 O(1)이 된다.

 

 

정리

이번 문제는 처음에는 단순한 탐색 문제처럼 보였지만, 실제로는 DP로 풀기 좋은 문제였다.

 

완전 탐색으로 접근하면 가능한 경우를 모두 확인할 수는 있다. 하지만 같은 계산이 반복되기 때문에 시간 복잡도가 지수적으로 커진다.

이를 개선하기 위해 먼저 함수가 값을 반환하는 구조로 바꾸었다. 특정 인덱스에서 시작했을 때 얻을 수 있는 최대 금액을 반환하도록 만들면, 같은 인덱스에 대한 결과를 캐싱할 수 있다. 이것이 Top-down DP, 즉 메모이제이션 방식이다.

 

이후에는 재귀를 사용하지 않는 Bottom-up 방식으로 바꾸었다. dp[i]를 i번째 집까지 고려했을 때 얻을 수 있는 최대 금액으로 정의하고, 현재 집을 터는 경우와 털지 않는 경우 중 더 큰 값을 선택했다.

 

점화식은 다음과 같다.

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

 

마지막으로 이 점화식에서 실제로 필요한 값은 dp[i-2], dp[i-1]뿐이라는 점을 이용해 공간 복잡도를 O(1)로 줄일 수 있었다.

정리하면 다음과 같다.

완전 탐색
- 시간 복잡도: O(2^n)
- 공간 복잡도: O(n)

Top-down DP + Memoization
- 시간 복잡도: O(n)
- 공간 복잡도: O(n)

Bottom-up DP + Tabulation
- 시간 복잡도: O(n)
- 공간 복잡도: O(n)

Bottom-up DP + 공간 최적화
- 시간 복잡도: O(n)
- 공간 복잡도: O(1)

 

결국 이 문제의 핵심은 "현재 집을 털 것인가, 털지 않을 것인가"를 기준으로 상태를 정의하는 것이다.

처음부터 점화식이 바로 떠오르지 않더라도, 완전 탐색으로 가능한 선택지를 먼저 생각해 보면 DP로 바꾸는 흐름을 이해하기 쉬워진다.

 

 

스터디 1주차 회고

이번 주차에는 스터디에 늦게 참여하게 되어 다른 스터디원분들께 코드 리뷰를 받지 못한 점이 아쉬웠다. 그래도 직접 다른 분들의 코드를 리뷰해 보면서, 내 코드도 읽는 사람을 고려해 더 명확하게 작성해야겠다고 느꼈다. 다음 주차부터는 리뷰를 받을 상황까지 감안해서 변수명과 주석을 더 신경 써서 작성해야겠다.