[198. House Robber] (알고리즘)
DP
문제
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security systems connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given an integer array nums representing the amount of money of each house, return the maximum amount of money you can rob tonight without alerting the police.
Example 1:
Input: nums = [1,2,3,1] Output: 4 Explanation: Rob house 1 (money = 1) and then rob house 3 (money = 3). Total amount you can rob = 1 + 3 = 4.
Example 2:
Input: nums = [2,7,9,3,1] Output: 12 Explanation: Rob house 1 (money = 2), rob house 3 (money = 9) and rob house 5 (money = 1). Total amount you can rob = 2 + 9 + 1 = 12.
Constraints:
1 <= nums.length <= 1000 <= nums[i] <= 400
스스로 고민
접근법
- 뭔가 해커가 된 느낌
- 연속으로 집을 털면 안되고 한 다리 건너서 돈을 쓸어야 되는 상황
- 그냥 반복문으로 문제를 풀면 되지 않나 생각했는데 문제 난이도가 미디엄이라 고민된다.
- 일단 해보자!
의사코드
- 반복문으로 하나 걸러서 도둑질 시도
구현 코드
class Solution:
def rob(self, nums: List[int]) -> int:
money = 0
for i in range(len(nums)):
if i % 2 == 0:
money += nums[i]
return money
- 실패했다.
[1,2]이렇게 두 개 만 있을 경우 하나만 시도해야한다.- 해시맵으로 문제를 풀어야 되나? 생각했는데 생각해보니 bfs 형식으로 풀어야 될거 같았다.
- 왜냐하면 첫 번째 원소와 두 번째 원소를 비교 했을 때 큰 값을 훔쳐야 된다면 네 번째 혹은 전체 길이에서 가장 돈을 많이 담을 수 있는걸 선택해야한다.
- 그렇다면 홀 수로 시작할 때와 짝수로 시작할 때의 값을 각각 구한 다음 합을 비교해서 리턴하면 되지 않을까?
class Solution:
def rob(self, nums: List[int]) -> int:
money1 = 0
money2 = 0
money = 0
for i in range(len(nums)):
if i % 2 == 0:
money1 += nums[i]
else:
money2 += nums[i]
max_money = money1 if money1 >= money2 else money2
return max_money
- 삼항 연산자로 시도했는데 테스트 케이스에서 실패했다.
[2,1,1,2]이렇게 있을 경우 답은 4라고 나온다.- 그렇다면 단순 홀수 짝수가 아니라
- 걸리지 않은 선에서 최대 값을 뽑아와야 한다.
- 그렇다면 탐색이 들어가고 bfs 나 dfs 로 풀어야 된다고 생각했다.
- 아직 제일 못 하는 부분인데… 그래도 도전!
- 여태까지 경험한 바로는 탐색 문제를 풀 때는 먼저 좌표부터 만들어야 한다. (많이 발전했다!)
- 그럼 모든 경우의 수를 다 반복하면서 진행해야될거 같은데 맵을 어떻게 만들어야 되는지 생각해봤다.
- 문제가 풀리지 않아서 찾아보니까 해당 문제는 동적 프로그래밍으로 푸는 문제라고한다.
동적 프로그래밍이란?
동적 프로그래밍(Dynamic Programming, DP)은 컴퓨터 과학 및 알고리즘 분야에서 사용되는 알고리즘 설계 기법 중 하나다. 동적 프로그래밍은 큰 문제를 작은 하위 문제로 분할하고, 작은 하위 문제의 해결 방법을 저장하며, 이를 활용하여 전체 문제를 해결하는 기법이다. 주로 최적화 문제나 재귀적으로 해결하기 어려운 문제를 효율적으로 해결하기 위해 사용된다.
동적 프로그래밍의 핵심 아이디어는 다음과 같다:
- 작은 하위 문제의 해결: 큰 문제를 작은 하위 문제로 나눈다. 작은 하위 문제는 원래 문제와 유사하지만 더 작은 크기를 갖는다.
- 하위 문제의 해결 저장: 작은 하위 문제를 한 번 해결하면 그 해결 방법을 저장한다. 이를 통해 동일한 하위 문제를 여러 번 해결하지 않고도 효율적으로 문제를 해결할 수 있다.
- 상향식 접근: 작은 하위 문제의 해결을 토대로 큰 문제를 해결한다. 즉, 상향식으로 문제를 해결하는 방식이다.
동적 프로그래밍은 다음 두 가지 주요 접근 방식으로 나눌 수 있다:
- 탑다운(Top-Down) 동적 프로그래밍: 재귀적인 방식으로 문제를 해결하며, 메모이제이션(Memoization) 기술을 사용하여 중복 계산을 피한다. 이 방식은 일반적으로 재귀 함수를 사용하며, 문제를 작은 하위 문제로 분할하고 해결하는 과정에서 중복된 계산을 저장하고 재사용한다.
- 바텀업(Bottom-Up) 동적 프로그래밍: 작은 하위 문제부터 시작하여 큰 문제를 해결하는 방식이다. 일반적으로 반복문을 사용하여 작은 하위 문제부터 시작하여 큰 문제까지 차례로 해결한다. 이 방식은 상향식으로 문제를 해결하며, 메모리를 덜 사용하는 경우가 많다.
동적 프로그래밍은 다양한 문제 유형에 적용할 수 있으며, 예를 들어 최단 경로 찾기, 문자열 편집 거리 계산, 배낭 문제 등 다양한 최적화 문제를 해결하는 데 사용된다. DP를 사용하면 문제의 시간 복잡도를 효율적으로 개선할 수 있으며, 많은 알고리즘 및 컴퓨터 과학 분야에서 중요한 역할을 한다.
정리
- 동적프로그래밍의 알고리즘 문제의 활용도는
- 최단경로 찾기, 문자열 편집 거리 계산, 배낭문제 등이 있다.
- DP 개념을 머리에 탑재후 다시 적용해보자
다시 생각해보기
- 작은 하위 문제의 해결
- 연속해서 집을 털 수 없다
- 하위 문제의 해결 저장
- 연속해서 집을 털 수 없는 모든 경우의 수를 저장
- 상향식 접근
- 각 경우의 수의 합 중에 가장 큰 수를 찾는다.
적용해보기
graph = [0] * n
graph[0] = nums[0]
graph[1] = max(nums[0], nums[1])
for i in range(2, n):
graph[i] = max(graph[i-1], graph[i-2] + nums[i])
return graph[-1]
- 이렇게 코드를 만들 경우 총 nums에 대한 길이만큼 0으로 가득 찬 리스트를 만들 수 있다.
- 그 후에 처음에 graph의 첫 번째 요소는 nums에 첫 번째 시작 요소를 넣는다.
- 그 후 두 번째 부터는 nums의 첫 번째 요소와 두 번째 요소중에 큰 숫자를 넣는다.
- 반복문에서는 이전의 합 vs 현재의 합 중에 더 높은 숫자를 그 다음 graph에 넣는다.
- 위의 로직을 숫자를 대입해서 생각해본다면 아까 처럼
[2,1,1,2]이렇게 있을 경우graph[0]= 2,graph[1]은 2가 된다. - 반복문에서는
graph[2]값은graph[1]값과graph[0]+nums[2]의 값 중 큰 값을graph[2]에 넣는다.graph[1]= 2graph[0]+nums[2]= 3graph[2]= 3- 지금의 경우는 첫 번째에서 물건을 털고 두 번째 집은 건너 뛰고 세 번째 집을 털은 경우다
graph[2]= 3graph[1]+nums[2]= 4graph[3]= 4- 이렇게 하면
graph[2]의 경우의 수는 첫 번째 집과 세번 째 집을 털었던 상황이다. graph[3]의 상황은 첫 번째집과 네번째 집을 털은 상황이다.- 위에서 첫 번째 집과 두 번째 집중 돈 많은 집을 털은 상황으로 두 번쨰 집부터 시작하는 게 아닌 첫 번째 집을 털은 걸로 시작이 된다.
- 이렇게 하면
- 이렇게 graph 의 마지막 값의 최종 결과 값은 지금 값을 더할지 혹은 뛰어 넘을지가 계산이 되어 있으며 또한 각 경우의 수와 그에 대한 합을 업데이트 시킨 값이다.
- 하지만 또 오류가 생겼다.
nums의 값이[0]만 있는상황- 그럼 문제에서 아예 없는 상황 이렇게 두 가지 예외 상황만 적용해서 문제를 풀면 될 것 같았다.
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
n = len(nums)
if n == 1:
return nums[0]
graph = [0] * n
graph[0] = nums[0]
graph[1] = max(nums[0], nums[1])
for i in range(2, n):
graph[i] = max(graph[i-1], graph[i-2] + nums[i])
return graph[-1]
시간 복잡도와 공간 복잡도
시간 복잡도: 이 코드의 시간 복잡도는 O(n) 다. 배열 nums의 길이를 n이라고 했을 때, 반복문을 통해 각 집을 한 번씩만 방문하므로 선형 시간에 문제를 해결한다.
공간 복잡도: 이 코드의 공간 복잡도는 O(n)다. graph 배열을 생성하여 각 집마다 최대로 훔칠 수 있는 금액을 저장하기 때문에 입력 배열 nums와 동일한 크기의 배열이 필요하다.
회고 과정
- 모르는 게 아직도 너무 많다.
- DP 라는 개념을 처음 알았다.
지금 코드에서 뭘 개선할 수 있지?
- 다른 사람의 코드를 보면서 뭘 더 개선하고 뭐가 다르고 어떤 접근 방식이 있는 지 알아보는 게 효율적이라고 생각했다.
다른 사람 코드를 보고 그 기준으로 어떤 부분을 개선 할 수 있는지 최종 회고
class Solution:
def rob(self, nums: List[int]) -> int:
# EXAMPLE - nums:, ANSWER:
rob1,rob2 = 0,0
for n in nums:
tmp = max(rob1 + n, rob2)
rob1 = rob2
rob2 = tmp
return rob2
- 코드를 보면 원리는 같지만 코드 가독성이라든지 성능도 더 좋고 간결하다
- 이 사람은 어떤 생각을 했길래 이런 코드를 만들었을까?
- 빙의를 해보자
- 도둑 군단 2개를 만들어서 비교해보자
- 첫 번째 도둑이 처음에 돈을 훔쳤을 경우와 현재 두 번째 도둑의 훔쳤던 돈의 양을 비교해서 가장 큰 값을 tmp로 기록한다.
- 두 번째 도둑이 훔친 돈을 첫 번째 도둑에게 준다.
- 이전에 tmp 값을 두 번째 도둑에게 다시 준다.
- 그럼 두 번째 돈을 훔치려는 시도를 할 때 첫 번째 도둑이 갖고 있던 돈은 두 번째 도둑이 이전에 갖고 있던 돈이고 여기서 두 번째 집을 털어본다.
- 두 번째 도둑은 이전에 첫 번째 도둑이 갖고 있던 돈이다.
- 뭔가 글로 설명하니까 복잡하니 시각화를 해보았다.
-
- 이런 식으로 rob 1은 tmp 라는 은행에 돈을 맡기면
- rob 2는 은행에서 돈을 찾는다.
- rob 1은 연속으로 다음 집을 턴다.
- 연속으로 털고 그럼 안되지 않나?
- 상관 없다!! 왜냐하면 rob1은 rob2의 값으로 업데이트 되서 실질적으로 첫 번째 집만 털은 상태고 3번째의 반복문에서는 실질적으로 1번과 3번 이렇게 건너서 집을 털은 상황이 된다.
- 실질적으로 1번과 2번이 같이 터는 상황이 일어나지 않음
- rob2는 첫 번째 집과 세 번째집 혹은 첫 번째 집과 네 번째 집 혹은 두 번째 집과 네 번째 집 중 가장 큰 값으로 자동 업데이트된다.
- 또한 집이 2개만 있는 경우도 결국 rob 1과 rob 2는 한 개의 집만 털은 상태이므로 문제가 없다.
- 솔직히 지금의 나로서는 시간을 아무리 많이 줘도 이렇게 생각을 못 할 것 같다.
- 현실적으로 극복할 수 있는 방향은 이렇게 문제를 계속 풀면서 다른 사람의 사고방식을 주입하는 거 말고는 없는 것 같다.
- 아 이렇게도 푸는구나 라는 유형을 많이 접해야만 사고의 폭을 강제로 넓힐 수 있을 것 같다고 생각했다.
댓글남기기