정의
- 탐욕법은 문제를 해결하는 과정에서 그 순간 마다 최적의 결정을 하는 방식으로 진행하여 최종 결론에 도답하는 문제 해결 방식.
- 그 순간의 상황에서 가장 좋다고 생각하는 걸 선택하기 때문에 가장 좋은 결과를 보장하는 것은 아니다.
- 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘
- 동적 프로그래밍을 대체하는 것은 아니며, 같이 쓰이며 보완하는 개념
- 예시 사진
이 그림과 같이 실질적으로 순간의 상황마다 최적의 값을 구하는 그리디 알고리즘으로 따라가보면 11의 값을 얻게 되지만, 실제의 최적의 답은 99이다. 이와 같이 가장 좋은 결과를 보장하는 것이 아님을 알 수 있다.
활용되는 문제
- 활동 선택 문제
- 각각의 활동들은 시작시간과 종료시간이 있다.
- 한 사람이 최대한 많이 할 수 있는 액티비티의 수와 액티비티의 종류를 구하는 것이다.
- 직관적으로 생각하면 활동들이 빨리 끝나는 걸 고르면 된다.
- 분할 가능 배낭 문제
- 물건이 무거울 경우 쪼개 넣을 수 있다.
- 즉, 무게가 초과할 것 같으면 물건을 쪼개서 일부만 넣을 수 있다.
- 부피 (또는 무게) 대비 가치가 높은 물건들부터 담으면 되기 때문에 탐욕 알고리즘에 속한다.
그리디 알고리즘을 사용한 알고리즘
- 프림 알고리즘
- 다익스트라 알고리즘
출처
'공부' 카테고리의 다른 글
| [python] list 안에서 for문과 if 조건문 이용하기 (list comprehension) (0) | 2021.01.10 |
|---|---|
| [crawling] selenium을 이용할 때 생기는 session not created 오류 해결 (0) | 2020.04.04 |
| [python] 모듈과 패키지 (0) | 2020.03.29 |
| [선형대수] Norm이란? (L0, L1, L2 Norm) (0) | 2020.03.23 |
| [자료구조] 해시(Hash), 해시테이블(Hash table),해싱(hashing) 이란? (0) | 2020.03.13 |