그리디 알고리즘

탐욕 알고리즘(Greedy Algorithm)이란?

• Greedy는 ‘탐욕스러운, 욕심 많은’ 이란 뜻이다.
• 탐욕 알고리즘은 말 그대로 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.
• 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법이다.
• 탐욕 알고리즘은 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.

탐욕 알고리즘 문제를 해결하는 방법

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

탑욕 알고리즘을 적용하려면 문제가 다음 2가지 조건을 성립하여야 한다.

1. 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
2. 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

탐욕 알고리즘을 일상 예시 

하나몬이 아르바이트를 하러 간 사이에, 안타깝게도 하나몬의 집에 도둑이 들었다.
도둑의 가방은 35kg까지의 물건만 담을 수 있고, 하나몬의 집에는 4개의 물건이 있다.

👉 도둑이 탐욕 알고리즘을 사용한다면?

1. 가방에 넣을 수 있는 물건 중 가장 비싼 물건을 넣는다.
2. 그다음으로 넣을 수 있는 물건 중 가장 비싼 물건을 넣는다.
3. 이 과정을 반복합니다.

 

탐욕 알고리즘을 문제 예시 

 

문제

해결