LeetCode 198 - House Robber

인접한 집을 동시에 털 수 없다는 조건에서 얻을 수 있는 최대 금액을 구하는 Medium DP 문제다. 각 위치에서 선택지는 현재 집을 털고 다음 집을 건너뛰거나, 현재 집을 건너뛰고 다음 집으로 이동하는 두 가지로 정리된다.

문제 링크 & 설명

• 문제 링크: 198. House Robber
• 요약: 정수 배열 nums가 주어졌을 때, 서로 인접한 원소를 동시에 선택하지 않으면서 얻을 수 있는 최대 합을 반환하는 문제.

예를 들어 입력이 이렇게 주어진다고 해보자.

nums = [1, 2, 3, 1]

1번 집과 3번 집을 고르면 합이 4가 되고, 인접한 집을 같이 고르지 않았기 때문에 조건도 만족한다. 이 경우 반환값은 4다.

접근 방법

처음 이 문제를 보면 각 집을 고를지 말지 결정하는 문제로 볼 수 있다. 현재 위치가 house일 때, 현재 집을 털면 바로 다음 집은 털 수 없으므로 house + 2로 이동해야 하고, 현재 집을 건너뛰면 house + 1로 이동하면 된다.

그래서 재귀 함수는 특정 위치에서 시작했을 때 얻을 수 있는 최대 금액을 반환하도록 잡았다.

rec(house) = max(nums[house] + rec(house + 2), rec(house + 1))

이 식에서 왼쪽 선택지는 현재 집을 턴 경우이고, 오른쪽 선택지는 현재 집을 건너뛴 경우다. house가 배열 범위를 벗어나면 더 이상 털 집이 없으므로 0을 반환한다.

if house >= len(nums):
    return 0

memoization 없이 재귀만 사용하면 호출이 두 갈래로 계속 갈라진다. rec(0)에서 현재 집을 털면 1번 집은 건너뛰어야 하므로 rec(2)로 이동하고, 현재 집을 털지 않으면 rec(1)로 이동한다. 여기까지는 선택지가 자연스럽다.

그런데 rec(1)에서도 다시 선택지가 갈라진다. 1번 집을 털면 rec(3)으로 가고, 1번 집을 털지 않으면 rec(2)로 간다. 결국 rec(2)는 “0번 집을 털고 1번을 건너뛴 경우”에서도 필요하고, “0번 집을 건너뛰고 1번 집도 건너뛴 경우”에서도 다시 필요해진다.

이렇게 같은 위치의 결과가 여러 경로에서 반복해서 계산된다. 깊이가 늘어날수록 호출 트리가 거의 두 배씩 커지기 때문에, memoization이 없으면 시간복잡도는 O(2ⁿ)까지 커질 수 있다. 그래서 한 번 계산한 house의 결과는 memo에 저장해두고 다시 요청되면 바로 반환한다.

if house in memo:
    return memo[house]

이렇게 하면 재귀 구조는 유지하면서도 각 위치의 결과를 한 번만 계산하게 된다.

복잡도 분석

• 시간 복잡도: O(n)

  • memoization 덕분에 각 house 위치는 한 번만 계산된다.

• 공간 복잡도: O(n)

  • memo dictionary가 위치별 결과를 저장하고, 재귀 호출 stack도 최악의 경우 입력 크기에 비례해서 깊어질 수 있다.

구현 코드

from typing import Dict, List

class Solution:
    def rec(self, house: int, nums: List[int], memo: Dict[int, int]) -> int:
        if house >= len(nums):
            return 0

        if house in memo:
            return memo[house]

        current_robbed = max(
            nums[house] + self.rec(house + 2, nums, memo),
            self.rec(house + 1, nums, memo),
        )
        memo[house] = current_robbed
        return current_robbed

    def rob(self, nums: List[int]) -> int:
        memo: Dict[int, int] = {}
        return self.rec(0, nums, memo)

요약 및 회고

이 문제는 현재 집을 털지 말지의 선택을 재귀식으로 옮기면 구조가 단순해진다. 다만 재귀만 쓰면 같은 위치의 결과를 반복해서 계산하므로, house index를 key로 memoization을 걸어 각 부분 문제를 한 번씩만 풀도록 만드는 것이 top-down DP의 핵심이었다.