House Robber
집들이 거리를 따라 한 줄로 늘어서 있고, nums[i]는 i번 집에 있는 돈입니다. 원하는 집에서 돈을 가져갈 수 있지만, 서로 이웃한 두 집에서는 가져갈 수 없습니다. 가져갈 수 있는 돈의 총액 중 최댓값을 반환하세요.
함수
- numsinteger-array
- 도로 순서대로 각 집에 있는 돈
- 반환값integer
- 서로 인접한 두 집에서 가져오지 않고 가져갈 수 있는 가장 큰 총액
제약 조건
1 ≤ nums.length ≤ 1040 ≤ nums[i] ≤ 1000- 정답은 최대
5 × 106이므로 부호 있는 32비트 정수에 들어갑니다.
예제
- 입력
- nums = [5, 3, 4, 11, 2]
- 출력
- 16
- 설명
- 집 0과 3에서 5와 11을 선택해 16을 만드세요. 연속으로 두 집을 건너뛰어도 되며, 이 경우 다른 모든 계획보다 낫습니다. 5 + 4 + 2 = 11이고 3 + 11 = 14입니다.
- 입력
- nums = [3, 10, 3]
- 출력
- 10
- 설명
- 양쪽 끝 집을 합하면 3 + 3 = 6입니다. 가운데 집 하나만 선택하면 10을 얻지만, 그 집을 선택하면 양옆의 집은 모두 선택할 수 없습니다.
- 입력
- nums = [2, 9, 3, 1, 8]
- 출력
- 17
- 설명
- 9와 8은 서로 이웃하지 않는 1번 집과 4번 집에 있으므로 합계는 17입니다. 시작점부터 한 집씩 건너뛰며 더하면 2 + 3 + 8 = 13만 나옵니다.
제출 시 숨은 테스트 +16개
후속 질문
가져갈 집들과 합계도 반환하세요. 그 목록을 다시 만들려면 표에서 무엇을 보관해야 하며, 두 개의 누계만으로 여전히 목록을 만들 수 있을까요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
마지막 집을 살펴보세요. 계획은 그 집을 선택하거나 건너뜁니다. 각 선택을 하면 무엇을 해결해야 할까요?
집
k-1을 건너뛰면, 가장 좋은 결과는 처음k-1개의 집에서 얻을 수 있는 최선의 결과입니다. 집을 선택하면, 처음k-2개의 집에서 얻을 수 있는 최선의 결과에nums[k-1]을 더합니다.k개의 집에 대한 답은 두 값 중 더 큰 값입니다.거리의 시작부터 최적의 총합을 채우세요. 집이 하나도 없는 경우는 0부터 시작합니다. 각 값은 이전 두 값만 있으면 되므로 변수 두 개면 충분합니다.
풀이
명백해 보이는 지름길은 통하지 않습니다. 한 집씩 건너뛰어 선택하면 [5, 3, 4, 11, 2]에서 5와 11처럼 두 집을 연달아 건너뛰는 계획을 놓치고, 가장 부유한 집을 먼저 선택하는 방법은 [3, 4, 3]에서 통하지 않습니다. 여기서는 4가 두 집의 합계인 6을 막기 때문입니다. 효과적인 방법은 한 번에 한 집씩 결정하는 것입니다. 어떤 집까지의 최댓값은 그 집에서 두 집 앞까지의 최댓값들에만 달려 있습니다.
각 집에서 두 가지 선택지를 모두 시도해 보세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
마지막 집인 n-1번 집을 살펴보세요. 어떤 계획이든 이 집을 건너뛰거나 선택합니다. 건너뛴다면 가능한 최선은 처음 n-1개 집에 대한 최선의 계획입니다. 선택한다면 n-2번 집은 선택할 수 없으므로, 처음 n-2개 집에 대한 최선의 계획에 nums[n-1]을 더합니다. 두 경우 중 더 큰 값이 정답입니다.
이를 함수 most(k)로 표현해 보세요. 처음 k개 집에서 선택할 수 있는 최대 금액입니다. 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억 회를 넘고, 테스트에는 최대 10^4개의 집이 있습니다. 또한 호출이 n단계 깊이까지 중첩되어 Python의 기본 제한인 1000을 초과합니다.
알고리즘
- 처음
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[k]는 처음 k개의 집에서 가져갈 수 있는 최대 금액입니다. 점화식: best[k] = max(best[k-1], best[k-2] + nums[k-1]): 집 k-1을 건너뛰거나, 이웃 집보다 앞에서 끝나는 최대 금액에 해당 집의 금액을 더해 가져갑니다. 기저 사례: best[0] = 0 및 best[1] = nums[0]. 순서: 각 항목이 그 앞의 두 항목을 참조하므로 k를 2부터 n까지 늘려 갑니다.
[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]두 개의 누계
핵심 아이디어
표의 각 항목은 바로 앞의 두 항목만 읽습니다. best[k]를 알고 나면 best[k-2]는 더 이상 읽지 않습니다. 따라서 표 대신 두 개의 숫자를 유지하면 됩니다. twoBack은 두 집 전까지의 최댓값이고, oneBack은 이전 집까지의 최댓값입니다.
x를 보유한 집에서 새로운 최댓값은 max(oneBack, twoBack + x)입니다. 그런 다음 값을 이동합니다. twoBack에는 이전 oneBack 값을 넣고, oneBack에는 새로운 최댓값을 넣습니다. 둘 다 첫 번째 집 이전의 빈 거리를 나타내는 0에서 시작하므로, 첫 번째 집에 대한 특별 처리가 필요하지 않습니다. 그 집의 최댓값은 max(0, 0 + nums[0])입니다.
[5, 3, 4, 11, 2]에서 쌍은 (0, 0), (0, 5), (5, 5), (5, 9), (9, 16), (16, 16)으로 바뀌고, oneBack은 16으로 끝납니다. 연산량은 표를 사용하는 경우와 같은 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
함정과 경계 사례
대부분의 오답은 입력이 작을 때만 통하는 지름길을 쓰거나, 두 합계를 잘못된 순서로 갱신해서 발생합니다.
- 짝수 번째 집과 홀수 번째 집의 금액을 각각 합산한 다음 더 큰 값을 고르면 두 집을 연달아 건너뛰는 선택을 놓치게 됩니다.
[10, 1, 1, 10]에서는 두 합계가 모두 11이지만, 0번 집과 3번 집을 선택하면 20입니다. - 가장 돈이 많은 집을 먼저 선택하면
[3, 4, 3]에서 실패합니다. 4를 선택하면 양쪽의 3을 모두 건너뛰게 되는데, 두 3의 합은 6입니다. oneBack을twoBack에 복사하기 전에 덮어쓰면 다음 집에서 필요한 값을 잃게 됩니다. 먼저 새로운 최댓값을 계산한 다음 값을 이동하거나, 언어에서 허용하는 경우 두 값을 한 번에 할당하세요.nums[1]을 읽거나 미리best[1]과best[2]를 설정하면 집이 하나뿐인 거리에서 오류가 발생합니다. 두 합계를 모두 0으로 시작하면 특별한 경우 처리가 필요 없습니다.- Lua와 R에서는 배열이 1부터 시작하므로,
k-1번 집의 금액은nums[k]입니다.
자주 묻는 질문4
House Robber의 점화식은 무엇인가요?
처음 k개의 집에서 얻을 수 있는 최댓값은 max(best[k-1], best[k-2] + nums[k-1])입니다. k-1번째 집을 건너뛰고 그 이전 집들에서 얻은 최댓값을 유지하거나, k-1번째 집을 선택해 이웃 집보다 앞에서 끝나는 최댓값에 더하면 됩니다. 기본 사례는 집이 없을 때 0이고, 집이 하나일 때 nums[0]입니다.
House Robber의 시간 및 공간 복잡도는 무엇인가요?
동적 프로그래밍 솔루션은 각 집을 한 번씩 살펴보므로 O(n) 시간이 걸립니다. 전체 테이블을 사용하면 O(n) 공간이 필요하지만, 마지막 두 합계만 유지하면 O(1)로 줄어듭니다. 답을 저장하지 않는 단순 재귀는 약 1.6^n번 호출되므로 지수 시간이 걸립니다.
왜 한 집씩 건너뛰며 털면 House Robber 문제가 해결되지 않을까요?
최선의 계획은 때때로 연속해서 두 집을 건너뜁니다. [10, 1, 1, 10]에서는 짝수 번째 집과 홀수 번째 집의 합이 모두 11인 반면, 첫 번째 집과 마지막 집을 선택하면 20이 됩니다. 동적 프로그래밍은 각 집에서 건너뛰는 경우와 선택하는 경우를 비교하므로 이러한 계획을 찾아냅니다.
집들이 원형으로 배치되어 있을 때 House Robber 문제는 어떻게 해결하나요?
원형에서는 첫 번째 집과 마지막 집이 이웃이므로, 계획에는 둘 중 최대 하나만 포함할 수 있습니다. 직선 거리 문제의 해결 방법을 두 번 실행하세요. 한 번은 마지막 집을 제외하고, 한 번은 첫 번째 집을 제외한 다음, 더 큰 결과를 반환하세요. 집이 하나뿐인 거리는 한 가지 특별한 경우입니다. 정답은 그 집입니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def rob(nums):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
nums = [5, 3, 4, 11, 2]
기대값
16