[알고리즘] Dynamic 프로그래밍과 예제들

우리가 여태 배워온 것들은 아래와 같다.
- D&C 기법
- Backtracking 기법
  : 어떤 결정의 연속을 통해 문제의 답을 점차적으로 만들어가는 것.
    Recursion을 돌린다. -> 문제에 대한 일반화가 필요함.

// 이번시간에 배울 것 
 - Recursion은 항상 옳은가?
 - 쓸데 없이 많은 Recursive call을 줄여보자.
 - 점화식을 이용한 효율적 구현
   >> Dynamic program (동적 계획법)

Dynamic Programming을 사용한 알고리즘
 - Fibonacci number 계산
 - Longest Increasing Subsequence(LIS)
 - Subset Sum

--------------------------------------------------------------------------------

// Dynamic Programming을 피보나치 수열을 통해 알아보자.

재귀적인 피보나치 수열

D&C 기법과 재귀를 통해 배웠던 Fibnacci 수열을 기억해보자.
우리가 배웠던 Fibonacci는 아래 그림과 같이 엄청 느리고 중복이 많다. -> 중복을 없애려면? Memoization. 

반복됨을 기억하려면? DP 프로그래밍의 Memoization하자.

Memoization
 : 계산한 결과를 저장하고 필요하면 다시 꺼내 쓰자.
   테이블을 이용해 저장한다(Fill the Table).

0

1

1

2

3

5

...

   이때, base case인 0과 1은 이미 채워져 있음. (테이블의 노란색 부분부터 채워진다.)

테이블을 사용하여 Memoization하는 방법을 이해하겠는가? Recursion을 통해 트리를 계속 만들어가는 것이 아닌 만들어진 값을 반복을 통해 테이블에 저장해두었던 '값'만을 불러오는 것이 DP Programming의 방법이다.

반복을 이용한 피보나치 수열

- bottom-up방식이다 : base case부터 테이블을 채워나가고, 가장 마지막의 값이 결과 값이거나 조금 수정해서 얻을 수 있음.
   **recursion은 top-down 방식이라 얘기하며, 전체 n을 나눠서 부분 문제로 n-1, n-2로 줄어들기 때문이다.

Fibbonacci에서 Fill the Table을 동작할 때, F[n]개의 값을 모두 기억하는 게 아니라 F[i-1]과 F[i-2] 값만 순간적으로 기억하여 next <- F[i-2]+F[i-1]로 진행한다. 
  >> 결과적으로 피보나치 수열에 DP 프로그래밍을 사용하면, O(n) 시간이 걸리는건 똑같지만, 사용되는 메모리가 O(n) 값에서 O(1)로 줄어든다. 


Dynamic Programming?
: DP 알고리즘은 중간의 subproblem에 대한 solution을 저장하는데, 보통 array 또는 테이블을 이용한다.
 recursion을 사용하지만 without repetion이다. (=중복이 없다.)
"Dynamic Programming is not about filling in tables. It's about smart recursion!"
      >> DP는 테이블을 채우는 게 아니다, 좀 더 똑똑하게 recursion 하는 과정이다.

**학교 수업을 듣다보니 동적 프로그래밍은 반복 혹은 재귀 중에 어떤 것을 사용하는 건지 헷갈렸다. 교수님께서는 주로 반복을 사용한 예제들만 설명해주셔서 그럼 재귀는 DP 프로그래밍에 사용되지 않는가 싶어 더 알아본 내용들이다. 추가적으로, 다른 블로그에서는 동적 계획법을 사용하면 기존의 시간복잡도가 변하지 않는다고 한 블로그가 몇 있었지만 구현 방식에 따라서 달라질 수 있다고 한다.

출처 : https://velog.io/@polynomeer/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming

DP를 사용하여 문제를 해결하는 일반적인 과정
1. Formulate the problem recursively
    : 문제를 해결하는 recursive algorithm 혹은 점화식을 찾아내야 한다.
      Formulate the problem recursively -> hard part
  - Specification : 문제를 명확하게 기술하라.
  - Solution : 명확한 점화식을 알아내라.
2. Build Solutions to your recurrence from the bottom up
    : Base case로부터 차곡차곡 답을 찾아간다.

DP 프로그래밍에 대한 일반적인 과정
 1) Identify the subproblems : 0에서 n 사이의 sub 문제를 풀게 된다.
 2) Choose a memoization data structure : 값들을 기억한다.
 3) Identify depenencies : 종속성
 4) Find a good evaluation order : 계산 순서를 알게 된다.
 5) Analyze space and running time : 시간 복잡도 분석을 하라.
 6) Write down the algorithm : for loop을 통해 푼다.
  **점화식을 찾는 것은 창의력이 필요함.


Dynamic Programming 기법을 적용해보자.
① LIS 시퀀스 구하기
 우리는 Backtracking을 이용해서 O(2ⁿ) 의 시간 복잡도를 가질 수 있었다.
  ((지수함수에 대한 알고리즘은 느려서 거의 못쓴다고 생각하면 된다.))
** Lisbigger 알고리즘을 간단하게 기억하고 넘어가면, A[j .. n]에서 A[i] 값보다 큰 값들을 선택해 recursion 하는 알고리즘

그럼 이것을 Dynamic Programing을 통해 풀어보자.
- LISbigger(i,j)를 저장하기 좋은 자료구조는 2차 배열이다.
- i는 [0 ... n], j는 [1 ... n] 범위를 가진다. 

테이블 채우는 순서? j는 n부터 1까지 역순으로, i는 상관 없음. 

LIS 시퀀스구하기 알고리즘

- i는 [0 ... n], j는 [1 ... n] 범위를 가진다.     >>  n² 공간
- 안쪽 for문 n, 바깥 for문 n                         >>  n² 시간
   >> O(n²)의 공간과 O(n²) 시간이 필요하다.


② LIS 길이 구하기

LIS 길이구하기 알고리즘

- 배열 LISfirst[1 .. n]에 저장(= 총 n개의 배열/sub-problem)   >>  n 공간
- 안쪽 for문 n, 바깥 for문 n                                                     >>  n² 시간
  ** return 값은 LISfirst[0]-1이다.       // 구한 길이에서 A[0] = -∞는 빼준다.
   >> O(n)의 공간과 O(n²) 시간이 필요하다.


③ Subset Sum
input : set X of positive integers and target integer T
output : true or false

SubsetSUM 알고리즘

X라는 배열은 이미 고정되어있다고 가정. 
SS(i, t) = {   true   if  t=0                            }
               {   false   if  t<0 or i>n and t>0    }
               { SS(i+1,t)∨SS(i+1, t-X[i])   나머지 경우 }


// 다이나믹

- 저장하기에 좋은 자료구조는 2차 배열(i와 t의 범위 : 1≤i≤n,  0≤t≤T)
- S[i, t]를 계산하기 위해 S[i+1, *]가 필요하다.
 >> 행은 아래에서 위로 (n to 1), 각 행에서는 아무 순서나

S[n+1, 0] <- True                              // base-case for t <- to T          S[n+1, t] <- false  for  i <- n  downto  1                      // 거꾸로 감소하면서       S[i,0] = True           for  t<- 1   to   X[i]-1                 //점화식의 세 번째의 경우 //for문은 T번               S[i,t] <- S[i+1, t]        for  t<- X[i]   to    T                    // 둘 중 하나를 리턴해준다.               S[i,t] <- S[i+1, t]∨S[i+1, t-X[i]]  return S[1,T]

- 2차 배열(1≤i≤n,  0≤t≤T)    >> n² 공간
- 안쪽 for문 T, 바깥 for문 n    >> nT 시간
** 원래 코드의 시간 복잡도는 O(2²)인데, Dynamic Programming을 통해 구한 O(nT)를 보면 O(2²) 보다 더 빨라 보인다. 하지만 그렇지는 않다. t가 T보다 더 큰 값만큼 돌아간다고 가정하면, 시간 복잡도는 2² 보다 더 커진다. 따라서 다이나믹 프로그래밍을 한다고 항상 빨라지는 것은 아니다.


다이나믹 프로그래밍
- 테이블을 통해 반복을 피하는 smart Recursion 방식이다.
- 재귀를 사용하는 것보다 속도가 빠르다.
- 가장 어려운 부분은 부분 문제 설정하는 것이다. -> 점화식 설정
- 부분 문제에 대한 올바른 점화식(어떻게 계산할 것인가)을 찾고 정의를 선언해라.