House Robber

LeetCode의 House Robber 문제를 함께 풀어보도록 하겠습니다.

문제

당신은 어떤 길을 쭉 따라서 여러 집을 털려고 하는 도둑이다. 각 집에는 일정 금액이 돈이 모여져있으며 같은 밤에 인접한 두 집을 털리면 자동으로 경찰에게 신고가 들어가는 보안 시스템 때문에 인접하고 있는 두 개의 집은 털 수가 없다.

모든 집에 있는 돈을 나타내는 배열 nums가 주어졌을 때, 경찰에 걸리지 않고 오늘 밤에 털 수 있는 최대 금액을 구하라.

예제

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

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

풀이 1

어떻게 하면 도둑이 최대 금액을 훔칠 수 있을까요? 다행히 돈이 음수인 집은 없으니 최대한 많은 집을 털어야할테고 당연히 모든 집을 다 터는 게 유리할텐데요. 하지만 보안 시스템 때문에 인접하고 있는 두 집을 털면 경찰에 걸리니 조심해야겠죠?

문제에서 주어진 첫 번째 예제를 통해 한 번 차근차근 생각해보겠습니다.

첫 번째 집을 털면 인접한 두 번째 집을 못 털겠죠? 대신 세 번째 집부터는 자유롭게 털 수 있을 것입니다.

 O  X  ____
[1, 2, 3, 1]

반대로 첫 번째 집을 안 털었다면 두 번째 집부터는 자유롭게 털 수 있다는 얘기가 됩니다.

 X  _______
[1, 2, 3, 1]

이렇게 첫 번째 집을 털지 말지 결정하면, 다음으로 털 수 있는 첫 번째 집이 결정이 되는데요. 첫 번째 집을 텄었을 경우 도둑이 훔칠 수 있는 최대 금액은, 세 번째 집부터 마지막 집까지 털어서 훔친 최대 금액에 첫 번재 집에서 훔친 금액을 더한 것일 겁니다. 반대로 첫 번째 집을 안 털은 경우 도둑이 훔칠 수 있는 최대 금액은, 두 번째 집부터 마지막 집까지 털어서 훔진 최대 금액일 것입니다. 그리고 이 두 개의 금액 중에서 더 큰 금액이 문제에서 최종적으로 요구하는 모든 경우를 커버하는 최대 금액일 것입니다.

F()를 집에 모여있는 돈의 배열 nums가 주어졌을 때 훔친 수 있는 최대 금액을 구하는 함수라고 가정하고 위 로직은 다음과 같이 수식으로 나타낼 수 있습니다.

인덱스 0에 있는 집을 털었을 때 최대 금액 = nums[0] + F(nums[2:])
인덱스 0에 있는 집을 안 털었을 때  최대 금액 = F(nums[1:])

F(nums) = MAX(nums[0] + F(nums[2:]), F(nums[1:]))

이 수식을 통해 우리는 이 문제를 재귀적으로 풀 수 있다라는 것을 알 수 있는데요. 인덱스 0에서 시작하는 최대 금액을 구하려면 인덱스 2에서 시작하는 최대 금액과, 인덱스 1에서 시작하는 최대 금액을 먼저 구해야하기 때문입니다. 마찬가지로 인덱스 1에서 시작하는 최대 금액을 구하려면, 인덱스 3에서 시작하는 최대 금액과 인덱스 2에서 시작한 최대 금액을 먼저 구해야하기 때문입니다. 다시 말해 우선 어떤 집을 털지 말지 결정해놓으면, 재귀 함수를 호출할 배열의 범위, 즉 시작 인덱스를 결정할 수 있게 됩니다.

따라서 배열 내에 모든 시작 인덱스에 적용할 수 있도록 start라는 변수를 써서 수식을 일반화시키면 다음과 같을 것입니다.

F(start) = MAX(nums[start] + F(start + 2), F(start + 1))

이렇게 시작 인덱스를 매번 1또는 2씩 늘려가면서 F() 함수를 재귀적으로 호출하다보면 언젠가는 F() 함수의 인자로 비어있는 배열이 넘어오게 되겠죠? 이 경우가 바로 재귀 함수의 기저 사례(base case)가 되며, 이 때는 더 이상 털 집이 없다는 뜻이므로 0을 반환하면 됩니다.

이 재귀 알고리즘을 코드로 작성해보겠습니다.

class Solution:
    def rob(self, nums: List[int]) -> int:
        def dfs(start):
            if not start < len(nums):
                return 0
            return max(nums[start] + dfs(start + 2), dfs(start + 1))

        return dfs(0)

이 알고리즘은 매번 재귀 함수가 호출될 때 마다 두 번의 추가적인 재귀 호출이 일어나게 되므로 시간 복잡도는 O(2^n)입니다. 반면에 주어진 배열가 길이가 길어지면 길어질 수록 재귀 호출 스택의 길이도 그에 비례하여 길어지므로 공간 복잡도는 O(n)입니다.

따라서 이 코드를 LeetCode에 제출하면 시간 한도를 초과하여 Time Limit Exceeded 오류가 발생하게 됩니다.

풀이 2

어떻게 하면 위 풀이의 성능을 개선하여 LeetCode에서 통과할 수 있을까요? 아래 재귀 함수가 호출되는 모습에서 불필요하게 반복되고 있는 함수 호출을 찾아보시겠어요? (인자로 시작 인덱스를 넘겨야하지만 좀 더 알아보기 쉽도록 부분 배열로 표시하였습니다.)

F([1, 2, 3, 1]) => MAX(1 + F([3, 1]), F([2, 3, 1])) = MAX(1 + 3, 3) = 4
    F([3, 1]) => MAX(3 + F([]), F(1)) = MAX(3 + 0, 1) = 3
        F([]) => 0
        F([1]) => MAX(1 + F([]), F([])) = MAX(1 + 0, 0) = 1
            F([]) => 0
            F([]) => 0
    F([2, 3, 1]) => MAX(2 + F([1]), F([3, 1])) = MAX(2 + 1, 3) = 3
        F([1]) => MAX(1 + F([]), F([])) = MAX(1 + 0, 0) = 1
            F([]) => 0
            F([]) => 0
        F([3, 1]) => MAX(3 + F([]), F(1)) = MAX(3 + 0, 1) = 3
            F([]) => 0
            F([1]) => MAX(1 + 0, 0) = 1
                F([]) => 0
                F([]) => 0

유심히 관찰해 보시면 F([3, 1])은 2번 호출되고 있고, F([1])은 3번 호출되고 있으며, F([])은 무려 8번이나 호출되고 있다는 것을 알 수 있는데요. 이렇게 낭비되는 연산은 주어진 배열의 길이가 길어질 수록 걷잡을 수 없도록 늘어나겠죠?

메모이제이션(memoization) 기법을 이용해서 함수 호출의 결과를 저장해두고 재사용하면 이렇게 불필요하게 반되는 연산을 제거할 수 있을 것입니다.

class Solution:
    def rob(self, nums: List[int]) -> int:
        memo = {}

        def dfs(start):
            if start in memo:
                return memo[start]
            if not start < len(nums):
                memo[start] = 0
            else:
                memo[start] = max(nums[start] + dfs(start + 2), dfs(start + 1))
            return memo[start]

        return dfs(0)

이렇게 알고리즘을 최적화해주면 시간 복잡도를 기존 O(2^n)에서 O(n)로 대폭 향상시킬 수 있습니다. 이 코드를 LeetCode에 다시 제출해보면 이번에는 시간 제한이 걸리지 않고 통과할 것입니다 🤗

풀이 3

위 재귀 풀이에서는 더 큰 배열에 대한 결과를 구하기 위해서 더 작은 배열에 대한 결과가 계산되기를 기다리는 방식으로 문제를 해결을 하는데요. 이렇게 Top-down 방향으로 문제에 접근을 해봤으니 이번에는 정반대인 Bottom-up 방향으로도 접근해볼까요?

이 문제는 동적 계획법 (Dynamic Programming)이라는 테크닉을 사용하면 반복 알고리즘으로도 해결할 수 있는데요. 기본적인 아이디어는 빈 배열부터 하나 씩 배열의 크기를 늘려가면서 최대 금액을 배열에 저장해두고 작은 크기의 배열을 상대로 저장해둔 계산 결과를 더 큰 크기의 배열을 상대로 계산할 때 활용하는 것입니다. 각 배열의 크기에 대한 계산 결과는 DP라는 배열에 저장해놓고 재활용하면 될 것 같아요.

그럼 문제에서 주어진 예제 배열인 [1, 2, 3, 1]을 통해서 이 아이디어를 적용해보겠습니다.

먼저 털 집이 하나도 없을 때 훔칠 수 있는 최대 금액은 얼마일까요? 당연히 0이 겠죠?

[]

DP: [0]

배열의 크기를 한 칸 늘리면 훔칠 수 있는 최대 금액이 얼마가 될까요? 털 집이 하나 밖에 없으니 첫 번째 집에 있는 금액 외에는 딱히 선택지가 없을 것입니다.

[1]

DP: [0, 1]

배열의 크기를 한 칸 더 늘려보면 어떻게 될까요? 이제 부터는 기존에 DP 배열에 구해놓은 더 작은 범위의 최대 금액을 현재 범위의 최대 금액을 구하는데 활용할 수 있습니다.

[1, 2]

MAX(2 + DP[0], DP[1]) = MAX(2 + 0, 1) = 2
DP: [0, 1, 2]

배열의 크기를 한 칸 더 늘리면 털 수 있는 집의 범위에 세 번째 집까지 들어오게 되죠?

[1, 2, 3]

MAX(3 + DP[1], DP[2]) = MAX(3 + 1, 4) = 4
DP: [0, 1, 2, 4]

배열의 크기를 한 칸 더 늘리면 털 수 있는 집의 범위에 마지막 집까지 들어오게 되죠?

[1, 2, 3, 1]

MAX(1 + DP[2], DP[3]) = MAX(1 + 2, 2) = 4
DP: [0, 1, 2, 4, 4]

재귀 알고리즘보다 훨씬 단순한 방법으로 전체 배열에 대한 결과가 구해지죠?

이 DP 알고리즘을 구현해보면 다음과 같습니다.

class Solution:
    def rob(self, nums: List[int]) -> int:
        dp = [0] * (len(nums) + 1)
        dp[1] = nums[0]
        for n in range(2, len(dp)):
            dp[n] = max(nums[n - 1] + dp[n - 2], dp[n - 1])
        return dp[-1]

같은 알고리즘을 자바스크립트로도 구현해보았습니다.

function rob(nums: number[]): number {
  const dp = new Array(nums.length + 1);
  dp[0] = 0;
  dp[1] = nums[0];
  for (let i = 2; i < dp.length; i++) {
    dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i - 1]);
  }
  return dp[dp.length - 1];
}

이 DP 알고리즘의 시간 복잡도와 공간 복잡도는 모두 O(n)으로써 메모이제이션을 적용한 재귀 알고리즘과 크게 다르지 않은데요. 그래도 전반적으로 코드가 짧아지고 이해하기기 쉬워지는 것을 알 수 있습니다.

풀이 4

위 다이나믹 프로그래밍 알고리즘은 메모리 사용량 측면에서 개선의 여지가 보이는데요. 훔칠 수 있는 최대 금액을 굳이 모든 크기의 배열에 대해서 다 저장해 둘 필요가 있을까요?

배열의 크기가 1일 때 계산 결과와 배열의 크기가 2일 때 계산 결과는 크기가 3인 배열에 대한 결과를 구할 때 활용하면 그 이후로는 쓸모가 없습니다.

이를 통해 우리는 현재 배열의 크기가 보다 1과 2가 작은 크기의 배열에 대한 계산 결과만 저장해두면 된다는 것을 깨닫게 됩니다. 따라서 길이가 n + 1인 배열 대신에 단 2개의 변수만으로도 이 알고리즘은 구현할 수 있습니다.

class Solution:
    def rob(self, nums: List[int]) -> int:
        prev, curr = 0, 0
        for num in nums:
            prev, curr = curr, max(num + prev, curr)
        return curr

이렇게 알고리즘을 최적화해주면 공간 복잡도를 O(1)로 내릴 수 있습니다. 처음에 작성한 코드도 나쁘지는 않지만 이렇게 추가적으로 최적화까지 해주면 코딩 시험에서 더 좋은 결과를 얻을 수 있을 것입니다.