알고리즘
-
Greedy Algorithm(그리디 알고리즘)알고리즘 2020. 12. 13. 00:56
Greedy Algorithm optimization problem을 풀 때 사용 dynamic programming이 너무 과도할 때(복잡할 때) greedy로 더 쉽게 풀 수 있다. 현재 상황에서 최선의 답을 선택. 현재 상황의 최선이 전체의 최선이길 바라면서 푼다. Greedy choice property(앞의 선택이 이후의 선택에 영향을 주지 않는 조건)를 만족할 때 사용한다. 현재 상황에서는 최선이지만 전체에서 최선이라는 보장은 없다. greedy로 풀 수 있는 문제는 모두 dynamic programming으로 풀 수 있다. top-down 구조 (dynamic은 bottom up) ex) 가방채우기 문제, 허프만 코드, 크루스컬 MST, 프림 MST, SSSP Counting money 6...
-
Dynamic Programming (동적 계획법)알고리즘 2020. 12. 13. 00:55
문제 해결 방법의 종류 brute-force approach : 모든 경우에 대해서 다 계산하고 가장 좋은것을 택하는 방법. n이 커지면 너무 오래걸려 실행 불가능하다. divide and conquer approach dynamic programming approach greedy approach Dynamic Programming(DP) 주어진 문제를 하위문제로 나누어서 해결한다. 하위 문제가 서로 연관이 있을 때 사용 (divide and conquer은 서로 연관이 없을 때 사용) optimization problem(최적해를 구할 때) 를 풀 때 사용 (최적화문제 : 답이 여러개인 문제에서 가장 좋은 답을 찾는 문제 ex. 최단경로 문제) 모든 하위 문제를 풀고 그 결과를 저장해두어 그 결과를 ..