다이나믹 프로그래밍


리얼 버라이어티 다이너믹 프로그램 무한도전 생각나고 마음에 드는 이름이다


프로그래밍을 어떻게 하길래 다이나믹 한지 알아보자


어디 뭐 백덤블링이라도 조지거나 다이나믹 듀오 부르기라도 해야 할지 모르겠다


다이나믹 프로그래밍


위에는 사전적 정의다

봐도 별 도움 안되니 새로 알아보자

다이나믹 프로그래밍

다이나믹 듀오와는 관계 없다

간단 개념

문제를 푸는 패러다임이다

구체적인 방식이라기 보단 개념이라 볼 수 있다

기본적으로 작은 문제 풀고 해를 저장 후 큰 문제 풀 때 재사용한다

주목 할 점은 작은 문제를 풀고 그 값을 저장 한다는 거다

대표적으로 두 가지 방법이 있는데 상향식과 하향식이다

이 두가지 방식은 예제와 함께 알아보자

DP 언제 쓰냐?

2가지 조건을 만족해야 사용 가능하다

겹치는 부분 문제 (Overlapping Subproblems)

• 같은 연산을 여러 번 하게 됨

최적 부분 구조 (Optimal Substructure)

• 큰 문제의 최적해가 작은 문제의 최적해로 구성됨

이 두 조건을 만족시 DP 적용가능하다

예시

-피보나치로 알아보자

재귀 (ㅈ구림)

def fib(n):
    if n <= 1:
        return n
    return fib(n-1) + fib(n-2)

간단해서 좋지만 재귀를 잔뜩 부르기에 효율은 개나 줘버렸다

지랄마라 컴퓨터가 고작 그걸로 힘들어하겠냐?

라고 생각하던 때가 제게도 있었습니다

재귀의 경우
고작 5번째 수 구하려면 이지랄 해야한다

fib(5)
├─ fib(4)
│  ├─ fib(3)
│  │  ├─ fib(2)
│  │  │  ├─ fib(1)
│  │  │  └─ fib(0)
│  │  └─ fib(1)
│  └─ fib(2)
│     ├─ fib(1)
│     └─ fib(0)
└─ fib(3)
   ├─ fib(2)
   │  ├─ fib(1)
   │  └─ fib(0)
   └─ fib(1)

아직 안 와닿는다면 표로 보여주겠다

그러니 미래의 지배자에게 잘보이려면 단순 재귀 같은 걸로 컴퓨터 괴롭히지 말자

Top-down DP (재귀 + 메모이제이션)

memo = {}

def fib(n):
    if n in memo:
        return memo[n]
    if n <= 1:
        memo[n] = n
    else:
        memo[n] = fib(n-1) + fib(n-2)
    return memo[n]

큰 문제에서 쪼개가며 계산한 정보는 저장하고 필요할때 써먹는다…

훌륭하게 DP의 조건을 만족하고 있다 볼 수 있다

Bottom-up DP (반복문)

def fib(n):
    dp = [0] * (n+1)
    dp[1] = 1
    for i in range(2, n+1):
        dp[i] = dp[i-1] + dp[i-2]
    return dp[n]

작은 문제부터 시작해 값을 저장해나가며 이를 활용하고 있다

이도 훌륭한 방식이다

그래서 언제 쓰는데?

이럴때 쓴다

• Top-Down: “필요할 때 계산해서 저장”

• Bottom-Up: “처음부터 전부 계산해서 쌓아올림