[항해99] DP - Dynamic Programming

DP? 

DP는 우리나라말로 동적계획법이라 하며, 한번에 풀기 어려운 문제를 잘게 쪼개서 (divide) 하나하나 풀어나가며 전체 문제를 푸는 (conquer) 방식이다. 

 

우리가 일반적으로 엥? 재귀랑 다른게 뭔데! 라고 한다면 DP는 결과를 기록해서 똑같은 계산을 하지 않음으로 시간을 아낀다는 것이다. 

 

피보나치 수열

피보나치 수열은 다음 값이 이번 값과 이전 값의 합으로 표현되는 수열이다.

 

식으로 나타내면 F(

n) = F(n-1) + F(n-2) 로 표현할 수 있는데, 

 

F(5)를 계산하기 위한 과정을 보면,

F(5)를 계산하기 위해서 F(3)은 두번 계산되고

F(2)는 3번이 계산되는 것을 볼 수 있다.

5라는 숫자가 작아서 몇 번 안 되는것 처럼 보이겠지만, 

시간복잡도는 O(2^n)의 시간 복잡도를 가져서 F(30)을 구하기 위해서는 계산을 꽤 오래 해야한다. 

숫자가 커질 수록, 계산 속도는 기하적으로 증가 하는 것을 알 수 있다. 

 

그렇다면 앞에서 배운 값을 저장한다! 라는 컨셉을 이용한다면

리스트를 만들고, 새로 값을 계산했다면 그 값을 저장하고, 값이 있으면 그 값을 불러와서 계산, 없다면 식을 통해 만들어낸 뒤 저장한다!

 

코드를 보자면.

memo = [1,2]

T = int(input())

def fibo(target):
    if len(memo) > target:
        return memo[target-1]

    if target <= 2:
        return target

    ret = fibo(target - 1) + fibo(target - 2)
    if ret not in memo:
        memo.append(ret)
    return ret


while T:
    print(fibo(T))
    T = int(input())

리스트에 있는 값은 바로 반환하고, 없다면 만들어내는 코드이다.

 

다음과 같이 계산한다면 시간복잡도는 O(N) 으로 줄일 수 있다.

 

백준 1932 정수삼각형

https://www.acmicpc.net/problem/1932

1932번: 정수 삼각형

합이 최대가 되는 경로의 수의 합을 구하는 문제이다.

한 줄에서 내려올 때 왼쪽 또는 오른쪽에 있는 것에서 선택하는데, 이 중에서 가장 큰 값을 취하면서 내려온다.

INF = int(1e9)

N = int(input())
tri = []
for _ in range(N):
    tri.append(list(map(int, input().split())))

memo = [[INF] * (i + 1) for i in range(N)]
memo[0][0] = tri[0][0]


def dp(r, c):
    if not (0 <= r < N and 0 <= c < len(tri[r])):
        return 0

    if memo[r][c] != INF:
        return memo[r][c]

    memo[r][c] = tri[r][c] + max(dp(r - 1, c-1), dp(r-1, c))
    return memo[r][c]


for col in range(N):
    dp(N-1, col)

print(max(memo[N-1]))

 

이차원 배열을 이용해서 행과 열의 정보를 담고, 행과 열에 정보가 없다면 이전 행에서 왼쪽과 오른쪽 값 중에 큰 값  + 현재 행렬의 값을 더해서 다시 memo에 넣는다.

 

정보가 있으면 memo[r][c] 에서 정보를 받아와서 여러번 계산하는 것을 막는다.

 

마지막 행까지 계산을 완료한 뒤, 모든 열 중에서 가장 큰 값을 출력하면 답이 된다.

백준 14501 퇴사

https://www.acmicpc.net/problem/14501

14501번: 퇴사

어떻게 일을 하면 돈을 더 잘 벌 수 있을까! 라는 일종의 최적해 를 구하는 문제이다.

 

문제를 어떻게 나눠서 ( divide ) 어떻게 정복할 지(conquer)를 고민해보면

 

일단 n번째 날에 고를 수 있는 선택지는

일을 하거나, 안 하거나 이다

이를 어느정도 수도코드로 만든다면

 

F( n번째날, 여태 번 돈)

 

-> 근무를 한다면 F( n + t, 여태 번 돈 + 근무해서 버는 돈 )

 

-> 근무를 안 한다면 F(n + 1, 여태 번 돈 ) 

 

으로 표현할 수 있다.

 

문제의 조건에 맞게, 퇴사를 하는 날이 넘어가면 일을 하지 않는 조건을 넣고 지금까지 번 돈이 제일 많으면 max_val에 이를 저장해서 마지막에 출력만 해주면 문제의 답을 구할 수 있다.

N = int(input())
lst = []
for _ in range(N):
    t, p = map(int, input().split())
    lst.append((t, p))

max_val = 0

def dp(idx, pay):
    global max_val
    if idx >= N:
        if pay > max_val:
            max_val = pay
        return

    t, p = lst[idx]

    for i in range(2):
        if i == 1:
            if idx + t > N:
                return
            dp(idx + t, pay + p)
        else:
            dp(idx + 1, pay)


dp(0, 0)
print(max_val)

"""
dp ( n번째날, 여태 번 돈) 

-> 근무를 한다면 dp (n+t, 여태 번돈 + n번쨰날 번 돈)

-> 근무를 안 한다면 dp(n+1, 여태 번돈 )
"""

 

회고

어렵게 생각하면 엄청나게도 어려워질테지만, thinking Backward와 divide and conquer를 이용해서 조금씩 조금씩 DP도 정복해 나가자.