[알고리즘개념] 다이나믹 프로그래밍

피보나치 함수

재귀함수

시간복잡도 O(2^n)

def fibo(x):
    if x == 1 or x == 2:
        return 1
    return fibo(x-1) + fibo(x-2)

다이나믹 프로그래밍

조건
1. 큰 문제를 작은 문제로 나눌 수 있다.
2. 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다

메모이제이션(Memoization)

• 다이나믹 프로그래밍을 구현하는 방법 중 한 종류
• 한 번 구한 결과를 메모리 공간에 메모해 두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법
• 캐싱(Caching)이라고도 한다.

재귀함수 - 탑다운(Top-Down) 방식

시간복잡도 O(N)

# Memoization 하기 위한 리스트
d = [0] * 100

def fibo(x):
    if x == 1 or x == 2:
        return 1
    # 이미 계산한 적 있는 문제라면 그대로 반환
    if d[x] != 0: 
        return d[x]
    d[x] = fibo(x-1) + fibo(x-2)
    return d[x]

반복문 - 보텀업(Bottom-Up) 방식

# DP 테이블(결과 저장용 리스트)
d = [0] * 100

d[1] = 1
d[2] = 1
n = 99

for i in range(3, n+1):
    d[i] = d[i-1] + d[i-2]