문제
당신은 전문털이범이다. 어느 집에서든 돈을 훔쳐올 수 있지만 경보 시스템 때문에 바로 옆집은 훔칠 수 없고 한 칸 이상 떨어진 집만 가능하다. 각 집에는 훔칠 수 있는 돈의 액수가 입력 값으로 표기되어 있다. 훔칠 수 있는 가장 큰 금액을 출력하라.
입력 : [1, 2, 3, 1]
출력: 4
설명
첫 번째 집에서 1, 세번째 집에서 3, 따라서 1 + 3 = 4
입력 : [2, 7, 9, 3, 1]
출력 : 12
설명
첫 번째 집에서 2, 세 번째 집에서 9, 다섯 번째 집에서 1, 따라서 2 + 9 + 1 = 12이다.
코드
"""
fixme. https://leetcode.com/problems/house-robber/
fixme. Q88. 집도둑
fixme. 당신은 전문털이범이다. 어느 집에서든 돈을 훔쳐올 수 있지만 경보 시스템 때문에
fixme. 바로 옆집은 훔칠 수 없고 한 칸 이상 떨어진 집만 가능하다.
fixme. 각 집에는 훔칠 수 있는 돈의 액수가 입력 값으로 표기되어 있다. 훔칠 수 있는 가장 큰 금액을 출력하라.
fixme. 입력 : [1, 2, 3, 1]
fixme. 출력 : 4
fixme. 설명
fixme. 첫 번째 집에서 1, 세번째 집에서 3, 따라서 1 + 3 = 4
fixme. 입력 : [2, 7, 9, 3, 1]
fixme. 출력 : 12
fixme. 설명
fixme. 첫 번째 집에서 2, 세 번째 집에서 9, 다섯 번째 집에서 1, 따라서 2 + 9 + 1 = 12이다.
"""
from typing import List
import collections
class Solution:
def rob(self, nums: List[int]) -> int:
def _rob(i: int) -> int:
if i < 0:
return 0
return max(_rob(i - 1), _rob(i - 2) + nums[i])
return _rob(len(nums) - 1)
def robDP(self, nums: List[int]) -> int:
if not nums:
return 0
if len(nums) <= 2:
return max(nums)
dp = collections.OrderedDict()
dp[0], dp[1] = nums[0], max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
print(dp)
return dp.popitem()[1]풀이
재귀 구조 브루트 포스
바로 옆집은 훔칠 수 없으니 현재 집과 옆집 숫자 중의 최댓값을 구하고, 한 집 건넛집과 현재 집의 합과 비교해서 더 큰 값을 구해나가는 식으로 풀어나간다. 이렇게 하면 피보나치 수열과 거의 유사하여 재귀로 풀 수 있다.
아래는 nums = [9,3,9,8], i = 3인 경우에 변수의 흐름이다.
이 풀이는 시간 제한으로 풀리지 않는다.
타뷸레이션
알고리즘은 동일하고, 이미 계산한 값을 dp에 저장한다.
원래 딕셔너리는 입력 순서가 유지되지 않았으나 파이썬 3.7+부터는 유지된다. 하지만 파이썬의 낮은 버전에서도 순서가 유지될 수 있도록 명시적으로 collections.OrderedDict()로 선언했다.
가장 마지막 값의 추출은 popitem()을 사용한다. 리스트의 pop()과 동일한 역할을 하는데, 딕셔너리에도 pop()이 있지만 반드시 키를 지정해야 하고 해당 키의 아이템을 추출하는 역할을 한다. 딕셔너리에서 가장 마지막 아이템을 추출하기 위해서는 popitem()을 사용해야 한다.
출처
파이썬 알고리즘 인터뷰 (글 : 박상길 그림 : 정진호) [책만]