728x90
- Dynamic Programming
- Greedy
- Back Tracking
- Branch and bound
- Greedy는 반례가 있어서 적용 안되는 경우가 있다.
- 0-1 knapsack problem - Greedy가 적용되지 않는 경우 Dynamic Programming 을 쓴다.
- Dynamic Programming 이 적용되지 않을 때 BackTracking을 쓴다.
- Dynamic Programming 은 2^n의 부분집합을 검사하니까 오래걸리는데 이걸 Backtracking이 Tree 형태의
pruned state space tree 로 promising 하는 경우만 check 한다. - Backtracking 에서 발전된게 Branch and bound 이다.
그리디는 local 한 최적해를 구하고
그게 global 하게 최적한지는 우리가 증명해야하는거니까
n 인거고 backtracking 은 최악에 전체 부분집합
그리디가 global 하게 최적화된 해라는게 증명되면 그리디가 대부분 빠름
728x90
'Algorithm > Study' 카테고리의 다른 글
Swift - BFS iteration on Binary Tree (0) | 2020.07.09 |
---|---|
Swift 배열 처리 (1) | 2020.07.04 |
😈 Greedy & Prims Algorithm (feat MST) (0) | 2020.06.18 |
01. 배열과 문자열 (0) | 2020.06.09 |
문제해결 전략 - 30. 최단 경로 알고리즘 (3) | 2020.05.29 |
댓글