동적 계획법 (Dynamic Programming)

정의

입력 크기가 작은 부분 문제들을 해결한 후, 해당 부분 문제를 활용하여 보다 큰 크기의 부분 문제를 해결하고, 최종적으로 전체 문제를 해결하는 알고리즘.

• 상향식 접근법 — 가장 최하위 해답을 구한 후 이를 저장하고, 해당 결과값을 이용하여 상위 문제를 풀어감
• Memoization — 이전에 실행했던 값을 저장하여 다음 계산에 사용

구현 — 피보나치 수열

점화식: F(n) = F(n-1) + F(n-2)

수열: [1, 1, 2, 3, 5, 8, 13, 21, 34, …]

def fibo(num):
    fibo_list = [0 for index in range(num + 1)]
    fibo_list[1], fibo_list[2] = 1, 1

    for index in range(2, num + 1):
        fibo_list[index] = fibo_list[index - 1] + fibo_list[index - 2]

    return fibo_list[num]