House Robber

Q: 왜 집을 하나씩 건너뛰어 털면 House Robber 문제가 해결되지 않을까요?

최선의 계획은 때로 집 두 채를 연속으로 건너뜁니다. [10, 1, 1, 10] 에서는 짝수 번째 집들과 홀수 번째 집들의 합이 모두 11인 반면, 첫 번째 집과 마지막 집의 합은 20입니다.

보통동적 계획법

+10

집들이 거리 옆에 일렬로 서 있고, nums[i]는 i번 집에 있는 돈입니다. 원하는 집에서 돈을 가져갈 수 있지만, 서로 이웃한 두 집에서 동시에 가져갈 수는 없습니다. 가져갈 수 있는 가장 큰 총액을 반환하세요.

함수

rob(nums: integer-array) → integer

numsinteger-array: 거리 순서대로 각 집에 있는 돈
반환값integer: 서로 인접한 두 집에서 가져오지 않고 가져갈 수 있는 최대 총액

제약 조건

1 ≤ nums.length ≤ 10⁴
0 ≤ nums[i] ≤ 1000
정답은 최대 5 × 10⁶이므로 부호 있는 32비트 정수에 들어갑니다.

예제

입력: nums = [5, 3, 4, 11, 2]
출력: 16
설명: 집 0과 3에서 5와 11을 가져와 16을 만드세요. 집을 연속으로 두 개 건너뛰어도 되며, 이 경우 다른 모든 계획보다 더 좋은 결과를 냅니다: 5 + 4 + 2 = 11, 3 + 11 = 14.

후속 질문

가져갈 집들과 총합을 함께 반환하세요. 그 목록을 다시 만들려면 표에서 무엇을 보관해야 하며, 누적 합계 두 개로도 할 수 있을까요?

힌트

하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.

3개 중 0개 열림

풀이

지름길은 실패합니다. 한 집씩 건너뛰어 선택하면 [5, 3, 4, 11, 2]에서 5와 11을 놓치고, 가장 돈이 많은 집을 먼저 선택하면 [3, 4, 3]에서 손해를 봅니다. 대신 한 번에 집 하나씩 결정하세요. 어떤 집까지의 최댓값은 그 집보다 두 집 앞까지의 최댓값에만 달려 있습니다.

모든 집에서 두 선택지를 모두 시도해 보세요

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

어떤 계획이든 마지막 집을 건너뛰거나 선택합니다. 건너뛰면 처음 n-1개 집에 대한 최선의 계획이 남고, 선택하면 처음 n-2개 집에 대한 최선의 계획에 nums[n-1]을 더합니다. 따라서 most(k) = max(most(k-1), most(k-2) + nums[k-1])이고, most(0) = 0, most(1) = nums[0]입니다. 두 분기는 모든 계획을 포괄하므로 답은 정확합니다.

두 분기는 서로 겹칩니다. most(k-1)은 다시 most(k-2)를 계산하며, 호출 횟수는 피보나치 수처럼 약 1.6^n으로 증가합니다. 집이 40채면 호출 횟수가 3억 회를 넘고, n은 10^4까지 커집니다.

알고리즘

처음 k개의 집에서 가져갈 수 있는 최대 금액을 반환하는 도우미 함수 most(k)를 작성하세요.
k가 0이면 0을 반환하고, k가 1이면 nums[0]을 반환하세요.
그렇지 않으면 skip = most(k-1)과 take = most(k-2) + nums[k-1]을 계산하세요.
둘 중 더 큰 값을 반환하세요. 정답은 most(n)입니다.

def rob(nums):
    def most(k):
        # The most you can take from the first k houses
        if k == 0:
            return 0
        if k == 1:
            return nums[0]
        # Skip house k-1, or take it and skip house k-2
        return max(most(k - 1), most(k - 2) + nums[k - 1])

    return most(len(nums))

상향식 테이블

핵심 아이디어

재귀는 most(0)부터 most(n)까지만 묻습니다. 총 n + 1개의 질문입니다. 각 질문에 한 번씩 답해 best 표에 저장합니다. best[0] = 0과 best[1] = nums[0]에서 시작해 k = 2부터 위쪽으로 채우면, 각 답을 계산할 때 읽는 두 항목이 이미 채워져 있습니다.

[5, 3, 4, 11, 2]의 표는 0, 5, 5, 9, 16, 16입니다. k = 4일 때, 3번 집을 건너뛰면 best[3] = 9가 유지되는 반면, best[2] = 5에 11을 더하면 16이 되어 더 큰 값이 됩니다. 각 항목에는 비교 한 번이 필요합니다. 시간 O(n), 공간 O(n)입니다.

알고리즘

n + 1개의 항목이 있는 best 테이블을 만듭니다.
best[0] = 0 및 best[1] = nums[0]으로 설정합니다.
2부터 n까지의 k에 대해 best[k]를 best[k-1]과 best[k-2] + nums[k-1] 중 더 큰 값으로 설정합니다.
best[n]을 반환합니다.

def rob(nums):
    n = len(nums)
    # best[k] is the most you can take from the first k houses
    best = [0] * (n + 1)
    best[1] = nums[0]
    for k in range(2, n + 1):
        # Skip house k-1, or take it on top of the best from the first k-2 houses
        best[k] = max(best[k - 1], best[k - 2] + nums[k - 1])
    return best[n]

두 개의 누적 합계

핵심 아이디어

각 항목은 바로 앞의 두 항목만 읽으므로, 표 대신 숫자 두 개를 유지하세요. twoBack과 oneBack은 각각 두 집 전까지의 최댓값과 바로 이전 집까지의 최댓값입니다. x를 가진 집에 대해서 새로운 최댓값은 max(oneBack, twoBack + x)입니다. 그런 다음 두 값을 앞으로 옮깁니다. 두 값은 모두 첫 번째 집 앞의 빈 거리를 나타내는 0에서 시작하므로, 집이 하나뿐인 거리도 특별히 처리할 필요가 없습니다. 시간 복잡도는 O(n)으로 유지되고, 메모리 사용량은 O(1)로 줄어듭니다.

알고리즘

twoBack과 oneBack을 0으로 설정합니다.
nums의 각 값 x에 대해 current = max(oneBack, twoBack + x)를 계산합니다.
oneBack을 twoBack에 넣은 다음, current를 oneBack에 넣습니다.
마지막 집을 지나면 oneBack을 반환합니다.

def rob(nums):
    # The best totals from the houses up to two back and up to one back
    two_back, one_back = 0, 0
    for amount in nums:
        # Skip this house, or take it on top of the best from two back
        two_back, one_back = one_back, max(one_back, two_back + amount)
    return one_back

함정과 경계 사례

oneBack을 twoBack에 복사하기 전에 덮어쓰는 것. 그러면 다음 집에서 잘못된 합계를 읽게 됩니다. 먼저 새로운 최댓값을 계산한 다음 값을 이동하거나, 두 값을 한 번에 할당하세요.
nums[1]을 읽거나, 처음부터 best[1]과 best[2]를 설정하는 것. 둘 다 [0]과 같은 집이 하나뿐인 거리에서 오류가 발생합니다.
Lua와 R에서는 배열이 1부터 시작하므로, k-1번 집의 금액은 nums[k]입니다.

자주 묻는 질문3

House Robber의 시간 및 공간 복잡도는 무엇인가요?

동적 프로그래밍은 각 집을 한 번씩 살펴보므로 O(n) 시간이 걸립니다. 전체 테이블은 O(n) 공간을 사용하며, 마지막 두 합계만 유지하면 O(1)로 줄어듭니다. 답을 저장하지 않는 단순 재귀는 약 1.6^n번 호출됩니다.

왜 집을 하나씩 건너뛰어 털면 House Robber 문제가 해결되지 않을까요?

최선의 계획은 때로 집 두 채를 연속으로 건너뜁니다. [10, 1, 1, 10]에서는 짝수 번째 집들과 홀수 번째 집들의 합이 모두 11인 반면, 첫 번째 집과 마지막 집의 합은 20입니다.

집들이 원형으로 배치되어 있을 때 House Robber 문제를 어떻게 해결하나요?

원형에서는 첫 번째 집과 마지막 집이 이웃이므로, 계획에는 둘 중 하나만 포함됩니다. 직선형 거리의 해결 방법을 두 번 실행합니다. 한 번은 마지막 집을 제외하고, 한 번은 첫 번째 집을 제외한 다음 더 큰 결과를 반환합니다. 집이 하나뿐인 경우는 특별한 경우로, 답은 그 집입니다.

def rob(nums):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자

nums = [5, 3, 4, 11, 2]

예상 출력

House Robber

함수

제약 조건

예제

힌트

풀이

모든 집에서 두 선택지를 모두 시도해 보세요

상향식 테이블

두 개의 누적 합계

함정과 경계 사례

자주 묻는 질문3

비슷한 문제