항해99 TIL 3주차 - 18

동적 계획법(Dynamic Programming)

동적 계획법이란?
여러개의 하위문제들을 풀고 그 결과를 기록하여 다음에 똑같은 과정이 나왔을 때 이용하는 알고리즘이다.

결과를 기록하는것을 메모이제이션(Memoization)이라하며
문제를 쪼갤 수 있는 구조를 겹치는 부분 문제(Overlapping subproblem)이라 한다.

피보나치 수열

피보나치 수열이란 첫번째 항과 두번째 항이 1이며 그 뒤의 항이 첫번째 항과 두번째 항의 합인 수열이다.

즉, F(n) = F(n-2) + F(n-1)이라고 할 수 있다.

피보나치 수열은 반복문, 재귀함수, 메모이제이션 3가지로 구현 할 수 있는데 3가지 중에 메모이제이션이 대부분 성능이 좋은 편이다

피보나치 수열 메모이제이션 구현코드

memo = {1: 1, 2: 1}


def fibo(n):
    if n in memo:
        return memo[n]
    memo[n] = fibo(n - 1) + fibo(n - 2)
    return memo[n]