다이나믹 프로그래밍

다이나믹 프로그래밍(DP)

하나의 큰 문제를 여러 개의 작은 문제로 나누어서 그 결과를 저장하여 다시 큰 문제를 해결할 때 사용하는 알고리즘이다.

중복되는 계산을 줄이기 위해서 앞에서 계산한 값을 자료구조에 저장을 하는데 이러한 점 때문에 “기억하며 풀기”라고 불리기도 한다.

---

그럼 DP를 왜 쓸까?

DP는 재귀 함수와 많이 유사한데 재귀 함수를 사용하게 되면 위에서 언급한 것처럼 중복되는 계산이 생긴다. 피보나치 수를 예로 들자면 fibonacci(5)를 구하는 것은 재귀 함수로 해도 문제가 없다. 계산 횟수가 그렇게 많지 않기 때문이다. 하지만 fibonacci(100)을 재귀 함수로 계산하면 어떻게 될까?

많은 시간이 걸린다. 그래서 앞에서 계산했던 값들을 다른 자료구조에 저장을 해놓고 연산할 때 이 값들을 이용하여 계산 횟수를 줄이고, 이를 통해서 시간도 줄인다.

계산 시간을 단축하기 위해서 사용한다고 보면 된다!

---

좋은건 알겠는데 언제 사용할 수 있어?

DP를 사용 조건은 2가지가 있다.

1. 최적 부분 구조큰 문제를 작은 문제로 나눌 수 있고, 작은 문제의 답을 모아 큰 문제를 해결할 수 있는 경우

위의 그림은 A → B로 가는 최단 경로를 찾는 문제이다. A → X의 최단 경로와 X → B의 최단 경로를 더하면 A → B의 최단 경로가 된다. 이러한 문제처럼 부분 문제의 답을 모아서 전체 문제를 해결할 수 있는 경우에 DP를 사용할 수 있다.

 

2. 중복되는 부분 문제

동일한 작은 문제를 반복적으로 해결 해야 하는 경우

위의 그림을 보면 표시된 부분이 중복되는 것을 확인할 수 있다. 이러한 경우에 f(3)의 값을 계산하고 저장 해놓으면 다시 계산할 필요가 없어진다.

---

근데 어떻게 구현함?

사용 조건 처럼 구현 방법도 2가지가 있다.

1. Bottom-Up(Tabulation)

아래부터 연산을 하여 이를 누적하여 전체 문제를 푸는 방법이다.

 

def fibonacci_bottom_up(n):
    if n <= 1:
        return n

    fir = 0
    sec = 1
    for i in range(0, n-1):
        next = fir+sec
        fir = sec
        sec = next
    return next

위의 코드는 피보나치 수를 구하는 코드이다. 피보나치 수는 현재 위치가 앞의 두 개의 수의 합이다. 위의 코드에서는 현재 위치의 앞의 두 수를 더하고, 연산 했던 수 중에서 큰 수와 결과 값을 더하는 것을 반복해서 최종 결과 값을 출력하게 된다.

이와 같이 밑에서 부터 연산을 하는 방법이 Bottom-Up 방법이다.

 

2. Top-Down(Memoization)

위부터 연산을 하여 맨 밑까지 내려간 다음에 해당 결과 값을 재귀를 통해서 전이 시켜 재활용하는 방식

def fibonacci_top_down(n):
    if memo[n] > 0:
        return memo[n]

    if n <= 1:
        memo[n] = n
        return memo[n]

    else:
        memo[n] = fibonacci_top_down(n-1) + fibonacci_top_down(n-2)
        return memo[n]

위의 코드도 피보나치 수를 구하는 코드이다. 우리가 재귀 함수를 배울 때 많이 봤던 코드이다. 첫 번째 코드와 다르게 우리가 구하고자 하는 n 부터 맨 밑까지 내려가고, 값을 구하면서 다시 올라오게 된다.

 

참고: https://hongjw1938.tistory.com/47