필독!!) DP (Dynamic Programming)

DP

• 처음 보면 dynamic programming이 무슨 뜻인지 감이 잘 안오는데, 쉽게 말하면 중복되는 과정은 재사용하겠다는 것이다. 큰 문제를 해결하는데 작은 문제들이 사용된다면, 이를 어디다가 저장해놓고 큰 문제를 해결하는데에 이용한다.
• 이 맥락에서 알 수 있듯이, 작은 문제의 결과를 저장해야 하므로 메모리를 추가적으로 사용한다.
• 그러나 생각해보자. 100이라는 문제를 푸는데 단계별로 1, 2, 3, ... , 98, 99가 필요하다고 한다면, 99까지의 결과를 어디다가 저장해두고, 99 → 100 이렇게 한단계만 푸는 게 효과적이지 않겠는가?? 그래서 메모리는 추가적으로 들지만 앞단계를 다 스킵할 수가 있으므로 시간을 많이 단축할 수 있다.

Memoization

• 위에서 설명했던, 메모리를 추가로 사용해서 저장하는 맥락을 Memoization이라고 불린다.
• 대표적으로, 피보나치 수열을 생각해보자. fibo(10) = fibo(9) + fibo(8)이다. 그럼 n = 9, 8일 때의 값을 저장해두었다면 이를 더하기만 하면 fibo(10)을 바로 구할 수가 있다.

구현

구현은 Bottom-up , Top-down 이렇게 2가지 방법이 있다. 둘중에 편한 방법으로 풀면 된다 !! 근데 경험상 bottom up으로 푸는 게 더 좋은 것 같다. 그러면 규칙을 발견하고, 일반식을 발견할 수 있는 것 같다. (내 경험이라 근거는 없음)

구현 - Bottom up

fibo(10)을 구한다고 하면, fibo(0)부터 차근차근 구해나가는 것이다. fibo(0), fibo(1), fibo(2) ..... fibo(10)

def fibo_bottoUp(n):
    if n<= 1:
        return n # fibo(0) = 0, fibo(1) = 1 이라는 뜻

    first = 0
    second = 1
    
    for i in range(0, n-1):
        next = first + second
        first = second
        second = next
    return next

구현 - Top down

fibo(10)을 구한다고 하면, fibo(10) = fibo(9) + fibo(8) 근데 fibo(9)를 모르면? 다시 재귀로 fibo(9) = fibo(8) + fibo(7) ,,,  이렇게 내려가는 것이다.

def fibo_topDown(n):
    if memoization[n] > 0:
        return memoization[n]

    if n <= 1:
        memoization[n] = n
        return memoization[n]
    else:
        memoization[n] = fibo_topDown(n-1) + fibo_topDown(n-2)
        return memoization[n]

memoization = [0] * 100 # 초기화

Tip

• 가장 작은 문제부터 차차 몇개만 구해보고, 일반화된 점화식을 발견하는 것.
• 점화식은 max, min을 사용하는 경우가 많다 !
• 처음에 memoization 초기화할 때, 입력값 범위 생각해서 초기화 하기 ! (런타임 에러 날 수 있음)