Greedy 알고리즘

탐욕 알고리즘

➡️ 최적의 해가 아닐 때도 있음!!

Greedy 알고리즘

탐욕 알고리즘

: 선택의 순간마다 당장 눈앞에 보이는 최적의 상황 만을 쫓아 최종적인 해답에 도달하는 방법

• 탐욕 알고리즘 문제 해결 방법

  • 선택 절차

    현재 상태에서 최적의 해답 선택

  • 적절성 검사

    선택된 해가 문제의 조건을 만족하는지 검사

  • 해답 검사

    원래의 문제가 해결되었는지 검사하고 해결되지 않았다면 선택 절차로 돌아가서 반복

• 탐욕 알고리즘 적용 가능한 문제의 조건

  • 선택 조건

    앞의 선택이 이후의 선택에 영향을 주지 않음

  • 최적 부분 구조 조건

    문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성됨

** 참고 :*

[알고리즘] 탐욕 알고리즘(Greedy Algorithm) - 하나몬

[알고리즘] 그리디(Greedy) 알고리즘과 예제 (파이썬)