그리디 알고리즘
현재 시점에서의 최적의 선택을 하는 알고리즘이다. 최종적으로 보면 가장 좋은 답이 아닐 수도 있는데 이는 그 순간 단계에서 가장 좋은 방법만 선택하기 때문에 앞으로의 선택들에 어떤 영향을 줄지 고려하지 않기 때문이다.
즉, 그리디 알고리즘에서 모든 선택이 최적의 선택과 일치하지 않는다.
탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
그리디 알고리즘을 사용하려면 이 방법이 최선이라는 근거가 필요하다. 일반적으로 그리디를 사용하는 문제는 최대한 적은, 최대한 많은 이라는 문구가 문제에 들어가는 경우가 많다. 이러한 문제는 최대/최소의 경우의 수를 구하는 문제이다. 또한 그리디를 사용할 수 있는 조건이 주어진다. 주로 알려진 그리디 대표문제로 동전문제가 있는데 다음과 같다.
📌 예제 1
500원, 100원, 10원 동전이 무수히 많다고 가정할 때 가장 적은 수의 동전을 이용해서 1410원을 만든다고 하자.
이때 사용하는 동전의 개수는 몇개인가?
위 동전 문제는 가장 큰 단위인 500원을 먼저 사용해 최대한 많이 만들고, 그 다음 100원, 10원 순으로 만들어서 1410원을 완성하면 된다. 이처럼 동전간의 배수, 약수 관계가 존재하여 그리디 방법을 사용할 수 있게 된다. 이러한 조건은 문제 내에 숨겨져있으므로 직접 찾아내야한다.
그리디 알고리즘이 사용되는 경우는 두 가지가 있다.
- 그리디 알고리즘을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우, 이는 DP보다 수행시간이 훨씬 빠르다.
- 시간이나 공간적 제약으로 인해 다른 방식으로 최적해를 찾기 힘든 경우를 대신해 적당한 근사해를 찾는 것으로 타협을 본다. => 최적은 아니나 임의의 답보다 좋은 답을 제공하여 유용하다.
주로 그리디 알고리즘을 사용하는 문제는 다음과 같다.
1. 활동 선택 문제
2. 거스름돈 문제
3. 최소 신장 트리
4. 제약조건이 많은 대부분의 문제
5. 다익스트라 알고리즘
6. 하프만 코딩
7. 크러스컬 알고리즘
...