다이나믹 프로그래밍 1

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법

하지만 우리의 일생은 위 그리디처럼 항상 독립적으로 일어날 수 없습니다. 과거에 의존적인 상황에서는 그럼 어떻게 해야 효율적인 판단을 내릴 수 있을까요?

이런 상황에서 우리는 복잡한 문제들을 여러 문제로 나누어 푸는 방법을 사용합니다. 아주 Dynamic하죠..?

DP를 가장 쉽게 설명하는 방법은 바로 우리가 쉽게 접해왔던 피보나치 수열입니다.

지금껏 피보나치 수열은 재귀함수로 많이 표현이 되어왔습니다.

하지만 이러한 함수 호출은 매우 치명적입니다. 위 그림을 보면 f(1)과 f(0)이 여러 번 출력됨을 볼 수 있습니다. 알고리즘 코드를 짜다보면 파이썬 에러 중 RecursionError: maximum recursion depth exceeded in comparison. 이 에러를 많이 보신 분들이 있을 텐데요. 이런 문제를 해결하기 위해 우리는 memoization, 즉 값을 저장해놓고 가져다 쓰는 방법을 사용할 수 있습니다. 📌Memoization은 시간/공간적으로 크게 효율적입니다.

다음으로 우리가 문제에 접근할 수 있는 방법을 알아봅시다.

피보나치 수열을 알아갈 때 위처럼 f(5)을 찾기 위해 f(4)와 f(3)을 탐색하는 직관적인 관점이 있습니다. 이를 우리는 📌Top Down 방식이라고 합니다.

하지만 애초에 f(1)부터 차근차근 구해놓고 시작해보면 어떨까요? 피보나치 수열을 나타낼 때 우리는 1 1 2 3 5 8 13 21 34 … 이런 식으로 앞에서부터생각해낼 수 있습니다. 이렇게 애초에 아래에서부터 차근차근 구해놓고 시작하는 것을 📌Bottom up 방식이라고 합니다.

다음 피보나치 수열을 BOTTOM-UP 형식으로 나타내면 다음과 같습니다.

N = int(input())
dp = [0]*(N+1)

def fib(num):
    dp[num] = dp[num-1] + dp[num-2]
    
if N == 0 :
    print(0)
else :
    dp[1] = 1
    for i in range(2, N+1):
        fib(i)
    print(dp[N])

  • DP중 bottom-up(상향식)방법은 1+2부터 시작해서 작은 수부터 N+1 길이의 dp를 채워주고 마지막 결과값을 반환합니다.

  • 트리 모양의 피보나치 수에서 밑(자식노드)에서부터 구하기 시작하는 것입니다.

TOP-DOWN은 다음과 같습니다.

N = int(input())
dp = [0]*(N+1)

def fib(num):
    if num <= 1 :
        return num
    elif dp[num] != 0:
        return dp[num]
    dp[num] = fib(num-1) + fib(num-2)
    return dp[num]
print(fib(N))

  • DP중 Top-down(하향식)방법은 우리가 구하고자 하는 수를 먼저 입력받습니다. N=100이라고 가정해봅시다. 우선dp[99] + dp[98]을 가져와서 더해!라고 명령합니다. > 그래서 dp[99]랑 dp[98]이 뭔데? > dp[99]와 dp[98]를 찾기위해 fib[99] 실행, fib[98] 실행합니다. > 그 안에서 또 98 97을 가져오라고 불러오면서 아래로 내려가는 형식입니다.

  • 그래서 계속 물어보며 내려가다가 값이 나오는 if num <= 1 : return num 이 조건에서 1과 0이 나오면서 그때부터 값이 채워지며 답하기 시작합니다.

  • 이 때 elif를 보면, 만약 dp[num]이 0이 아닌 경우 저장해두었던dp[num]값을 가져오는 것을 볼 수 있습니다. 이것이 바로 memoization 입니다.

번외) 번외로, TOP DOWN 방식은 위에서 보는 것으로 알 수 있듯이 재귀함수로 구현됩니다. 파이썬은 Recursion의 한도가 시스템의 안정을 위해 정해져 있다는특징이 있습니다. 그래서 그 한도를 푸는 방법이 있는데, sys 모듈로 recursionlimit을 풀어주어야 하는 경우가 많습니다.

import sys     
sys.setrecursionlimit(10000)     #재귀의 한도를 10000까지 풀어준다.

이 점이 파이썬이 C++에게 뒤쳐지는 이유인데요, 가끔 python으로는 풀리지 않은 백준 / 또는 대회 DP TOPDOWN 문제가 존재합니다. 하지만 코딩테스트에서는 그럴 일이 많이 없으니 걱정 마세요!

다음으로는 2차원으로 memoization하여 사용하는 DP 문제에 대해 알아볼까요?

이 문제를 그리디로는 풀 수 없습니다. 이 사실은 '가장 높은 점수를 가지는 두 스티커 (100과 70)은 변을 공유하기 때문에, 동시에 뗄 수 없다.' 라는 문장만 봐도 알 수 있습니다.

규칙은 매우 단순합니다. 현재상태에서의 최선의 점수를 보려면 한 칸 앞 대각선 또는 두칸 앞 대각선을 보면 결정할 수 있습니다.

예를 들어 노란색 구간에서의 최대값을 찾고 싶다고 해봅시다 그러면 아래 1번 경우와 2번경우의 파란색 상황에서 적용해 가져올 수 있습니다.

만약 아래 3번 상황도 가져와야 하는 거 아닌가? 라고 생각했다면, 3번 상황은 1번 상황에 이미 반영되어 있을 것이므로 불가능합니다!

이를 모두 종합하여 이렇게 BOTTOM UP DP를 구현할 수 있습니다.

t = int(input())
for i in range(t):
    s = []
    n = int(input())
    for k in range(2):
        s.append(list(map(int, input().split())))
    for j in range(1, n):
        if j == 1:
            s[0][j] += s[1][j - 1]
            s[1][j] += s[0][j - 1]
        else:
            s[0][j] += max(s[1][j - 1], s[1][j - 2])
            s[1][j] += max(s[0][j - 1], s[0][j - 2])
    print(max(s[0][n - 1], s[1][n - 1]))

위와 같이 1열부터 시작하여 BOTTOM UP 방식으로 2차원 채워나갈 수 있습다.

※ 더 생각해보기!

다음 문제는 어떻게 해결해야 할까??

KAU 대학교의 학생식당은 맛없는 음식으로 악명이 높다. 두 식당이 A,B 둘 있고 밥값은 $3, $4, $5 중 하나이다. 총 N일동안 각 식당의 가격이 미리 공지된다. KAU 대학교의 모든 학생은 반드시 하루에 정확히 한 끼를 학생식당에서 먹어야 한다. 최소의 비용으로 밥을 먹으려 하는데, 이 식당들의 음식은 너무 맛이 없어 연속으로 최대 이틀까지 같은 식당에서 밥을 먹을 수 있다.

즉, 예를 들면, 1일, 2일을 식당 A에서 밥을 먹었다면 3일째에는 반드시 식당 B에서 밥을 먹어야 한다. 아래 표는 총 8일간 식당의 가격표이다. 위 조건을 만족하면서 8일간 밥을 먹는 최소 비용을 구하시오.

답은 3차원 DP로 DP[식당 A, 식당 B][총몇 일째인지][연속된 날짜수] 로 표현하여 의존성을 생각하며 처리하는 것입니다.

풀어볼 문제

Previous그리디Next다이나믹 프로그래밍 2

Last updated