Greedy
탐욕 알고리즘(Greedy Algorithm)의 개념과 특징을 설명합니다. 매 순간 최적의 해를 선택하는 방식과 그 한계점을 이해하고, 실제 문제 적용 시 주의사항을 학습합니다.
개념:
매 순간 최적의 해라고 생각되는 것을 선택해 나아가며, 최종적인 해답에 도달한다!
쉽게 말해 나무만 보고 숲을 보지 못하는 것
조건이 있습니다
- 앞의 선택이 이후의 선택에 영향을 주지 말 것!
- 문제에 대한 최적해가 부분문제에 대해서도 최적해일 것!
★삽화 예시
마리오가 leaf 노드까지 가는데 가장 큰 값을 구하려면?
마리오가 모험을 시작했습니다
가장 첫번째 길목에서 슈퍼 나뭇잎이 4점이라 저걸 바로 택했습니다
슈퍼 나뭇잎을 택한 상황에서 그다음 제일 좋은 것을 비교해보니 불꽃이 최적의 해 입니다
탐욕 알고리즘의 한계
- 반드시 최적을 해를 구할 수는 없다.
- 최적의 해에 가까운 것을 구하는 방법 중 하나라 근사치 추정에 활용은 된다.
이 경우에는 마리오가 버섯(2점) → 별(5점)으로 가는게 전체 최적해가 됩니다!
참고
This post is licensed under CC BY 4.0 by the author.
