[ Algorithm ] 그리디 알고리즘

 

그리디 (Greedy) / 탐욕 알고리즘

: 현재 상황에서 최적이라고 생각하는 해를 선택하는 방법이다. 

 

하지만 앞으로 남은 단계의 선택을 고려하지않고 현재 단계의 가장 최선의 선택만 고려하기 때문에 항상 최적해를 보장하지않는다. 각 단계에서 최선의 선택한 결과가 전체적으로 최선이길 바라는 알고리즘이다.

 

예를 들어, 아래 트리구조의 경로가 있고 가장 적은 거스름돈을 남기는 것을 목적을 해보자.

가장 적은 거스름돈을 남기기 위해선 파란색 경로로 이동해야 하지만 단계별로 높은 금액을 선택하는 그리디 방법은 빨간색 경로로 이동하여 900원의 거스름돈을 남긴다.

 

⭐ 최적의 해를 도출하기 위한 2가지 조건

 

탐욕스런 선택 조건(Greedy Choice Property)

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

 

최적 부분 구조 조건(Oprimal Substructure)

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

 

🞸 2가지의 조건이 성립하지 않는 경우에는 그리드 알고리즘은 최적해를 구하지 못한다.

🞸 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적의 근사값을 빠르게 도출 시킬 수 있는 장점을 가지고 있다.

🞸 대부분의 경우 계산 속도가 빨라 실용적으로 사용 가능하다.

🞸 매트로이드 구조의 문제에 대해선 언제나 최적해를 찾아낼 수 있다.

 

 

매트로이드 구조

 : 최적해을 가려낼 수 있는 경우인지를 판별할 수 있는 수학적 공간

 모든 문제에서 나타나는 것은 아니나, 여러 곳에서 발견되기 때문에 그리디 알고리즘의 활용도를 높여준다.

 

 

참고

---

https://dad-rock.tistory.com/663

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/