greedyAlgorithm
-
탐욕 Greedy AlgorithmToday_I_Learned/Algorithm 2023. 4. 16. 23:28
개념 현재 상황에서 가장 좋아보이는 값을 사용하는 것. 이전/미래 상황 고려 X 전제 Optimal Substructure Property 충족 (Optimal Substructure Property 란 현재 상황에서 최선으로 보이는 선택지의 하위 선택지 역시 최선의 선택지인 속성을 의미) 특징 Optimal Substructure 가 충족되지 않을 땐 항상 최고의 결과가 나오는 것은 아님.(최고의 결과 근사치 추출 가능) 하지만 계산 속도는 빠르므로 근사치가 필요한 경우에 사용 가능 Ex) 네비게이션 예시 0-1 knapsack 영상 : https://www.youtube.com/watch?v=ZeZgP4vsUuw&list=PL9mhQYIlKEhdvKFh-wVpDuihNQv6C1gSy&index=19 ..