[알고리즘] 탐욕, 그리디 (greedy)

탐욕, 그리디 : greedy

현재 상황에서 가장 좋은 것(최선의 선택)을 고르는 알고리즘

• 탐욕 알고리즘은 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
• 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다.

❓최적해

    제약 조건을 충족시킬 수 있는 해(어떤 문제가 요구하는 값) 가운데 목적 함숫값을 최대 또는 최소로 만드는 값

 

그리디 특징

탐욕 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만,

어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다.

이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있다.

탐욕 알고리즘을 적용해도 언제나 최적해를 구할 수 있는 문제(매트로이드)가 있고,

이러한 문제에 탐욕 알고리즘을 사용해서 실용적으로  빠른 계산 속도로 답을 구할 수 있다.

 

 

그리디 예시

https://velog.io/@contea95/%ED%83%90%EC%9A%95%EB%B2%95%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

위의경우 제일 합이 큰 수를 구하라고 하면

best는  6 + 128 = 134  라는 결과를 얻지만

greedy는 현재 상황에서 최선을 선택한다는 알고리즘 정의처럼

루트에서 17과 6이 있을때 그중 가장 큰 수인 17, 그 다음 자식노드의 23과 4중에 큰 23을 선택새

 17+23 = 40  의 결과를 얻는다.

 

 

그리디 해결 순서

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

 

그리디 성립을 위한 문제의 조건

 

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

 

 

 

 

✔️ 참고

 

https://velog.io/@contea95/%ED%83%90%EC%9A%95%EB%B2%95%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

https://hanamon.kr/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%83%90%EC%9A%95%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-greedy-algorithm/