다이나믹 프로그래밍
들어가기 전에
다이나믹 프로그래밍 알고리즘은 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘이다. 분할 정복 알고리즘과 차이점이라면 다이나믹 프로그래밍은 하위 문제들이 중복 된다는 점이다. 다이나믹 프로그래밍의 방법론은 다음과 같이 두가지로 구분된다.
- 상향식(타뷸레이션): 작은 하위 문제부터 차례로 정답을 풀어나간다.
- 하향식(메모이제이션): 하위 문제에 대한 정답을 계산했는지 확인해가며 재귀 방법으로 풀어나간다.
다이나믹 프로그래밍은 접근 방법이 매우 어렵고 난이도가 지나치게 높기 때문에 코딩 테스트에는 가급적 나오지 않는다.
Question 85: 피보나치 수열
내 풀이
class Solution:
def fib(self, n: int) -> int:
if n<2:
return n
f = [0,1]
for num in range(1,n):
f.append(f[num] + f[num-1])
return f[-1]
결과
Runtime: 65 ms, faster than 31.29% of Python3 online submissions for Fibonacci Number. Memory Usage: 14 MB, less than 10.48% of Python3 online submissions for Fibonacci Number.
풀이 1: 재귀 구조 브루트 포스
class Solution:
def fib(self, n: int) -> int:
if n<=1:
return n
return self.fib(n-1) + self.fib(n-2)
중요 내용
- 중복된 계산을 계속 해나가므로 시간 초과 에러가 뜬다.
풀이 2: 메모이제이션
class Solution:
dp = collections.defaultdict(int)
def fib(self, n: int) -> int:
if n <= 1:
return n
if self.dp[n]:
return self.dp[n]
self.dp[n] = self.fib(n-1) + self.fib(n-2)
return self.dp[n]
중요 내용
- 이미 계산한 값은 dp 딕셔너리에 넣음으로써 중복된 계산은 하지 않는다.
풀이 3: 타뷸레이션
class Solution:
dp = collections.defaultdict(int)
def fib(self, n: int) -> int:
self.dp[0] = 0
self.dp[1] = 1
for i in range(2, n+1):
self.dp[i] = self.dp[i-1] + self.dp[i-2]
return self.dp[n]
중요 내용
- 재귀를 사용하지 않고 반복문으로 풀었다.
- 내 풀이 방법과 비슷하나 딕셔너리를 지정한 뒤 푸는 것에 차이가 있다.
풀이 4: 두 변수만 이용해 공간 절약
class Solution:
def fib(self, n: int) -> int:
x, y = 0, 1
for i in range(0, n):
x, y = y, x + y
return x
중요 내용
- 공간복잡도가 O(n)에서 O(1)로 줄어든다.
풀이 5: 행렬
class Solution:
def fib(self, n: int) -> int:
M = np.matrix([[0, 1], [1, 1]])
vec = np.matrix([[0],[1]])
return np.matmul(M ** n, vec)[0]
중요 내용
- O(log n)번의 연산 만으로 구할 수 있다.
Question 86: 최대 서브 배열
합이 최대가 되는 연속 서브 배열을 찾아 합을 리턴하라.
입력: nums = [-2,1,-3,4,-1,2,1,-5,4]
출력: 6
풀이 1: 메모이제이션
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
for i in range(1, len(nums)):
nums[i] += nums[i - 1] if nums[i - 1] > 0 else 0
return max(nums)
중요 내용
- 이전 값과 계속 더해 나가면서 최대값을 리턴한다.
- 이전 값을 더했을때 0보다 작으면 그 값을 배열에 포함할 필요가 없으므로 0보다 클때만 더한다.
풀이 2: 카데인 알고리즘
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
best_sum = -sys.maxsize
current_sum = 0
for num in nums:
current_sum = max(num, current_sum + num)
best_sum = max(best_sum, current_sum)
return best_sum
중요 내용
- $O(n^2)$ 만큼 걸리던 시간 복잡도를 $O(n)$ 만큼 줄일 수 있다.
Question 87: 계단 오르기
정상에 도달하기 위해 n 계단을 올라야 한다. 매번 각각 1계단 또는 2계단씩 오를 수 있다면 정상에 도달하기 위한 방법은 몇가지 경로가 되는지 계산하라.
입력: 3
출력: 3
내 풀이
class Solution:
dp = collections.defaultdict(int)
def climbStairs(self, n: int) -> int:
if n <= 2:
return n
if self.dp[n]:
return self.dp[n]
self.dp[n] = self.climbStairs(n-1) + self.climbStairs(n-2)
return self.dp[n]
- 피보나치 수열과 같은 알고리즘이다.
피보나치 수열과 같은 방법을 사용했으므로 자세한 내용은 생략하도록 하겠다.
Question 88: 집 도둑
어느 집에서든 돈을 훔쳐올 수 있지만 경보 시스템 때문에 바로 옆집은 훔칠 수 없고 한 칸 이상 떨어진 집만 가능하다. 각 집에서는 훔칠 수 있는 돈의 액수가 입력값으로 표기되어 있다. 훔칠 수 있는 가장 큰 금액을 출력하라.
입력: [2,7,9,3,1]
출력: 12
내 풀이
class Solution:
dp = collections.defaultdict(int)
def rob(self, nums: List[int]) -> int:
num_len = len(nums)
if self.dp[num_len]:
return self.dp[num_len]
if nums[2:]:
self.dp[num_len] = max(self.rob(nums[1:]), self.rob(nums[2:]) + nums[0])
return self.dp[num_len]
elif nums[1:]:
self.dp[num_len] = max(nums[0], nums[1])
return self.dp[num_len]
else:
self.dp[num_len] = nums[0]
return self.dp[num_len]
풀이 1: 재귀 구조 브루트 포스
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)
중요 내용
- 시작을 len(nums)-1 에서 했다는 것만 제외하면 내 풀이 방법과 비슷하다.
- 타임아웃으로 풀리지 않는다.
풀이 2: 타뷸레이션
class Solution:
def maxSubArray(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])
return dp.popitem()[1]
중요 내용
- for 문으로 풀이하였다.
- 해시 테이블은 입력 순서가 유지되지 않는다!
- OrderedDict는 입력 순서를 유지하는 딕셔너리이다.
Comments