728x90
작은문제로 쪼개서 -> 값을 재활용하기
DP를 사용하면 재귀나 완전탐색보다 효율적으로 문제를 풀 수 있다
ex) 피보나치의 경우...
f(n) = f(n-1)+f(n-2)
재귀 사용시 복잡도: O(n^2)
dp 사용시 복잡도: O(n)
dp를 사용할수 있는 조건
1. 큰 문제를 작은 문제들로 나눌 수 있는가(동일한 작은문제들이 반복)
2. 작은 부분 문제의 값이 그것을 포함하는 큰 문제에서도 동일한가
dp에서 중요한것
- 점화식세우기
- memoization: 앞에서 계산한 값을 배열에 저장했다가 필요할 때 재사용
구현방법
top down
bottom up
728x90
'코테준비 > 알고리즘' 카테고리의 다른 글
| 유클리드 호제법 (0) | 2023.09.05 |
|---|---|
| 백트래킹 (0) | 2023.08.24 |
| #4963 섬의 개수 (0) | 2023.07.30 |
| #2178 미로탐색 (0) | 2023.07.27 |
| 2차원 리스트를 90도 회전하는 함수 (0) | 2023.07.08 |