[알고리즘 | 자료구조] 그리디 알고리즘(Greedy Algorithm)

그리디 알고리즘(Greedy Algorithm)

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

예시)

다음 중 가장 큰수를 고르라고 한다면 그리디 알고리즘은 12 -> 6 을 선택한다.
결과를 봤을 때 최적의 수는 아니지만 모든 노드를 거치지 않아 계산속도가 빠르다는 점을 지녔다.

문제 해결 방법

• 선택절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택한다.
• 적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사한다.
• 해답검사(Solution Check) : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택절차로 돌아가 위의 과정을 반복

사용하는 문제

• 활동 선택 문제
• 거스름돈 문제
• 최소 신장 문제
• 제약조건이 많은 대부분의 문제
• 다익스트라 알고리즘

=> '가장 큰 순서대로' , '가장 작은 순서대로' 와 같은 기준이 있으면 그리디이다..