6. 동적프로그래밍

 

동적 프로그래밍(DP)은 문제를 작은 부분 문제로 나누고, 각 부분 문제의 결과를 저장해 중복 계산을 피하는 알고리즘 기법입니다. 최적 부분 구조와 중복된 부분 문제가 있는 문제에서 효과적입니다. 이를 푸는 방법은 두 가지입니다:

1. 탑다운 방식(메모이제이션): 재귀적으로 문제를 풀고, 계산된 값을 저장해 중복 계산을 방지.
2. 바텀업 방식(테이블링): 작은 문제부터 해결해 큰 문제를 푸는 반복문 방식.

예시로는 피보나치 수열, 최단 경로 문제, 배낭 문제 등이 있으며, 중복된 계산을 피하고 효율성을 높입니다.

 

 

피보나치수열

 

 

•따라서, 이미 계산한 값들을 적어 놓고 재사용한다면 (Memoization), 효율을 크게 올릴 수 있을 것

 

def dyn_fib(n):
F = list()
F[0] = 0
F[1] = 1

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