다이나믹 프로그래밍

메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법
이미 계산된 결과(작은 문제)는 별도의 메모리 영역(리스트나 딕셔너리로, 일종의 캐시 역할)에 저장하여 다시 계산하지 않도록 함
한 번 해결한 문제의 답을 메모리에 저장하여 같은 문제를 중복해서 풀지 않도록 하여 효율을 높임
일반적으로 탑다운(재귀함수를 통해 점점 작게) / 보텀업(반복문을 통해 점점 크게) 두 가지로 구현
점화식을 먼저 떠올리고 -> 이를 코드로 구현

조건

최적 부분 구조(Optimal Substructure)

큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아서 큰 문제를 해결할 수 있음

중복되는 부분 문제(Overlapping Subproblem)

동일한 작은 문제를 반복하여 해결해야 답을 구할 수 있음

메모이제이션(Memoization)

다이나믹 프로그래밍을 구현하는 방법 중 하나로, 한 번 계산한 결과를 메모리 공간에 메모하는 기법
일종의 캐싱
같은 문제를 호출하면 메모했던 답을 그대로 가져옴
이전에 계산된 결과를 일시적으로 기록해 놓는 넓은 개념을 의미하며, 다이나믹 프로그래밍에 국한된 개념은 아님

예시

피보나치 수열

n번째 수 = n-1번째 수 + n-2번째 수인 수열

1,1,2,3,5,8,13,21,34,55,89...

점화식으로 표현하면 an = an-1 + an-2, a1=1, a2=1
이 점화식을 다이나믹 프로그래밍 없이 단순 재귀 함수로 구현하면 같은 부분 문제를 중복히여 여러번 풀게 되어 시간적 비효율이 발생(O(2N)(지수))

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

print(fibo(4)) # 수열의 4번째 값(a4) 구하기

-> 메모이제이션을 이용하여 구현(탑다운/보텀업)할 경우의 시간 복잡도는 O(N)

• 탑다운 방식(재귀함수로 구현)

# DP 테이블의 길이 설정은 구할 값에 맞게 설정
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)) # 수열의 99번째 값(a99) 구하기

• 보텀업 방식(반복문으로 구현)

# 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]

print(d[n])