[Algorithm] 탐욕 알고리즘

 

Greedy Algorithm

 

문제를 해결하는 과정에서

그 순간순간 최적이라고 생각되는 결정을 하는 방식

 

>> 지역적으로 최선의 선택을 하여 전체적으로 최적의 결과를 도출하겠다!

 

 

탐욕적 선택 속성

현재 선택이 그 이후의 선택에 영향을 주지 않음

 

최적 부분 구조

큰 문제를 작은문제로 나눌 수 있으며 작은 문제의 방법으로 큰 문제를 해결할 수 있음

 

 

▼ 문제점 ▼

 

제일 빠른 길은 1 → 3 → 5 인데

그리디 알고리즘을 적용하면 오른쪽과 같은 문제점이 생길 수 있음

 

 

 

 

▶ Greedy Argorithm 문제 중에 젤 유명한 문제

▼ 함수 안에 뭐 써야할까

▼ 함수 안에 뭐 써야할까

>> 400을 리스트에 추가해도 결과는 6이 나옴

>> 탐욕 알고리즘의 문제점을 보여줌