동적 프로그래밍(Dynamic Programming)이란?

동적 프로그래밍(Dynamic Programming)이란 복잡한 문제를 간단한 여러 개의 문제로 나누어 해결하는 방법을 의미한다.

여러 개의 문제로 나누어 해결한다는 점에서 분할 정복(Divide and Conquer)과 유사해 보이지만, 동적 프로그래밍의 경우,

간단한 문제들이 반복적으로 일어난다는 점에서 차이가 있다. 즉, 동적 프로그래밍은 간단한 문제들을 한 번만 해결하고

그보다 복잡한 문제를 풀어나갈 때 똑같은 간단한 문제가 다시 나타나면 그 결과 값을 이용해해결하는 방법이다.

이때, 간단한 문제의 결과 값을 기억하여 반복 수행을 제거하는 과정을 메모이제이션(Memoization)이라고 한다. 

 

동적 프로그래밍을 사용하려면 아래 두 가지 조건을 만족해야 한다.

1. 부분 문제 반복(Overlapping Subproblem)
   : 간단한 부분 문제들이 반복적으로 등장해야 한다.

2. 최적 부분 구조(Optimal Substructure)
   : 간단한 부분 문제에서 구한 최적의 결과로 복잡한 문제의 최적의 결과를 구할 수 있어야 한다.

 

▶ 구현 코드

memo = [0 for i in range(101)]

def memoization_fibo(N):
    memo[0] = memo[1] = 1
    
    if N < 2:
        return memo[N]
    
    for i in range(2, N + 1) :
        memo[i] = memo[i - 2] + memo[i - 1]

    return memo[N]

print(memoization_fibo(100))
print(memo)