-
탐욕 Greedy AlgorithmToday_I_Learned/Algorithm 2023. 4. 16. 23:28
개념
현재 상황에서 가장 좋아보이는 값을 사용하는 것. 이전/미래 상황 고려 X
전제
Optimal Substructure Property 충족 (Optimal Substructure Property 란 현재 상황에서 최선으로 보이는 선택지의 하위 선택지 역시 최선의 선택지인 속성을 의미)
특징
Optimal Substructure 가 충족되지 않을 땐 항상 최고의 결과가 나오는 것은 아님.(최고의 결과 근사치 추출 가능) 하지만 계산 속도는 빠르므로 근사치가 필요한 경우에 사용 가능 Ex) 네비게이션
예시
- 0-1 knapsack
- 동전 최소 개수 거스름 돈
- MST 탐색 (PRIM, Kruskal)
'Today_I_Learned > Algorithm' 카테고리의 다른 글
99클럽 코테 스터디 5일차 TIL: 배열, Leetcode 1476. Subrectangle Queries (0) 2024.06.15 99클럽 코테 스터디 4일차 TIL : Graph, 프로그래머스, 순위 (0) 2024.06.13 99클럽 코테 스터디 3일차 TIL: Graph, Dijkstra, 프로그래머스, 가장 먼 노드 (0) 2024.06.12 99클럽 코테 스터디 1일차 : 그리디, 구명보트(프로그래머스) (0) 2024.06.06 MST 탐색(프림 Prim / 크루스칼 Kruskal) (0) 2023.04.16