동적 계획법(Dynamic Programming)

• 복잡한 문제를 간단한 여러 개의 하위 문제로 나누어 풀고 그 결과를 기록하고 이용해 문제를 해결하는 알고리즘
• 부분 문제 반복과 최적 부분 구조를 가지고 있는 알고리즘을 일반적인 방법에 비해 더욱 적은 시간 내에 풀 때 사용
• 재귀와 비슷하지만 그 결과를 기록하고 이용한다는 점에서 다름

메모이제이션(Memoization) : 결과를 기록하는 것
겹치는 부분 문제(Overlapping Subproblem) : 문제를 쪼갤 수 있는 구조

피보나치 수열 - 동적 계획법

1. 메모용 데이터를 만든다. 처음 값인 Fibo(1), Fibo(2) 는 각각 1씩 넣어서 저장해둔다.
2. Fibo(n) 을 구할 때 만약 메모에 그 값이 있다면 바로 반환한다.
3. Fibo(n) 을 처음 구했다면 메모에 그 값을 기록한다.


# 기록을 위해 dictionary 사용
memo = {
    1: 1, # Fibo(1) 의 값은 1이라고 기록해둔다.
    2: 1  # Fibo(2) 의 값은 1이라고 기록한다.
}

fibo(3) 을 찾아와라!

1. memo[3]이 있는지 본다.
2. 없으니까 fibo(2) + fibo(1) 을 구해야 한다.
3. 그러면 memo[2] 와 memo[1] 이 있는지 찾아본다.
4. 있으니까 그 값을 가져온 뒤 더해서 fibo(3) 을 만든다.
5. memo[3] 에 fibo(3) 을 기록한다. 

input = 100     # Fibo(100) = Fibo(99) + Fibo(98)

# memo 라는 변수에 Fibo(1)과 Fibo(2) 값을 저장해놨습니다!
memo = {
    1: 1,
    2: 1
}

def fibo_dynamic_programming(n, fibo_memo):
    if n in fibo_memo:						# 100이 있으면 그대로 꺼내옴
        return fibo_memo[n]

    nth_fibo = fibo_dynamic_programming(n-1, fibo_memo) + fibo_dynamic_programming(n-2, fibo_memo)
    fibo_memo[n] = nth_fibo

    return fibo_memo[n]

print(fibo_dynamic_programming(input, memo))