[ 알고리즘 ] 다이나믹 프로그래밍(DP) - 개념

1. 다이나믹 프로그래밍(DP)이란 ?

큰 문제를 작은 문제로 나누어 푸는 알고리즘 

다이나믹 프로그래밍, 동적계획법은 문제를 어떤 형태로 변형시켜 쉽게 푸는 방법을 의미한다. 

 

 

* 여담이지만 '동적(Dynamic)'은 멋있어보여서 붙은 이름이라고 한다. 처음에 이 사실을 모르고 Dynamic에 집중해서 이 알고리즘을 보았는데 .. 계속 어느 부분이 동적으로 작동한다는 거지? 라고 생각했었다. 이 사실을 알고 나서는 '계획법'을 집중해서 보게 되었다.. !

---

2. DP의 2가지 필수 조건 

 

1) Overlapping Subproblem

같은 문제는 항상(구할 때 마다) 정답이 같다. 

큰 문제가 작은 문제로 세분화될 수 있고, 같은 방법으로 풀릴 때 

ex. 피보나치 수

출처 : Koala 깃북

- Fib(n-1) = Fib(n-2) + Fib(n-3)

- Fib(n-2) = Fib(n-3) + Fib(n-4) 

큰 문제(왼쪽 항) = 작은 문제들(오른쪽 항)로 구성되며 구하는 방법이 모두 동일하다 ! 

 

2) Optimal Substructure

작은 문제들이 반복된다. 

큰 문제의 정답을 작은 문제의 정답들로 구할 수 있을 때 

출처 : Koala 깃북

피보나치 수열의 첫번째 항, 두번째항은 각각 1,1 로 지정이 되어있고 3번째 수는 언제나 2, 4번째 수는 언제나 3, 5번째수는 언제나 5 .. 처럼 지정되며 이후 항들도 지정된 앞 항들의 덧셈으로 이루어지므로 언제나 같은 값을 가지는 것을 알 수 있다 ! 

 

 

1, 2 번은 서로 겹치며 유사한 부분이 많기에 굳이 1번인가 2번인가를 따지지 않아도 될 것 같다. 무엇보다 중요하게 기억해야할 점은 바로 작은 문제들의 반복과 이 같은 문제들은 항상 구할 때 값이 같다는 것이다 

 

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

15624번: 피보나치 수 7

대표적인 DP, 피보나치와 관련한 문제이다 .

---

3. 구현방법 

* 메모이제이션 (memoization) : 값을 저장해놓고 가져다 쓴다 - 시/공간적인 효율성을 추구 
다이나믹 프로그래밍에서는 작은 문제들이 반복되고 이 반복되는 작은 문제들의 값이 항상 같다. 그래서 우리는 이 점을 활용하여 조금 더 효율적으로 코드를 짜 보고싶다. 이렇게 반복되는 작은 문제들의 값을 기억하는 것이 바로 이 '메모이제이션'이다! 

 

출처 : Koala 깃북

1. Top-Down 방식

말 그대로 위 → 아래로 탐색을 진행해나가는 과정이다. 예를 들어 피보나치 수열의 F(7)을 구하기 위해 F(6),F(5)를 구하고 여기서 F(6)을 구하기 위해 F(5),F(4)를, 다시 F(4)를 구하기 위해 F(3), F(2)를 구하는 과정이다. 

재귀함수로 구현하는 경우가 대부분 이 Top-down방식이다. 큰 문제를 풀기 위해 작은 문제를 풀어나가는 것이다! 

* 작성하기 어렵지만 가독성이 좋다 

n = int(input())

dp = [0]*(n+1)

def fib(n):
    if n==1 or n==2:
        return 1
    # dp값이 0이 아닌 인덱스 = 이미 값을 구한 인덱스
    if dp[n] !=0:
        return dp[n]

    dp[n]=fib(n-1) + fib(n-2)
    return dp[n]

print(fib(n))

 

2. Bottom-Up 방식 

아래 → 위 방식으로 올라가는 방식이다. F(7)을 구하기 위해 F(1), F(2), F(3)... F(6)까지 차근차근 구한 뒤 F(7)을 구하는 방법이다. 아래에서부터 작은 문제들을 차근차근 구해서 큰 문제를 구하는 방식이다. 

* 작성하기 쉽지만 가독성이 어렵다 

##bottom-up
n = int(input())

dp= [0] * (n+1)

dp[1] = 1
dp[2] = 1

#재귀호출
for i in range(3,n+1):
    dp[i] = dp[i-1] +dp[i-2]

print(dp[n])

---

요약 

중요한 건 꺾이지 않는 코드 .. 

- DP는 큰 문제가 작은 문제로 분할되며 이 작은 문제들의 값은 항상 동일하다 !!! 

- Top-Down 방식, Bottom-up 방식이 나은지에 대해서는 정답이 없다. 각각의 장단점이 있기에 .. 본인에게 맞는 편한 코드를 찾아서 사용해보면 될 것 같다 ! 

---

[ 참고 및 출처 ]

https://koalas-organization.gitbook.io/koala_codingtest_study/greedy_and_dp/dp1 

https://koalas-organization.gitbook.io/koala_codingtest_study/greedy_and_dp/dp2

https://galid1.tistory.com/507

https://konghana01.tistory.com/100