D P

조졌다. 오면 안되는게 왔다.

동적 프로그래밍은 사실 동적이냐고 하면 이상하다.
Dynamic Programming을 처음 생각해낸 사람 조차 정부의 지원금을 타기 위한 그럴듯한 이름이 필요했다고 설명한다.

어쨌든, 동적 프로그래밍의 개발 취지는, 인류 문명에 있어 최적화 문제를 푸는 것이 중요했기 때문이다. 내가 햄북스딱스를 뒤집어먹을건지, 토마토를 빼고 먹을건지, 사이사이에 감자튀김을 살짝 채워먹을건지 순서와 방법 하나하나는 인류가 더 나은 방향성으로써 지내게 하는 주된 내용이지 않은가.

예로부터 프로그래밍은 계획을 논하는 경우도 잦았기에, 동적 계획법이라고 번역되기도 한다.

어쨌든, DP는 분할정복과 같이 논하게 된다. 하지만..

• DP도 나눠 푸는 것은 사실이다.
• DP는 최적화 문제를 푼다는 표현이 맞다.
  • 여기서 최적이라는 용어는 여러 조건들을 잘 만족 시키는 것을 말한다.
  • 다시 말해, 모든 조건을 정확하게 만족 시킬 필요는 없다!

여러가지 논함이 많겠지만, 최적 하부 구조로 풀 수 있는 형태를 Dynamic Programming 으로 수행한다고 표현한다.
부분적인 최단경로 같은게 예제인데, 이 부분에 대해선 빠른 시일 내 다른 글에서 다룰 수 있도록 하겠다.

그리고 중복되는 부분 문제들에 대한 해결 방안도 포함된 것이 DP이다.

Top DOWN vs Bottom Up
탑 따 운	바텀 업
재귀를 활용하여 큰 문제를 작은 문제로 나눈다.	작은 문제를 차근차근 수행하며 주로 반복문을 사용한다.
재귀 사용으로 인해 바텀 업보단 다소 느리다.	단순 반복문이기에 탑다운에 비해 우수한 속도이다.
탑 다운에서의 기존 내용 저장을 Memoization 이라 한다.	표를 채우는 형태의 저장 방식이며, Tabulation 이라 부른다.
재귀는 항상 어렵다. 조절 하지 못하면 생각보다 안된다.	모든 문제를 계산 해야한다. 불필요한 계산 포함 될 수 있다.

간단한 예제.

탑 다운 식 피보나치

def fib_topdown(n, memo):
    if n <= 1:
        return n
    if n not in memo:
        memo[n] = fib_topdown(n - 1, memo) + fib_topdown(n - 2, memo)
    return memo[n]

# 호출
n = 10
print(fib_topdown(n, {}))  # 결과 출력

바텀 업 식 피보나치

def fib_bottomup(n):
    if n <= 1:
        return 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]

# 호출
n = 10
print(fib_bottomup(n))  # 결과 출력