[쓰면서 익히는 알고리즘과 자료구조](7) 동적 프로그래밍(Dynamic Programming)

 

동적 프로그래밍은 어디서 유래되었을까?

 

동적(Dynamic)이란 말은 수학자인 리처드 벨만이 알고리즘의 시가변적(time_varing)이며 다단계적인 특성을 나타내기 위해서 채택한 용어라고 한다.

 

동적프로그래밍 알고리즘을 적용한다는 것은 하나의 문제를 작은 단위로 쪼개어 해결하고 결과를 수집 및 병합하여 최정 결론을 만들어내는 일련의 과정을 말한다.

 

여기서 중요한 포인트가 하나 더 있는데 동적 프로그래밍은 쪼개어진 문제를 해결해가는 과정에서 연산의 결과값을 저장하고 그 이후엔 중복된 연산의 저장된 값을 꺼내어 쓸 수 있다는 것이다.

 

동적 프로그래밍으로 해결하는 문제는 모든 경우의 수를 파악하여 진행하면(brute-forece) 지수승의 시간 복잡도를 가지는 경우가 많다. 피보나치수열도메모이제이션을 사용하지 않는 다면 O(2^n)의 시간 복잡도를 가진다.

 

동적 프로그래밍도 다양한 문제를 학습 및 연습한다면 난이도가 높은 코딩 문제 해결에 대한 자신감이 생길 것이다.

 

동적 프로그래밍을 통해 문제를 해결하기 위해서는 단계적 풀이에 대한 연습이 필요하다.

 

전체 탐색(Brute-force) 방법으로 문제를 우선 해결해 본다.

그다음 해당 풀이를 분석하여 반복되는 작업을 정리한다.

즉, 전체 탐색에서 하위(sub problem)로 쪼개어보고 반복되는 단계가 있는지 찾아낸다.

 

---

7.1 0 / 1 배낭(knapsack) 문제

items = {물,통조리,라디오, 구급약}

values = {7,5,3,4}

weights = {2,1,3,4}

배낭 용량 = 5

물 + 라디오 (총 무게5) ⇒ 가치 10

통조리 + 라디오 (총 무게4) ⇒ 가치 8

물 + 통조리(총무게3) ⇒ 가치 12

이론 조합이 가능할 테넫 배낭 용량에서 가장 가치가 높은 구성은 물과 통조림을 챙기는 것이다.

각 이이템 별로 선택과 비선택이 있을 수 있다. 이걸 이용해서 재귀로 풀어보자

 

def knapsack_brute_force(values: list[int], weights: list[int], capa: int, curr_index: int):
    if capa <= 0 or curr_index >= len(values):
        return 0

    selected = 0

    if weights[curr_index] <= capa:
        selected = values[curr_index] + knapsack_brute_force(values, weights, capa - weights[curr_index], curr_index + 1)

    not_selected = knapsack_brute_force(values, weights, capa, curr_index + 1)

    return max(selected, not_selected)


print(knapsack_brute_force([7, 5, 3, 4], [2, 1, 3, 4], 5, 0))

동일한 capa 와 index 값을 저장해놓으면 다시 사용할 수 있음을 알 수 있다.

 

def knapsack_dp(dp, values, weights, capa, curr_index):
    if capa <= 0 or curr_index >= len(values):
        return 0

    if dp[curr_index][capa] != -1:
        return dp[curr_index][capa]

    selected = 0
    if weights[curr_index] <= capa:
        selected = values[curr_index] + knapsack_dp(dp, values, weights, capa - weights[curr_index], curr_index + 1)
    not_selected = knapsack_dp(dp, values, weights, capa, curr_index + 1)

    dp[curr_index][capa] = max(selected, not_selected)

    return dp[curr_index][capa]


dp1 = [[-1 for _ in range(8)] for _ in range(4)]
print(knapsack_dp(dp1, [1, 6, 10, 16], [1, 2, 3, 5], 7, 0))

 

이와 같이 최종 값을 기준으로 하위 문제로 진행되며 트리 모양 연산이 발생하는 접근 방식을 Top Down 방식이라고 부른다. 동적 프로그래밍은 하위 문제로부터 최종 입력값으로 향해가는 Bottom Up 방식으로도 구현 가능하다. 이는 중복된 연산을 제거하느 방식이라기 보다 하위 문제에서 상위로 진행하며 어떤 가치를 가질 수 있는지에 대한 한계를 파악하는 과정을 통해 최종 값에 도달 할 수 있도록 하는 방식이다.

 

def knapsack_dp_bu(n, values, weights, capa):
    if capa <= 0 or n == 0 or n != len(weights):
        return 0

    dp = [[0 for _ in range(capa + 1)] for _ in range(n)]

    for c in range(capa + 1):
        if weights[0] <= c:
            dp[0][c] = values[0]

    for i in range(1, n):
        for c in range(1, capa + 1):
            selected, not_selected = 0, 0
            if weights[i] <= c:
                selected = values[i] + dp[i - 1][c - weights[i]]

            not_selected = dp[i - 1][c]
            dp[i][c] = max(selected, not_selected)

    return dp[n - 1][capa]

 

---

7.2 동일 합으로 배열 분할 문제

배열이 주어졌을 때 동일한 합을 가지는 배열로 분할 가능한지 판단하는 문제

 

def can_partition(nums: list[int]) -> bool:
    if sum(nums) % 2 != 0:
        return False

    def can_partition_rec(nums: list[int], s, index):
        if s == 0:
            return True
        if index >= len(nums):
            return False

        if s - nums[index] >= 0:
            if can_partition_rec(nums, s - nums[index], index + 1):
                return True

        return can_partition(nums, s, index + 1)

    return can_partition_rec(nums, int(sum(nums) / 2), 0)

 

def can_partition_td(nums: list[int]) -> bool:
    s = sum(nums)
    if s % 2 != 0:
        return False

    def can_partition(dp: list[int], nums: list[int], s, index):
        if s == 0:
            return 1
        if index >= len(nums):
            return 0

        if dp[index][s] == -1 and nums[index] <= s:
            if can_partition(dp, nums, s - nums[index], index + 1) == 1:
                dp[index][s] = 1
                return 1

        dp[index][s] = can_partition(dp, nums, s, index + 1)

        return dp[index][s]

    dp = [[-1 for x in range(int(s/2)+1)] for y in range(len(nums))]

    return True if can_partition(dp, nums, int(s/2), 0) == 1 else False

 

def can_partition(nums: list[int]) -> bool:
    total = sum(nums)
    n = len(nums)
    if total % 2 != 0:
        return False

    half = int(total / 2)
    dp = [[False for x in range(half + 1)] for y in range(n)]

    for i in range(n):
        dp[i][0] = True

    for s in range(half + 1):
        if nums[0] == s:
            dp[0][s] = True

    for i in range(1, n):
        for s in range(1, half + 1):
            if dp[i - 1][s]:
                dp[i][s] = dp[i - 1][s]
            elif s >= nums[i]:
                dp[i][s] = dp[i - 1][s - nums[i]]

    return dp[n - 1][half]

---

7.3 동전교환

동전 교환 문제는 요소를 중복 선택할 수 있는 점에서 조금 다르게 진행된다.

 

def coin_change(coins: list[int], amount: int) -> int:
    def coin_rec(remain: int):
        nonlocal coins

        if remain == 0:
            return 0

        min_coins = float('inf')

        for coin in coins:
            if remain >= coin:
                curr_min = coin_rec(remain - coin)
                min_coins = min(curr_min, min_coins)

        return min_coins + 1

    return coin_rec(amount)


print(coin_change([1, 2, 3], 6))

 

def coin_change_td(coins: list[int], amount: int) -> int:
    dp = [-1 for _ in range(amount + 1)]

    def coin_rec(remain: int):
        nonlocal dp, coins

        if remain == 0:
            return 0

        if dp[remain] != -1:
            return dp[remain]

        min_coin = float('inf')
        for coin in coins:
            if remain >= coin:
                min_coin = min(min_coin, coin_rec(remain - coin) + 1)

        dp[remain] = min_coin
        return dp[remain]

    return coin_rec(amount)

 

def coin_change(coins: list[int], amount: int) -> int:
    dp = [float('inf') for _ in range(amount + 1)]

    dp[0] = 0

    for i in range(1, amount + 1):
        for c in coins:
            if i >= c:
                dp[i] = min(dp[i - c] + 1, dp[i])

    return dp[amount]

---

7.4 최장 공통부분 수열(Longest Common Subsequence)

두 문자열(str1, str2)이 주어지면 해당 두 문자열의 최장 공토부분 수열의 길이를 반환하자, 부분 수열은 연속적이지는 않으나 순서대로 나열될 수 있는 문자열을 말한다.

 

def lcs(str1: str, str2: str) -> int:
    def lcs_rec(i, j):
        nonlocal str1, str2

        if i >= len(str1) or j >= len(str2):
            return 0

        if str1[i] == str2[j]:
            return 1 + lcs_rec(i + 1, j + 1)
        else:
            return max(lcs_rec(i + 1, j), lcs_rec(i, j + 1))

    return lcs_rec(0, 0)

 

def lcs_td(str1: str, str2: str) -> int:
    dp = [[-1 for _ in range(len(str2) + 1)] for _ in range(len(str1) + 1)]

    def lcs_rec(i, j):
        nonlocal str1, str2, dp

        if i >= len(str1) or j >= len(str2):
            return 0

        if dp[i][j] != -1:
            return dp[i][j]

        if str1[i] == str2[j]:
            dp[i][j] = 1 + lcs_rec(i + 1, j + 1)
        else:
            dp[i][j] = max(lcs_rec(i + 1, j), lcs_rec(i, j + 1))

        return dp[i][j]

    return lcs_rec(0, 0)

 

def lcs_bu(str1: str, str2: str) -> int:
    n = len(str1)
    m = len(str2)
    dp = [[-1 for _ in range(m + 1)] for _ in range(n + 1)]

    for i in range(m + 1):
        dp[0][i] = 0

    for j in range(n + 1):
        dp[j][0] = 0

    for i in range(1, n + 1):
        for j in range(1, m + 1):
            if str1[i - 1] == str2[j - 1]:
                dp[i][j] = 1 + dp[i - 1][j - 1]
            else:
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

    return dp[n][m]