알고리즘. 탐욕 알고리즘(Greedy Algorithm) 알아보기

🌟 탐욕 알고리즘이란?

탐욕 알고리즘은 현재 상황에서 가장 최선의 선택을 하는 알고리즘이다.

여기서 가장 최선의 선택이란, 결과 값이 아닌 현재 값의 최대치를 말함!

예를 들어, 트리가 있을 때 일정한 경로를 타고 100의 수를 얻을 수 있고 그게 트리의 최대라면 우리가 보기에 그게 최선의 선택이지만, 탐욕 알고리즘을 사용하면 그 중간에 100으로 가는 경로가 아닌 다른 경로를 선택할 수도 있음! 왜냐면 자매 노드와 비교해서 가는 경로 중에 더 큰 수쪽으로 틀기 때문!

경로가 2 - 3 - 100이고 5 - 7 - 9 이렇게 되어 있다면 2와 5 중에서 5를 선택해서 100을 못 얻는다는 뜻 ~! 자세한 건 참조 블로그 그림 참고.

🌟 탐욕 알고리즘 조건

1. 선택은 항상 안전하다는 게 보장되어야 함. 이 선택으로 인해 전체 문제의 최적해를 반드시 도출할 수 있어야 한다는 것! (위 예시처럼 된다면 탐욕 알고리즘 사용하면 안됨)
2. 문제에 대한 최종 해결 방법이 부분 문제에도 적용되어야 함

탐욕 알고리즘 문제로는 거스름돈, 활동 선택 등이 있다.

contea95.log