Greedy Algorithm (탐욕 알고리즘)
그리디 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로 여러 경우 중하나를 결정 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 그것이 최적이라고 보장하지는 않는다.
탐욕 알고리즘이 잘 작동하는 문제는 대부분,
- 탐욕스런 선택 조건 (greedy choice property)
- 앞의 선택이 이후의 선택에 영향을 주지 않음
- 최적 부분 구조 조건 (optimal substructure)
- 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해임
이라는 두가지 조건을 만족한다. 이러한 조건을 성립하지 않는 경우에는 그리디 알고리즘은 최적해를 구하지 못한다. 하지만 이러한 경우에도 근사 알고리즘으로 사용이 가능하고 대부분의 경우 계산속도가 빨라 실용적이다.
사용되는 예시
- 결정 트리 학습법 (Decision Tree Learning)
- 활동 선택 문제 (Activity selection problem)
- 거스름돈 문제
- 최소 신장 트리 (Minimum spanning tree)
- 제약조건이 많은 대부분의 문제
- 다익스트라 알고리즘
- 허프만 코드
- 크루스칼 알고리즘
예제
활동 선택 문제 (Activity Selection Problem)
내가 풀었던 BOJ-1931 회의실 배정 문제와 같다. 회의가 빨리 끝나는 순으로 강의를 선택하는 방법으로 풀이했다.
- 각 상태에서 최적의 선택을 진행했을 때 최적해에 도달하는 문제로,
- 한 번 강의를 수강한 이후에 다음 최적의 강의를 선택하는 방법도 최초 한번 강의를 선택한 방법이 같다.
- 이는 곧 문제 전체를 해결하는 방법과 같다.
분할 가능 배낭 문제 (Fractional Knapsack Problem)
N개의 물건의 가치V와 무게M이 주어지고, W무게만큼 수용할 수 있는 배낭에 이 물건들을 가치의 합이 최대가 되게 담아야 한다.
-
0-1 배낭 문제에서는, 물건을 쪼갤 수 없으며, 담거나 안담거나 한가지만 택할 수 있다. 백준의 BOJ-1202 보석 도둑 문제가 0-1배낭문제이다.(배낭이 여러개라 다르긴 하지만, 같은 논리가 적용된다.)
-
분할 가능 문제에서는, 물건을 원하는 무게만큼 쪼갤 수 있다.
- 0-1 배낭 문제와는 달리 가방의 최대 수용 무게보다 물건 무게의 총합이 크다면 쪼개서 무조건 가방을 꽉 채울 수 있다.
예제 및 풀이 출처는 GeeksforGeeks - Fractional Knapsack Problem 이다.
Input :
Item은 (value, weight) 짝으로 이루어져 있다.
arr[] = {{60, 10}, {100, 20}, {120, 30}}
배낭용량 W = 50;
Output :
가능한 최대 value의 합 = 240
아이템을 10kg, 20kg, 그리고 30kg의 2/3조각(20kg)으로 만든다.
그렇게 되면 이 된다.
- 브루트 포스로 모든 가능한 부분집합을 구해 최대합을 구할 수는 있지만 시간이 너무 오래걸린다.
- 효과적인 방법은 그리디이다.
-
각 아이템을 value/weight 로 만들고, 이렇게 만든것을 정렬한다.
-
그리고 value/weight 가 가장 큰것부터 (즉, 가치가 큰 것부터) 배낭이 허용하는 한 최대로 담는다.
-
이 과정은 항상 이 문제에 대한 최적해가 된다. 따라서 그리디 알고리즘을 만족한다.
이 문제의 C++, Java, Python3, C# 풀이는 GeeksforGeeks - Fractional Knapsack Problem에 있다.
🔎 백준 문제 풀이
| 문제 | 풀이 링크 |
|---|---|
| 백준 4796 - 캠핑 | 🔗 |
| 백준 2217 - 로프 | 🔗 |
| 백준 1439 - 뒤집기 | 🔗 |
| 백준 11000 - 강의실 배정 | 🔗 |
| 백준 1744 - 수 묶기 | 🔗 |
참고자료
