동적 프로그래밍

정의

• 큰 문제를 작은문제로 나누고 작은문제의 정답값을 통해 큰 문제를 푸는 문제 해결방법이다.
• 작은 문제가 반복해서 일어나고 같은 문제는 구할때마다 정답이 같아야한다.
• 작은 문제의 답을 반복해서 구하는 것을 피하기 위해 memoization을 사용한다.

구현

Bottom-up

• 작은 문제부터 차근차근 답을 구해나가는 방법이다.
• 보통 반복문을 통해 이를 구현한다.

Top-down

• 큰 문제부터 차근차근 답을 구해나가는 방법이다. 큰 문제를 풀 떄 작은 문제가 아직 풀리지 않았다면 그제서야 작은 문제를 해결하는 방법이다.
• 보통 재귀함수를 통해 이를 구현한다.

대표적인 문제 : 피보나치 함수

문제 정의

• 다음수열 = 이전수열 + 두단계 전 수열의 합이라는 점화식을 가진 순열

구현

• 작은 문제를 다음수열 = 이전수열 + 두단계 전 수열의 합 로 나눌 수 있다. n=0 일때 0, n=1 일때 1이 정답값임을 이용하면 모든 n에 대해 정답값을 구할 수 있다.
• 구현방법은 Bottom-up 과 Top-down 두가지 방법이 있다.

코드

• Bottom-up

def fibo_bottom_up(n):
    if n<=1: return n

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

if __name__ == '__main__':
    n = int(input())
    print(fibo_bottom_up(n))

• Top-down

def fibo_top_down(n):
    if memo[n] > 0 : return[n]

    if n <= 1 : 
        memo[n] = n
        return memo[n]

    else: 
        momo[n] = fibo_top_down(n-1)+ fibo_top_down(n-2)
        return meno[n]

if __name__ == '__main__':
    memo = [0 for _ in range(100)]
    n = int(input())
    print(fibo_bottom_up(n))