동적프로그래밍(Dynamic Programming)

📢 동적프로그래밍

• 동적프로래밍(DP, Dynamic Programming) : 알고리즘 설계의 일반적 기법 중 하나
• 언뜻 보기에 많은 시간( 심지어 지수 시간 )이 소요될 것 같은 문제에 주로 적용한다.
• 적용의 조건은 :
  
  👉 부문제 단순성(Simple Subproblems) : 부문제들이 j,k,l,m 등과 같은 몇 개의 변수로 정의 될 수 있는 경우
  👉 부문제 최적성(Optimality Subproblems) : 전체 최적치가 최적의 부문제들에 의해 정의될 수 있는 경우
  👉 부문제 중복성(Overlap Subproblems) : 부문제들이 독립적이 아니라 상호 겹쳐질 경우 ( 즉, 상향식으로 구축 )
  
  
• 대표적 예시
  
  👉 피보나치 수(Fibonacci progression)에서 N-번째 수 찾기
  👉 그래프의 이행적폐쇄 계산하기
  
  
• 동적프로그래밍 vs 분할통치법
  
  공통점
  
  👉 알고리즘 설계기법의 일종
  👉 문제공간 : 원점-목표점 구조 ( 원점 : 문제의 초기 또는 기초지점 / 목표점 : 최종해가 요구되는 지점 )
  
  차이점
  
  👉 문제해결 진행 방향
  
  동적프로그래밍(단방향) : 원점 -> 목표점
  분할통치법(양방향) : 목표점 -> 원점 -> 목표점 ( 단, 해를 구하기 위한 연산을 진행, 방향은 원점->목표점 )
  
  성능
  
  👉 동적프로그래밍 : 단방향 특성때문에 종종 효율적
  👉 분할통치법 : 분할 회수(보통 2분할을 한다.) , 중복연산 수행 회수에 따라 다름
• 이름은 "동적"프로그래밍이지만, 실제로 우리가 아는 "동적", 그때그때 사용하는 그런 의미는 아니다.
  하나 구한 것은, 다를 때, 사용하는 의미일 뿐이고, 이러한 기법의 이름을 지은 사람이 그냥 "동적프로그래밍"이라 작명한 것 일 뿐이다. 오해하지말자.

📢  동적프로그래밍 예시

• N-번째 피보나치 수 찾기 : 피보나치 수열(Fibonacci Progression)은 i = 0,1에 대해 f(i) = 1이며, i >= 2 에 대해
  f(i) = f(i-1) + f(i-2)인 수열이다.
• 즉, f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5, f(5) = 8, .......
• f(n), 즉 피보나치 수열의 n-번째 수를 찾기 위해, 정의로부터 직접 재귀알고리즘 f를 작성할 수도 있지만,
  불행히도 지수시간(exponential time)에 수행하므로 너무나 비효율적이다 !!
• 이를, 동적프로그래밍에 기초하여 f(n)을 찾는 비재귀, 선형시간 알고리즘을 다음 두 버젼으로 작성해보자.
  
  👉 1. 선형공간으로 수행하는 버젼
  👉 2. 상수공간으로 수행하는 버젼

Alg f(n)		// 선형 공간

if(n == 0 || n == 1)
    return 1

A[0] <- 1
A[1] <- 1
for i <- 2 to n
    A[i] <- A[i-1] + A[i-2]

return A[n]

=============================

Alg f(n)		// 상수 공간

if(n == 0 || n == 1)
    return 1

a <- 1
b <- 1
for i <- 2 to n
    c <- a + b
    a <- b
    b <- c

return c