탐욕법(Greedy)
탐욕법
개요
최적해를 구할 때 사용되는 알고리즘으로, 문제를 쪼개어 단계별로 나눈 후, 각 단계에서의 최적해를 구해나가며 전체 문제의 최적해를 구하는 알고리즘이다.
조건
총 두 조건이 만족할 시 탐욕법 사용이 가능하다.
탐욕적 선택 속성(greedy choice property): 각 단계에서 최적의 선택을 하는 것으로 전체 문제의 최적해를 얻을 수 있어야 한다. 다음 단계에서 선택까지 고려한다면 그것은 탐욕적인(Greedy) 방법이라고 할 수 없다.
최적 부분 구조(Optimal Substructure): 문제의 최적해를 찾고자 할 때 부분 문제들에 대한 최적해를 찾고, 이를 결합하여 문제의 최적해가 나와야 활용이 가능하다. 이는 그리디 알고리즘을 사용하기 위한 자명한 사실이다.
사용되는 경우
보통 두 가지 용도로 사용된다.
탐욕법을 사용하여도 항상 최적해를 구할 수 있는 경우: 왠만한 최적해를 구하는 알고리즘보다 빠르기 때문에 유용하게 사용된다.
시간 및 공간 제약으로 인하여 최적해를 찾기 어려울 때 근사해를 찾기 위한 경우: PS에서는 보통 조합탐색 또는 메타휴리스틱 알고리즘이 근사해를 찾기에 더 최적화 되어있기 때문에 자주 쓰이지는 않는다.
탐욕법 사용 방식
레시피
그리디 알고리즘을 사용하여 문제를 해결할 때 보통 해당 과정대로 진행된다.
- 문제를 구하는 과정을 여러 단계로 쪼개어본다.
- 각 단계별로 최적해를 구하기 위하여 어떤 선택을 해야 하는지 확인하며 그리디 알고리즘을 구상한다.
- 탐욕적 선택 속성과 최적 부분 구조를 증명한다.
2번 과정의 경우 예제를 풀어보며 구상해 보는 것이 도움이 된다. 3번이 가장 중요한 과정으로, 두 조건이 증명하지 않는다면 구상한 알고리즘이 성립되지 않는다는 뜻이기 때문에 두 조건을 반드시 증명하여야만 한다.
탐욕적 선택 속성을 증명하는 방법
보통 아래 과정대로 증명한다.
- 탐욕적 선택을 포함하지 않는 최적해의 존재를 가정한다.
- 해당 최적해를 탐욕적인 선택을 포함하여 만들 수 있음을 증명한다.
탐욕법과 정렬
그리디 알고리즘을 설계할 때 정렬이 활용되는 경우가 많다.
이는 그리디의 특성에서 기인하는데 보통 그리디 알고리즘에서는 최적의 선택을 하기 전 어떠한 기준을 정하고, 해당 기준을 통하여 최적의 선택을 반복적으로 하는 방식으로 문제를 해결한다.
이때 해당 기준에 따라 정렬을 한다면 최적의 선택을 반복적으로 하는 면에 있어서 대부분 문제의 구조가 단순해지는 경우가 많기 때문에 정렬이 자주 활용되곤 한다.
웰노운 그리디 알고리즘
거스름돈 문제
해당 문제는 거스름돈이 배수 관계로 이루어져 있을 때만 사용 가능하다.
추후 추가 예정
기타
이 외에도 그리디 알고리즘이 활용되는 알고리즘은 다음과 같다.
- 크루스칼 알고리즘 (kruskal Algorithm)
- 다익스트라 알고리즘 (Dijkstra Algorithm)
- 허프만 코드 알고리즘 (Huffman Code Algorithm)
- 그 외 제약 조건이 많은 대부분의 문제