동적 계획법(Dynamic Programming)

1) DP란?

하나의 큰 문제를 작은 문제로 나누어 해결하는 기법

2) 사용 조건

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

메모이제이션: DP를 구현하는 방법 중 한 종류로, 한 번 구한 결과를 메모리 공간에 메모해두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법(캐싱)

3) 대표적인 예시(피보나치 수열)

#한 번 계산된 결과를 메모이제이션 하기 위해 리스트 초기화
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]

print(fibo(99))