다이나믹 프로그래밍 (Python Algorithm Interview 23장)

algorithm

파이썬 알고리즘 인터뷰 23장을 정리한 내용입니다.

다이나믹프로그래밍

  • 다이나믹프로그래밍 알고리즘은 문제를 각각의 작은 문제로 나누어 해결한 결과를 저장해뒀다가 나중에 큰 문제의 결과와 합하여 풀이하는 알고리즘이다
  • 다이나믹 프로그래밍을 이용해 문제의 최적 해결 방법이 부분 문제에 대한 최적 해결 방법으로 구성되는 경우의 문제를 풀이할 수 있다
  • 순간 최적을 선택하는 그리디 알고리즘과 많이 비교되며 다이타믹 프로그래밍은 중복된 하위 문제들의 결과를 저장했다가 풀이한다는 차이가 있다

최적 부분 구조

스크린샷, 2021-09-29 17-58-34.png

  • 서울에서 부산까지 가는 최단 경로를 찾는 간단한 예이다
  • 서울에서 대구까지는 3가지의 경로가 있고 부산까지도 3가지의 경로를 가지고 있다
  • 서울에서 부산까지의 최단 경로는 $200km + 80km=280km$이다
  • 위 경로는 서울에서 대구까지 가는 최단경로(200km)와 대구에서 부산까지 가는 최단 경로(80km)로 구성된다
  • 서울에서 부산까지의 최단 경로는 (1)서울에서 대구까지 최단경로 (2)대구에서 부산까지 최단경로 두가지 부분 문제의 해답의 합이된다
  • 이런 구조는 부분 문제에 대한 최적 해결 방법으로 구성되는 다이나믹 프로그래밍이다

다이나믹 프로그래밍 방법론

스크린샷, 2021-09-29 18-18-23.png

  • 상향식과 하향식으로 나뉜다 상향식을 타블레이션, 하향식을 메모이제이션이라고도 한다

상향식

1
2
3
4
5
6
7
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]
  • 더 작은 하위 문제부터 살핀다음 작은 문제의 정답을 이용해 큰 문제의 정답을 풀어나간다
  • 데이터를 테이블 형태로 만들면서 문제를 풀이한다

하향식

1
2
3
4
5
6
7
8
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]
  • 하위 문제에 대한 정답을 계산했는지 확인해가며 문제를 자연스러운 방식으로 풀어나간다
  • 재귀와 비슷하며 이미 풀어봤는지 확인하여 재활용하는 효율적인 방법이다

0-1 배낭 문제

쪼갤수 없는 배낭문제를 다이나믹 프로그래밍으로 푼다

  • 모든 경우의 수를 계산해야 한다
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def zero_one_knapsack(cargo):
    capacity = 15
    pack = []

    for i in range(len(cargo) + 1):
        pack.append([])
        for c in range(capacity + 1):
            if i == 0 or c == 0:
                pack[i].append(0)
            elif cargo[i - 1][1] <= c:
                pack[i].append(
                    max(
                        cargo[i - 1][0] + pack[i - 1][c - cargo[i - 1][1]],
                        pack[i - 1][c]
                    ))
            else:
                pack[i].append(pack[i - 1][c])

    return pack[-1][-1]
  • pack에 중간 결과 테이블을 생성한다
  • 테이블 크기의 기준은 짐의 최대 개수 +1, 배낭의 최대 용량 +1로 6X16이다
  • 각 셀에는 위치까지의 짐의 개수와 배낭에 용량에 따른 최댓값이 담긴다
    스크린샷, 2021-09-30 12-51-41.png
  • 세로축은 짐의 개수, 가로축은 배낭의 용량이다
  • 0-1 배낭문제를 타뷸레이션으로 풀었다

#86 최대 서브 배열

합이 최대가 되는 연속 서브 배열을 찾아 합을 리턴하라

다이나믹 프로그래밍(메모이제이션)

1
2
3
4
5
def maxSubArray(nums: list) -> int:
    for i in range(1, len(nums)):
        print(nums)
        nums[i] += nums[i - 1] if nums[i - 1] > 0 else 0
    return max(nums)
  • 메모이제이션 풀이이다
  • 앞에서부터 값을 계산하면서 누적 합을 계산한다
  • 더해가면서 0이하일 경우에는 버린다
  • 메모이제이션으로 더한 값들 중 최댓값을 반환하면 최대 합을 알 수 있다

카데인 알고리즘

1
2
3
4
5
6
7
8
9
def kadane(nums: list) -> int:
    best_sum = -sys.maxsize
    current_sum = 0
    for num in nums:
        print(f'num {num} current num {current_sum} best sum {best_sum}')
        current_sum = max(num, current_sum + num)
        best_sum = max(best_sum, current_sum)

    return best_sum
  • 리스트의 숫자를 돌면서 매번 best_sum을 계산하여 반환한다
  • 메모이제이션과 비슷하지만 개인적으로 카데인 알고리즘이 이해하기 편했다