-
-
다이내믹 프로그래밍 완전 정복 - 빠르고 우아한 상향식 문제 풀이법
미나크시.카말 라와트 지음, 박상은 옮김 / 한빛미디어 / 2019년 10월
평점 :
나름대로 꾸준히 알고리즘 문제를 풀기는 하지만, 항상 어려운 부분이 있는데 그 중 하나가 DP, dynamic programming이다. 밀접한 관계에 있는 재귀는 비교적 쉬운데 왜 DP는 항상 어려운지 잘 모르겠는데(아마 노력이 부족해서겠지) 이번에 그걸 보완할만한 책이 있어 읽어보게 되었다. 책을 읽으면서 나름대로 연습을 해서 그런지 읽고 난 후 약간 DP에 대한 자신감이 생기는 느낌이다. 실제 문제를 풀어봐야 확실해지겠지만. 개인적인 연습 코드는 python3로 작성했다.
Chapter 1
완전히 초보자를 위한 재귀에 대한 소개. 재귀 자체에 대한 이해도 필요하지만, 메모리 내부에서 재귀 호출이 어떻게 메모리를 할당하고 해제하는지 컴퓨터 구조의 측면에서 이해하는 부분도 중요하다는 점을 알려준다.
Chapter 2
재귀 호출에 대해 좀 더 설명을 한다. 우선 피보나치 수열과 matrix를 이용해 범위를 줄여 계산하는 종류의 문제가 재귀와 DP에 적합하다는 점을 설명한다. 그 다음으로 메모 전략(memoization)을 설명하는 데 이해하고 사용하기는 쉽지만 이것만으로도 인터뷰에서 꽤 쓸만한 성과를 낼 수 있기 때문에(특히 온라인 문제 풀이의 경우) 혹시라도 몰랐다면 매우 유용한 방법이다.
# p68, 역 사이 최소 비용 구하기
def minCost(cost, s, d):
if d == s:
return 0
if d - s == 1:
return cost[s][d]
minRes = cost[s][d]
for i in range(s + 1, d):
minRes = min(minCost(cost, s, i) + minCost(cost, i, d), minRes)
return minRes
Chapter 3
드디어 DP이다. 앞서 살펴봤던 피보나치 수열과 matrix를 이용해 역간 이동 비용을 계산하는 문제를 DP로 해결하면 시간 복잡도가 줄어든다는 걸 설명한다. 그리고 부분 문자열 문제를 이용해 본격적인 설명을 한다. 재귀와 DP의 차이는 하향식이냐 상향식이냐의 차이인데, 이걸 피보나치 수열을 통해 더 자세히 설명한다. 아마 이 부분이 이 책에서 가장 중요하지 않을까 싶은데(최소한 나에게는 그렇다), 재귀와 비슷하면서도 차이가 있는 부분을 인식해야 각각에 알맞은 방법을 찾을 수 있기 때문이다. 마지막으로 드물지만 상향식 프로그래밍(DP)가 하향식에 비해 덜 효율적인 경우에 대해 설명하고 이번 장을 마친다.
# p89, 부분 문자열 다루기
class Solution:
# recursive
def maxEqualSumLen0(self, s: str) -> int:
if s is None or 0 == len(s):
return 0def getMaxEqualSumLen(l):
m = len(l) // 2
if sum(l[:m]) == sum(l[m:]):
return 2 * m
return max(getMaxEqualSumLen(l[2:]), getMaxEqualSumLen(l[1:-1]), getMaxEqualSumLen(l[:-2]))l = list(int(c) for c in s)
if len(l) % 2 == 0:
return getMaxEqualSumLen(l)
return max(getMaxEqualSumLen(l[:-1]), getMaxEqualSumLen(l[1:]))
Chapter 4
DP에 익숙해지기 위해 재귀, 메모, DP의 세 가지 방법을 한 가지 문제(2 * 2 matrix에서 최소 비용으로 이동하기)에 대해 설명하고 예제를 소개한다. 이어서 3가지 예제를 통해 DP에 대해 더 설명하는데, 책에도 나와있듯이 실제 면접에서 사용될만한 난이도의 문제들이라 아주 좋은 연습이 된다.
# p105, 행렬에서 최소 이동 비용 구하기
class Solution:
def minCost(self, grid: List[List[int]]) -> int:
if grid is None or 0 == len(grid) or 0 == len(grid[0]):
return 0R, C = len(grid), len(grid[0])
cost = [[0] * C for _ in range(R)]
cost[0][0] = grid[0][0]
for r in range(1, R):
cost[r][0] = cost[r - 1][0] + grid[r][0]
for c in range(1, C):
cost[0][c] = cost[0][c - 1] + grid[0][c]
for r in range(1, R):
for c in range(1, C):
cost[r][c] = min(cost[r - 1][c], cost[r][c - 1]) + grid[r][c]
return cost[-1][-1]# p120, 특정 점수에 도달하는 경우의 수 구하기
class Solution:
def countWaysRecur(self, num):
if num == 0:
return 0def count(n):
if 0 == n:
return 1
if n < 3:
return 0
cnt = 0
for c in [3, 5, 10]:
if c <= n:
cnt += count(n - c)
return cntreturn count(num)def countWaysDP(self, num):
if num == 0:
return 0dp = [0] * (num + 1)
dp[0] = 1
for i in range(1, len(dp)):
for c in [3, 5, 10]:
if c <= i:
dp[i] += dp[i - c]
return dp[-1]# p122, 연속된 부분 배열의 최댓값 구하기
class Solution:
def maxSubSumArray(self, arr: List[int]) -> int:
if arr is None or 0 == len(arr):
return 0
if 1 == len(arr):
return arr[0]
maxSum, subSum = 0, [0] * len(arr)
for i, a in enumerate(arr):
curSum = subSum[i - 1] + a
if curSum <= 0:
continue
subSum[i] = curSum
maxSum = max(maxSum, curSum)
return maxSum
Chapter 5
여러가지 문제를 통해 DP에 익숙해지는 연습이다. 문제 풀이 연습 사이트들에서 볼 수 있는, 면접에 나올 가능성이 있는 문제들이다. 개인적으로는 마지막 문제가 가장 기억에 남는데, 수년 전 가고 싶던 회사에서 저 문제를 못 풀어서 떨어졌던 기억이 나기 때문이다. 당시에는 영어 설명부터가 머리에 들어오지 않아 DP 문제라는 생각조차 못했다. 여러 문제 풀이 연습 사이트에서 세부 주제별 문제 분류를 제공하니(i.e. https://leetcode.com/tag/dynamic-programming/) 추가로 연습을 진행하면 더 좋을 것이다.
# p130, 최소 교정 비용 문제
class Solution:
def minEditNum(self, s1: str, s2: str) -> int:
if (s1 is None or 0 == len(s1)) and (s2 is None or 0 == len(s2)):
return 0
if s1 is None or 0 == len(s1):
return len(s2)
if s2 is None or 0 == len(s2):
return len(s1)R, C = len(s1), len(s2)
grid = [[0] * (C + 1) for _ in range(R + 1)]
for r in range(1, R + 1):
for c in range(1, C + 1):
if s1[r - 1] == s2[c - 1]:
grid[r][c] = 1 + grid[r - 1][c - 1]
else:
grid[r][c] = max(grid[r - 1][c], grid[r][c - 1])
return max(R, C) - grid[-1][-1]# p152, 부분집합의 합 구하기
class Solution:
def minEditNum(self, s1: str, s2: str) -> int:
if (s1 is None or 0 == len(s1)) and (s2 is None or 0 == len(s2)):
return 0
if s1 is None or 0 == len(s1):
return len(s2)
if s2 is None or 0 == len(s2):
return len(s1)R, C = len(s1), len(s2)
grid = [[0] * (C + 1) for _ in range(R + 1)]
for r in range(1, R + 1):
for c in range(1, C + 1):
if s1[r - 1] == s2[c - 1]:
grid[r][c] = 1 + grid[r - 1][c - 1]
else:
grid[r][c] = max(grid[r - 1][c], grid[r][c - 1])
return max(R, C) - grid[-1][-1]# p171, 거스름돈 최적화
class Solution:
def minCoins(self, coins: List[int], money: int) -> int:
if coins is None or 0 == len(coins):
return 0dp = [float('inf')] * (money + 1)
dp[0] = 0
for m in range(1, money + 1):
for coin in coins:
if m < coin:
continue
elif m == coin:
dp[m] = 1
else:
if dp[m - coin] > 0:
dp[m] = min(dp[m], 1 + dp[m - coin])
return dp[-1]# p176, 철근 자르기
class Solution:
def maxProfitRecur(self, costs: List[int], length: int) -> int:
if costs is None or 0 == len(costs):
return 0def getMaxProfit(acc, _costs, _length):
if _length == 0:
return acc
if _length < 0:
return 0
subProfit = 0
for rodLen, cost in _costs:
if rodLen > _length:
continue
acc += cost
curProfit = getMaxProfit(acc, _costs, _length - rodLen)
subProfit = max(subProfit, curProfit)
acc -= cost
return subProfitreturn getMaxProfit(0, [(i + 1, cost) for i, cost in enumerate(costs)], length)def maxProfit(self, costs: List[int], length: int) -> int:
if costs is None or 0 == len(costs):
return 0dp = [[0, 0]] * (length + 1)
dp[0] = [0, 0]
for d in range(1, length + 1):
for i, cost in enumerate(costs):
rodLen = i + 1
if d < rodLen:
continue
candCost = dp[d - rodLen][1] + cost
if dp[d][1] < candCost:
dp[d] = [dp[d - rodLen][0] + 1, candCost]
return dp[-1][1]# p187, 최장 회문 부분 수열의 길이
class Solution:
def maxPalindromeLen(self, s: str) -> int:
if s is None or 0 == len(s):
return 0R = C = len(s)
rStr, grid = s[::-1], [[0] * (C + 1) for _ in range(R + 1)]
for r in range(1, R + 1):
for c in range(1, C + 1):
if s[c - 1] == rStr[r - 1]:
grid[r][c] = 1 + grid[r - 1][c - 1]
else:
grid[r][c] = max(grid[r - 1][c], grid[r][c - 1])
return grid[-1][-1]
한국어판 부록 A
알고리즘 서적에는 항상 빠지지 않는 시간/공간 복잡도에 대해 간단히 소개한다. 간단한 소개에 그치기 때문에 자세한 내용은 자료구조/알고리즘 교과서를 보는 게 좋다
한국어판 부록 B
codility 사용 방법을 소개한다. 많은 회사들이 면접 시 1차로 리크루터와 통화를 한 후 두 번째 단계로 이런 문제 풀이 사이트에서 문제를 풀고 제출하게 하는데, codility나 hackerrank가 가장 유명한 편이다. 우리나라에서도 점점 많은 회사들이 도입하고 있기 때문에 시간 날 때마다 풀어보면서 익숙해지는 게 좋다.
소소한 장점
원서는 c source인데 역자가 python으로 옮겨놓았다 https://github.com/crapas/dp
중간중간 박스를 통해 실제 인터뷰에서 유용할 팁을 알려주는 경우가 있다. 원서 제목 자체가 Dynamic Programming for Coding Interviews이니 적절한 설명이라고 생각한다.
소소한 단점
(리디북스 한정) 역시나 매번 그렇듯 옮긴이의 말에 있는 링크는 정상 동작하지 않는다. 사소한 버그이지만 리디북스의 프로그래밍 책을 읽는다는 특성상 컴퓨터에서 읽는 경우가 많은데 링크가 동작하지 않으면 불편하다.
Site