이전시간에서는 Dynmaic programming(DP)에 대해서 배워보았으니 문제를 풀어보는 시간에 대해서 가져보겠습니다.

DP문제를 풀기위한 Framework에 대해서 이는 왠만하게 모든 방법에서 풀수 있기때문에 단계별로 이해하면서 문제를 풀어보도록 하겠습니다.

아래그림처럼 처음 풀 문제는 Climbing Staris의 문제입니다. 이 문제는 top-down(recursive)로 풀수 있는데요

이 문제의 경우에서는 한글말로 "계단오르기"문제로써 간편하게 풀수 있는 문제입니다.

문제 : n step을 통해서 정상에 올라갈수 있는데 정상에 오르기 위해서는 몇가지의 방법을 통해서 올라갈수 있는지??
조건 : 한번 올라갈때마다 반듯이 1,2칸만 갈 수 있음.
예시 : n=3이라면 (1,1,1),(1,2),(2,1)로 총 3가지의 방법으로 올라갈수 있음.

이 문제를 풀기 위해서는 우리가 이전에 공부하였던 DP를 활용하여 문제를 풀어 봅시다.

DP를 적용하기 위해서 state라는 개념이 있는데요.

state의 경우는 지금의 현제 상태에 대해서 설명할수 있는 변수의 집합이라고 됩니다. 위의 그림처럼 계단 오르기를 할때 step이 3이라고 하면 3가지의 방법들로 풀수 있는데요 (ex) n=3이라면 (1,1,1),(1,2),(2,1))

이때 집합들의 값들에 있는 변수들을 state variables라고 부릅니다.

이때 state variable에서 연관(relevant)이 있는 요소는 하나만 있는데 이 relevant 에 대해서는 다음에 설명하도록 하겠습니다 .

이러한 문제를 DP의 문제는 3가지의 조건을 반듯이 가지는데요 이러한 Framework에 대해서 알아보도록 하겠습니다.

Framework

1. function이나 data structure들은 모든 state 마다 계산이 되어져야 합니다.
   위의 문제로 예시로 들어보았을떄 dp(i)를 function으로 잡았을때 이 dp(i)는 $i^{th}$번째에 방법들에 대해서 나와야 합니다.
2.  점화식/재귀식 (recurrence relation)은 다른state에 이행되어진다.
   마찬가지로 위의 문제처럼 dp(30)으로 간다고 하였을떄 수많은 state variables이 집합으로 되어있을겁니다. 이떄 dp(30)은 이전의 29th과 28th에 도착되어졌을때 1,2의 계단만 올라가면 되는 문제로 풀수 있습니다.
   따라서 이론적으로 recurrence relation로 풀수 있으므로 dp(i) = dp(i-1) + dp(i-2)로 풀어집니다
3. 초기 값들은 recurrence relation은 무한하게 되어지지 않도록 방지하는 역할을 합니다.
   dp(i) = dp(i-1) + dp(i-2)라는 수식 자체는 반복하다보면 negative값까지 가게 되어서 무한하게 수식이 되어집니다.
   그렇기 때문에 이를 방지할 수 있는 base가 되는 값을 가져야 하며 위의 문제에서는 dp(1)=1, dp(2)=2라는 초기 값을 설정이 되어짐을 볼수 있습니다.
   이를 통해서 negative로 가는 것을 막을수 있으며 위의값들을 풀어낼 수 있습니다.

Example Implementations

그렇다면 2가지의 문제로 접근해서 풀어보도로 하겠습니다. 

Top-down

class Solution: 
	def climbStaris(slef, n: int) -> int: 
    	def dp(i): 
        	if <= 2: 
            	return i 
                
            return dp(i-1) + dp(i-2)
    	return dp(n)

위의 방법은 $O(2^n)$의 방법으로 구성이 되어지지만 top-down 방식의 기본인 memoization이 없는 것을 볼 수 있습니다. 이 방법의 time complexity를 줄이기 위해서 memoization를 사용하게 되면 아래와 같습니다. 

class Solution:
    def climbStairs(self, n: int) -> int:
        def dp(i):
            if i <= 2: 
                return i
            if i not in memo:
                memo[i] = dp(i - 1) + dp(i - 2)
            
            return memo[i]
        
        memo = {}
        return dp(n)

이렇게 되면 $O(n)$로 줄어드는 것을 볼 수 있다. 

bottom-up 

이 방법을 적용해보자 

class Solution:
    def climbStairs(self, n: int) -> int:
        if n == 1:
            return 1
            
        # An array that represents the answer to the problem for a given state
        dp = [0] * (n + 1)
        dp[1] = 1 # Base cases
        dp[2] = 2 # Base cases
        
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2] # Recurrence relation

        return dp[n]

위와 같은 방법으로 보았을떄 각자의 장단점이 있음으로 top-down, bootom-up의 방법을 적당히 사용하면된다. 

어찌보니 Leetcode 프리미엄이 1년치가 구독이 되어져버렸다.. (취소를 못한 나의잘못..)

여튼 그래서 이번에 공부를 좀 해보고자 한다.

Dynamic Programming(DP)에 대해서 공부한지가 너무 가물가물하니 예시 문제를 풀면서 Github에도 업로드도 하면서 복습하면 좋은 시간이 되어지지 않을까 싶다!

DP를 이해하기 앞서서 Recursion과 Greedy algorithm에 대해서 알아야하며 Big O와 hash tables에 대해서도 알아야 하며 잘 모를경우 Recursion먼저 배워야한다.

What is Dynamic Programming ?

DP가 무엇인가에 대해서 문게에 대해서 가능한 모든 방법을 탐색해서 해결하는 방식을 말하는데.. 이는 직관적으로 이해가 되지 않는다. 그래서 2가지의 특성을 가지면 이해할수 있는데 아래와 같다.

1. 여러번 재 반복해서 더 작은 문제로 풀수 있는 방법인가('overlapping subproblems')
2. 이러한 overlapping subproblems이 최적의 방법으로 풀수 있는가 ('optimal substructures')

대표적인 예시의 문제로 피보나치 수열의 문제가 있는데 이는 DP에 대해서 설명을 하여준다. 처음 시작은 0,1로 시작을 하고 다음에서는 이전에 정의되었던 0,1의 합으로 다음 수가 만들어지는 원리이다.

위의 그림처럼 $n^{th}$의 경우에서는 피보나치 수를 $F(n)$으로 정의를 하는데 방법을 subproblems로 나눌수 있다.즉 $F(n-1) + F(n-2)$로 나뉘어진다. 그리고 두 수식은 optimal substructure로 표현이 되어지는 $F(n) = F(n-1) + F(n-2)$로 더해진다. 이 subproblems은 overlapping이 되어진다.

위와 같은 방법은 greedy problems과 유사한데 optimal substructure를 가진다는 점이다. 하지만 overlapping(겹치지) 하지는 않다. 다른 방법중에 하나인 divide and conquer의 방법도 비슷하지만 overlapping하지 않는 점이 다르다고 볼 수 있다.

Top-down and Bottom-up

이러한 DP는 2가지의 방법으로 풀수 있으며 아래처럼 알려져있다.

1. bottom-up 은 tabulation
2. top-down은 memoization

Bottom-up(Tabulation)

이 방법의 경우에서는 가장 base case에서부터 시작되는 방법이다. 피보나치로 예시로 들었을 때 $F(0)=0, F(1)=1$를 사용하여 $F(3)$을 만들고 나중에 $F(n)$가지 만드는 과정을 말한다.

// Pseudocode example for bottom-up

F = array of length (n + 1)
F[0] = 0
F[1] = 1
for i from 2 to n:
    F[i] = F[i - 1] + F[i - 2]

Top-down (Memoizaion)

이 방법의 경우는 recursion사용하고 효과적으로 memoization을 만들어진다. 예시로 $n^{th}$의 경우 $F(n)$의 피보나치 수를 가지며 이는 $F(n-1), F(n-2)$로 구성이 되어지는것을 찾을 수 있다. 이는 recusive 패턴을 찾아 $F(0) = F(1) = 1$이라는 것을 찾을 수 있다.
반복적인 패턴으로 인해서 $F(100)$같의 값을 찾기 위해서는 이전의 $F(99), ... F(0)$까지 값을 계산해야되는데 이는 비효율적이다. 결국 빠르게 찾기 찾기 위해서 memoize의 결과를 활용하고 이를 memoizion이라고 불린다.

**memoizion**는 결과의 값을 hashmap, array에 저장을 해 놓고 같은 값이 나오면 return을 하는 방법이다. 

코드는 아래와 같다.

// Pseudocode example for top-down

memo = hashmap
Function F(integer i):
    if i is 0 or 1: 
        return i
    if i doesn't exist in memo:
        memo[i] = F(i - 1) + F(i - 2)
    return memo[i]

둘중에 누가 좋나?

• bottom up의 경우에서는 runtime이 빠르다. 왜냐! recursive를 하지 않기 때문에
• top-down은 더 쉽게 코드 작성이 가능하며 recursion을 사용하지 않음.

When to Use DP

특히나 DP의 문제에서는 코테에서 문제를 푸는 방법을 찾는데 시간을 절반을 소요하기 때문에 앞서 말한 2가지의 특징이 중요합니다.

1. overlapping subproblems : 작은 문제를 여러번 사용이 가능해야됨
2. optimal substructure : 중첩되는 즉 overlapping의 문제를 최적의 방법으로 풀어야한다.
   이렇게 말하면 뭔가 느낌적으로 감이 안올것이기 때문에 좀더 쉽게 몇가지의 특징에 대해서 말해보겠습니다.

First characteristic

어떤 문제에 있어서 optimum value를 요구합니다.
예로들어서 가장 cost가 적게드는 maximum한 값, 몇가지의 방법이 있는가..등등
모든 방법들이 위의 예제같이 나타나진 않지만 공통된 특징을 가지고 있습니다.
첫번째의 방법은 설명한 방법을 무조건 DP로 풀진 않아도 됩니다. (Greedy algorithm 으로도 풀수 있음)

Second characteristic

DP의 다른 특징중에 하나는 미래의 decisions이 과거의 Decision에 영향을 가지는 특징을 가지고 있습니다.
마치 나비효과처럼 처음의 값이 나중에 값의 영향을 미치는것입니다.
이 특징은 greedy algorithm에서는 적용할수 없는 문제이기때문에 DP로만 풀수 있습니다.

0. 예시 문제 : Climbing Stairs

1. 예시 문제 : House Robber  (링크 : 풀이)

2. 예시 문제 : Longest Increasing Subsequence  (링크 : 풀이)