boj 110001 그리디 1. 그리디로 항상 최적해를 구할 수 있다면, 그리디는 dp보다 훨씬 빠르다. (그리디로 풀리면 보통 dp로도 풀린다) 2. 시공간 제약으로 인해 최적해를 찾는 것이 극히 제한되는 경우, 근사해를 찾아준다. ps에선 1번 용도로만 사용된다. 근사해 찾기는 조합탐색이나 메타휴리스틱을 사용한다. 탐욕적 선택 속성(greedy choice property) : dp처럼 답의 모든 부분을 고려하지 않고 탐욕적으로만 선택하더라도 최적해를 구할 수 있는 속성 최적 부분 구조(optimal substructure) : dp처럼 부분 문제의 최적해에서 전체 문제의 최적해를 만들수 있는지 ->대부분 자명해서 증명할 필요가 없는 경우가 많다. 하지만 예외 존재 알고리즘이 위 두 속성을 만족하는지 검증해야 한다. 1. 활동.. 2019. 12. 18. 이전 1 다음
