반응형
DP(Dynamic Programming)란?
문제에 대한 정답이 될 가능성이 있는 모든 해결책을 “체계적”이고 “효율적”으로 탐색하는 풀이법
- 완전 탐색의 경우 시간 복잡도(계속 함수를 두 개씩 호출함) : O(2^n)
ex) 피보나치 수열을 재귀함수로 풀 때
return fibo(n - 1) + fibo(n - 2)
Q. fibo(1), fibo(2) 등 하위 문제들이 fibo(8), fibo(7) 계산할 때 계속 해서 중첩해서 계산됨
→ 동적 프로그래밍(DP) 이용
하위문제 여러 개로 나눈 후 메모리에 계산 값을 넣어 향후 상위 문제에서 계산 하지 않고 꺼내 씀
→ 시간 복잡도가 O(2^n) → O(n)으로 감소
Top-Down 방식
memo = {}
def fibo(n):
if n == 1 or n == 2:
return 1
if n not in memo:
memo[n] = fibo(n - 1) + fibo(n - 2)
return memo[n]= 상위 문제 f(n) 부터 하위문제 f(1)로 접근
- Memoziation : Top-Down방식에서 메모리를 채워 나가는 것
Bottom-Up 방식
memo = {}
def fibo(n):
for i in range(3, n + 1):
memo[i] = memo[i - 1] + memo[i - 2]
return memo[n]
= 하위문제 f(1)부터 상위 문제 f(n) 접근
- Tabulation : Bottom-Up 에서 memo를 채워나가는 것
반응형