[Algorithm] / [Python] 그리디 (Greedy)

1. 그리디 (Greedy) ?

영어 단어 Greedy는 '욕심 많은'이란 뜻을 가지고 있다. 이 뜻 그대로 그리디 알고리즘이란 '현재 상황에서 가장 좋은 최선의 선택을 고르는' 알고리즘을 말합니다.

순간 순간 최적이라고 생각되는 것을 선택해 나가는 방식으로 최종적인 해답을 찾지만 그것이 최적이라는 보장은 없습니다.

 

2. 그리디 알고리즘 문제를 해결하는 방법

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

 

3. 그리디 알고리즘 적용을 위한 2가지 조건

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

위 조건이 성립하지 않는 경우에는 그리디 알고리즘은 최적해를 구하지 못한다. 

매트로이드 구조의 문제에 대해서는 그리디 알고리즘이 언제나 최적해를 찾아낼 수 있다.

 

4. 정리

• 그리디 알고리즘은 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출할 수 있는 장점이 있다. 이 장점으로 인해 탐욕 알고리즘은 근사 알고리즘으로 사용할 수 있다.
• 그리디 알고리즘을 적용해도 언제나 최적해를 구할 수 있는 매트로이드 문제가 있다.

 

참고

근사 알고리즘(approximation algorithm)

: 어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘

: 가장 최적화되는 답을 구할 수는 없지만, 비교적 빠른 시간에 계산이 가능하며 어느 정도 보장된 근사해를 계산할 수 있다.

 

참고 사이트

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/

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

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

탐욕법(그리디) 알고리즘