[파이썬 알고리즘 인터뷰] 다이나믹 프로그래밍

• 다이나믹 프로그래밍: 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘
  • 최적 부분 구조: 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성
    • 대부분의 재귀 알고리즘은 최적 부분 구조 문제를 풀 수 있음
  • 중복된 하위 문제들의 결과를 저장해뒀다가 풀이해나감

알고리즘	풀이 가능한 문제들의 특징	풀이 가능한 문제 및 알고리즘
다이나믹 프로그래밍	- 최적 부분 구조 - 중복된 하위 문제들	- 0-1 배낭 문제 - 피보나치 수열 - 다익스트라 알고리즘
그리디 알고리즘	- 최적 부분 구조 - 탐욕 선택 속성	- 분할 가능 배낭 문제 - 다익스트라 알고리즘
분할 정복	- 최적 부분 구조	- 병합 정렬 - 퀵 정렬
다익스트라 알고리즘	- 최적 부분 구조 - 중복된 하위 문제들 - 탐욕 선택 속성	- 최단 경로 문제

• 최적 부분 구조

최단 경로를 찾는 최적 부분 구조 문제

• [A -> B 최단 경로] + [B -> C 최단 경로] == [A -> C 최단 경로]
  • 부분 문제의 답을 조합하여 전체 문제의 답 도출
• 분할 정복으로 풀이 가능하며, DP나 그리디로 접근해볼 수 있는 후보 문제가 된다
• 만약 A -> C로 한번에 가는 길이 생긴다면 더 이상 최적 부분 구조가 아니게 된다

 

• 중복된 하위 문제들
  • 예) 피보나치 수열
  • f(5) = f(4) + f(3), f(4) = f(3) + f(2), f(3) = f(2) + f(1)
  • 하위 문제들끼리 중복되는 지점들이 있음
• 다이나믹 프로그래밍 방법론
  • 패러다임: 중복된 하위 문제들 + 최적 부분 구조 -> 분할 정복
  • 방법론: 메모이제이션(하향식) or 타뷸레이션(상향식)
    • 상향식: 더 작은 하위 문제부터 본 다음, 작은 문제의 정답을 이용해 큰 문제의 정답을 풀어나감
      • 일반적으로 이 방식만을 DP로 지칭하기도 함
    • 하향식: 하위 문제에 대한 정답을 계산했는지 확인해가며 문제를 자연스럽게 재귀로 풀어나감

# 상향식
def fib(n):
    dp[0] = 0
    dp[1] = 1
    
    for i in range(2, n + 1):
    	dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]
    
# 하향식
def fib(n):
    if n <= 1:
        return n
        
    if dp[n]:
    	return dp[n]
    dp[n] = fib(n - 1) + fib(n - 2)
    return dp[n]

 

509. Fibonacci Number

- 재귀 브루트 포스

- 메모이제이션

- 타뷸레이션

- 두 변수만 이용해 x, y = y, x + y 로 반복 다중 할당

- (numpy모듈로 행렬 활용)

- 내 풀이: defaultdict 대신 리스트 활용하고, 재귀로 풀 때 fib()를 직접 리턴하여 느려짐

 

• 0-1 배낭 문제 (짐을 쪼갤 수 없음)
  • 짐을 쪼갤 수 있을 때는 그리디하게 단가 순으로 배치하여 풀이했었음
  • 짐을 쪼개지 못하므로 모든 경우의 수를 계산해야하며, 이때 DP가 굉장히 유용함
  • 타뷸레이션: 그 위치까지의 짐 개수와 배낭의 용량에 따른 최댓값을 상향식으로 반복 축적해 최종 답안 계산
    • 예) 짐(4) x 용량(4) 일때 최댓값 10 -> 짐(4) x 용량(5) 일때 최댓값 12 -> ...

53. Maximum Subarray

- 메모이제이션 -> 앞에서부터 순회하며 누적합 계산하되, 0이하가 되는 지점이 생기면 그 다음 숫자부터 새로 계산

-> 각 요소까지의 누적합 값이 그 지점까지의 서브 배열 중 최대 합을 가지는 배열의 합

- 카데인 알고리즘 -> 위와 같은 방식이지만 리스트에 누적합을 일일히 저장하고 max()하는 것이 아니라, 각 단계마다 누적합과 그 전 단계까지의 최댓값 비교

 

70. Climbing Stairs

- 재귀 구조 브루트 포스 -> 피보나치와 동일

- 메모이제이션 -> 피보나치와 동일

- 내 풀이: 두 변수로 피보나치와 동일하게

 

198. House Robber

- 재귀 구조 브루트 포스

- 타뷸레이션

* 딕셔너리 메소드: pop(), popitem(), update()

• 파이썬 3.7+ 에서만 딕셔너리가 자동 정렬되므로, 코테에서는 필요시 OrderedDict()를 사용하기!

n과 n-1, n-2 사이의 관계

# 리트코드 다른 답안
class Solution:
    def rob(self, nums: List[int]) -> int:
        prev1 = 0
        prev2 = 0
        for i in range(0, len(nums)):
            prev1, prev2 = max(prev1, prev2+nums[i]), prev1
        return prev1
# 두 변수에 계속 축적