동적계획법(DP)
- 상향식 접근
- 최하위 해답을 구하고, 해당 결과값을 이용해 상위 문제 해결
- Memoization 기법 사용 (이전 계산값 저장하는 기법)
- 문제를 쪼갤 때, 부분 문제 중복(재활용) (ex> 피보나치 수열)
분할 정복 (divide & conquer)
- 하향식 접근
- 상위의 해답을 구하기 위해, 아래로 내려가면서 하위의 해답 구함
- 재귀함수로 구현
- 문제를 쪼갤 때, 부분 문제 중복 X (ex> 병합 정렬, 퀵 정렬)
- Memoization 기법 사용 X
'코딩테스트' 카테고리의 다른 글
| 알고리즘 풀이 블로그 (0) | 2020.07.15 |
|---|---|
| 코딩인터뷰완전분석 - 알고리즘 설계의 5가지 접근법 (0) | 2020.06.12 |
| 백트래킹, N Queen (0) | 2020.02.17 |
| DFS, BFS (0) | 2020.01.23 |
| 코테 에러 분석 (0) | 2020.01.07 |