메모리를 적절히 사용하여 수행 시간 효율성을 비약적으로 향상시키는 방법.
이미 계산된 결과는 별도의 메모리에 저장하여 다시 계산하지 않는 방식.
일반적으로 두 가지 방식 (탑다운 / 보텀업) 으로 구성된다.
다이나믹 프로그래밍은 다음의 조건을 만족할 때 사용할 수 있다.
1. 최적 부분 구조(Optimal Substructure)
큰 문제를 작은 문제로 나눌 수 있으며 작은 문제의 답을 모아 큰 문제를 해결한다.
2. 중복되는 부분 문제(Overlapping Substructure)
동일한 작은 문제를 반복적으로 해결한다.
피보나치 수열은 대표적인 다이나믹 프로그래밍 예시문제이다.
1,1,2,3,5,8,13...
이런식으로 나열되는 수열로 다음과 같은 점화식으로 나타낼 수 있다.
def fivo(n):
if( n == 1) or (n == 2):
return 1
return fivo(n-1)+fivo(n-2)
print(fivo(6))
# 출력
8
하지만 이렇게 구현하면 수를 줄여가며 함수를 호출할 때마다 계산을 다시 하게 된다.
ex) fivo(6)라면
이처럼, n을 호출하면 2, 1이 될때 까지 반복호출 및 계산을 수행한다.
다이나믹 알고리즘 개념을 생각하면 한번 계산을 수행한 것은 기록해놓고 함수가 호출될 때 계산된 값이 있다면 그 값을 사용하여 구현할 수 있다.
---------탑다운 방식----------
# 계산 결과를 담을 리스트 작성
check = [0]*20
def fivo(n):
if( n == 1) or (n == 2):
return 1
if ( check[n] != 0 ):
return check[n]
check[n] = fivo(n-1)+fivo(n-2)
return check[n]
print(fivo(6))
---------보텀업 방식----------
check = [0] * 20
check[1] = 1
check[2] = 1
n = 6
for i in range(3,n+1):
check[i] = check[i-1] + check[i-2]
for j in range(1,n+1):
print(check[j])
이렇게 다이나믹 알고리즘을 활용하면 다음과 같이 구현하여 시간복잡도를 줄일 수 있다.