반응형
다이나믹 프로그래밍
* 큰 문제를 작은 문제로 나눠서 푸는 알고리즘
* Dynamic은 아무 의미가 없다.
1. DP (중복O)
2. 분할 정복 : Divide & Conquer (D&C) (중복X)
overlapping subproblem : 부분문제가 겹치는 경우
-> 피보나치 수
optimal substrucure : 최적부분 구조
-> 문제의 정답을 작은 문제의 정답에서 구할 수 있다.
-> 서울 대전 대구 부산 갈 때, 대전에서 부산가는 빠른 길은 대구를 거쳐야 한다.
Top-down
Bottom-up
반응형
'코딩 테스트 > 알고리즘' 카테고리의 다른 글
| [알고리즘 파이썬] DFS/BFS (0) | 2021.02.24 |
|---|---|
| [알고리즘 파이썬] sort(), sorted() 차이 (0) | 2021.02.13 |
| [알고리즘 파이썬] input 속도 높이기 (0) | 2021.01.30 |
| [알고리즘 파이썬] 인접 행렬과 인접 리스트 (0) | 2020.11.08 |
| [알고리즘 파이썬] 위상 정렬 (0) | 2020.11.08 |