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

그리디(탐욕) 알고리즘

• 각 단계에서 최선책만을 선택하며 다음 단계로 이동하는 일고리즘
• 최적의 해를 구하는 알고리즘이 아니다. 최적의 해에 근사 해를 구하는 알고리즘
• 동적 프로그래밍이 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘. 동적 프로그래밍을 대체하는 것은 아니며 서로 보완해서 사용할 수 있다.
• 각 단계에서 최선책만을 선택하기 때문에 현재의 결과에 의해 다음 선택이 변하는 경우 적합한 알고리즘이 아니다.
• 각 단계에서 최선의 선택만을 하지만 결과는 최선이 아닐 수 있다.

* 예제

위의 그림에서 가장 숫자가 큰 요소를 찾는데 있어서 해당 분기점마다 보다 큰 수를 찾는 방식으로 최종 해답을 찾아가고 있다. 순간마다 큰 수를 찾아가면 최종 결과는 12이다. 하지만 실제 전체 숫자 중에서 가장 큰 수는 99이다. 이처럼 전체 문제해결에서의 최적 해답을 찾지는 못한다.

하지만 이러한 단점들을 극복하는 그리디 알고리즘의 가장 큰 장점은 계산 속도에 있다. 그렇기 떄문에 몇몇의 문제에서는 최적해를 빠르게 산출해낼 수 있다.

 

• 활동 선택문제에서 탐욕 알고리즘 응용하기

각각의 활동들은 시작시간과 종료시간이 있다. 한 사람이 최대한 많이 할 수 있는 액티비티의 수와 액티비티의 종류를 구해보자.

1. 각각의 활동들은 시작시간과 종료시간이 주어져 있다.
2. 한 사람이 하는 것이므로 한 가지 액티비티를 종료하여야 다른 액티비티를 할 수 있다.

1. 첫 번째 활동은 가장 먼저 끝나는 것으로 선택하는 것이 현재 상황에서 가장 최선의 선택이다. (주어진 시간 내에 많이 액티비티를 해야 하므로)
2. 활동이 끝난 후 또 다시 가장 빠르게 끝낼 수 있는 활동을 찾는다.
3. 또 다시 활동이 끝난 후 다시 가장 빠르게 끝낼 수 있는 활동을 찾는다.
4. 이러한 단계를 반복하는 것이 탐욕 알고리즘이다.

탐욕스러운 선택 조건(Greedy choice property): 앞의 선택이 이후의 선택에 영향을 주지 않는 조건.
최적 부분 구조 조건(Optimal Substructure): 문제에 대한 최종 해결 방법이 부분 문제에 대해서도 또한 최적 문제 해결 방법이라는 조건

그리디(탐욕) 알고리즘은 위 두 가지가 성립해야한다.

* 응용

• 다익스트라 알고리즘
• 활동 선택 문제
• 분할가능 배낭문제

---

[참고]

https://velog.io/@cyranocoding/%EB%8F%99%EC%A0%81-%EA%B3%84%ED%9A%8D%EB%B2%95Dynamic-Programming%EA%B3%BC-%ED%83%90%EC%9A%95%EB%B2%95Greedy-Algorithm-3yjyoohia5