LeetCode · Dynamic Programming · Python
LeetCode House Robber 파이썬 풀이
오늘은 DP 입문 문제로 자주 등장하는 House Robber를 정리해보겠습니다. 단순히 정답 코드만 보는 것이 아니라, 왜 이 문제가 DP인지, 어떻게 값이 쌓이는지 시각적으로, 그리고 코드가 실제로 한 줄씩 무슨 역할을 하는지까지 한 번에 이해할 수 있도록 구성했습니다.
핵심 요약
- 서로 붙어 있는 집은 동시에 털 수 없습니다.
- 각 위치에서 현재 집을 털지 / 털지 않을지 비교합니다.
- 점화식은 dp[i] = max(dp[i-1], dp[i-2] + nums[i]) 입니다.
- 이번 글에는 시각화와 코드 한 줄 한 줄 해설도 포함했습니다.
- 시간 복잡도는 O(n), 공간 복잡도는 O(n) 입니다.
1. 문제 설명
도둑이 일렬로 놓인 여러 집을 털려고 합니다. 그런데 인접한 두 집을 연속으로 털면 경보가 울립니다. 따라서 서로 붙어 있는 집은 동시에 선택할 수 없고, 털 수 있는 금액의 합이 최대가 되도록 선택해야 합니다.
예를 들어 nums = [2, 7, 9, 3, 1] 이라면,
7과 9는 서로 붙어 있으므로 동시에 선택할 수 없습니다.
최적 선택은 2 + 9 + 1 = 12 입니다.
2. 왜 DP로 풀어야 할까?
이 문제는 매 집마다 아래 두 선택 중 하나를 해야 합니다.
- 현재 집을 털지 않는다. → 바로 이전 집까지의 최대 금액을 그대로 가져옵니다.
- 현재 집을 턴다. → 바로 이전 집은 못 터니까, i-2번째 집까지의 최대 금액 + 현재 집 금액을 더합니다.
즉 현재 선택이 이전 결과에 의존하기 때문에, 이전까지의 최적값을 저장하면서 진행하는 DP가 가장 자연스럽습니다.
3. 점화식 정리
dp[i] 를 i번째 집까지 고려했을 때 얻을 수 있는 최대 금액이라고 정의합니다.
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
- dp[i - 1] : 현재 집을 털지 않았을 때
- dp[i - 2] + nums[i] : 현재 집을 털었을 때
4. 시각화로 이해하기
말로만 보면 어렵기 때문에, 입력값 [2, 7, 9, 3, 1] 를 기준으로 흐름을 시각화해보겠습니다.
상태 전이 시각화
dp[0] = 2
→
dp[1] = max(2, 7) = 7
→
dp[2] = max(7, 2 + 9) = 11
dp[3] = max(11, 7 + 3) = 11
→
dp[4] = max(11, 11 + 1) = 12
→
최종 정답 = 12
포인트
집 2의 값 9가 커 보여도, 바로 앞 집 7과 함께 가져갈 수는 없습니다. 그래서 단순히 큰 숫자만 고르면 안 되고, 이전까지의 최적 결과를 저장해 비교해야 합니다.
5. 코드
Python
class Solution:
def rob(self, nums: List[int]) -> int:
# 집이 1개뿐이면 바로끝
if len(nums) == 1:
return nums[0]
# dp[i] = i번째 최대 돈
dp = [0] * len(nums)
# 첫 번째 집까지의 최대돈 미리 선정
dp[0] = nums[0]
# 두 번째 집까지의 최대값
dp[1] = max(nums[0], nums[1])
# 세 번째 집부터 끝까지 확인
for i in range(2, len(nums)):
# 안털면 전에거 최대값인걸로
rob_not = dp[i - 1]
# 현재집털기, (바로 전집은 못텀)
rob_n = dp[i - 2] + nums[i]
# 둘 중 더 큰 값 선택
dp[i] = max(rob_not, rob_n)
return dp[-1]
6. 코드 한 줄 한 줄 설명
아래에서는 실제 코드가 어떤 순서로 작동하는지 한 줄씩 나눠서 설명해보겠습니다.
| 라인 |
코드 |
설명 |
| 1 |
class Solution: |
리트코드에서 사용하는 클래스 선언입니다. |
| 2 |
def rob(self, nums: List[int]) -> int: |
정수 배열 nums를 입력받아 훔칠 수 있는 최대 금액을 반환하는 함수입니다. |
| 3 |
# 집이 1개뿐이면 바로끝 |
예외 상황을 설명하는 주석입니다. |
| 4 |
if len(nums) == 1: |
집이 하나뿐인 경우를 체크합니다. |
| 5 |
return nums[0] |
집이 하나면 그 집을 터는 것이 최댓값이므로 바로 반환합니다. |
| 6 |
# dp[i] = i번째 최대 돈 |
DP 배열의 의미를 적어둔 주석입니다. |
| 7 |
dp = [0] * len(nums) |
집 개수만큼 DP 배열을 만들고, 처음에는 0으로 채웁니다. |
| 8 |
# 첫 번째 집까지의 최대돈 미리 선정 |
첫 번째 초기값을 설명하는 주석입니다. |
| 9 |
dp[0] = nums[0] |
첫 번째 집까지만 본다면 선택지는 하나뿐이므로 그 값 그대로 저장합니다. |
| 10 |
# 두 번째 집까지의 최대값 |
두 번째 초기값을 설명하는 주석입니다. |
| 11 |
dp[1] = max(nums[0], nums[1]) |
첫 번째 집과 두 번째 집은 같이 못 터니, 둘 중 더 큰 값 하나를 선택합니다. |
| 12 |
# 세 번째 집부터 끝까지 확인 |
이제부터 점화식을 반복 적용하면 됩니다. |
| 13 |
for i in range(2, len(nums)): |
세 번째 집 인덱스인 2부터 마지막 집까지 순회합니다. |
| 14 |
# 안털면 전에거 최대값인걸로 |
현재 집을 털지 않는 경우를 설명합니다. |
| 15 |
rob_not = dp[i - 1] |
현재 집을 털지 않으면, 이전 집까지의 최대값을 그대로 가져오면 됩니다. |
| 16 |
# 현재집털기, (바로 전집은 못텀) |
현재 집을 터는 경우를 설명합니다. |
| 17 |
rob_n = dp[i - 2] + nums[i] |
현재 집을 턴다면 바로 전 집은 건너뛰어야 하므로, i-2번째까지의 최대값에 현재 금액을 더합니다. |
| 18 |
# 둘 중 더 큰 값 선택 |
이제 두 경우를 비교해서 최적값을 선택해야 합니다. |
| 19 |
dp[i] = max(rob_not, rob_n) |
현재 위치까지의 최대 금액을 DP 배열에 저장합니다. 이 한 줄이 핵심 점화식입니다. |
| 20 |
return dp[-1] |
마지막 집까지 모두 고려한 최대 금액을 반환합니다. |
7. 예시로 직접 따라가 보기
입력값이 [2, 7, 9, 3, 1] 일 때를 표로 다시 보면 더 명확합니다.
| i |
nums[i] |
털지 않을 때 |
털 때 |
dp[i] |
| 0 |
2 |
- |
2 |
2 |
| 1 |
7 |
2 |
7 |
7 |
| 2 |
9 |
7 |
2 + 9 = 11 |
11 |
| 3 |
3 |
11 |
7 + 3 = 10 |
11 |
| 4 |
1 |
11 |
11 + 1 = 12 |
12 |
8. 시간 복잡도와 공간 복잡도
- 시간 복잡도: O(n)
- 공간 복잡도: O(n)
배열을 한 번만 순회하므로 시간 복잡도는 O(n)입니다. 현재 코드는 DP 배열을 따로 사용하기 때문에 공간 복잡도는 O(n)입니다.
9. 공간 최적화 버전
사실 점화식 계산에는 직전 값과 직전의 직전 값만 있으면 됩니다. 그래서 배열 없이 변수 두 개만 사용해서도 풀 수 있습니다.
Python · 공간 최적화 버전
class Solution:
def rob(self, nums: List[int]) -> int:
prev2 = 0
prev1 = 0
for money in nums:
prev2, prev1 = prev1, max(prev1, prev2 + money)
return prev1
이 방식은 공간 복잡도를 O(1) 로 줄일 수 있습니다. 다만 블로그 글에서는 처음엔 DP 배열 버전으로 설명하는 편이 훨씬 이해하기 쉽습니다.
10. 마무리
House Robber 문제의 핵심은 결국 현재 집을 털지 않을 때와 현재 집을 털 때를 비교하는 것입니다. 이 비교를 반복해서 저장하면 자연스럽게 최적해가 완성됩니다.
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
한 줄 결론
House Robber는 인접한 집을 동시에 선택할 수 없다는 제약 때문에 DP가 필요한 문제이고, 현재 집을 털지 않을 때와 털 때를 비교하는 방식으로 풀면 깔끔하게 해결됩니다.