1. Greedy 란?
- 근시안적인 방식으로 최적해를 구하는 알고리즘입니다.
목적
- 많은 연산이 필요한 Dynamic Programming의 효율적인 대안으로 사용하기 위함입니다.
- 사용조건을 만족하면, Dynamic Programming보다 더 효율적으로 해를 구할 수 있습니다.
동작 방식
- 각 단계에서 최적의 답을 선택하므로써 전체적인 최적해를 구하는 방식으로 동작합니다.
사용 조건
탐욕적 선택 속성 - greedy choice property
- 각 단계에서의 선택이 전체 해결책의 최적성을 해치지 않고, 문제의 남은 부분에 대한 탐욕적 기준 또한 유지됩니다. (독립적)
- 각 단계에서의 최적의 선택이 전체의 해를 구성함을 의미합니다.
최적 부분 구조 - optimal substructure
- 문제의 최적해는 전체 문제의 부분문제의 해로 구성됩니다.
- 작은 문제로 나누어 해결하고, 이 해결책들을 결합함으로써 전체 문제의 해를 얻을 수 있음을 의미합니다.
2. 대표 문제
거스름돈 문제
- 최소 동전 개수로 거스름돈을 주는 문제입니다.
해결 방법
- 가장 큰 단위의 동전부터 최대한 사용하여 거스름돈을 줍니다.
탐욕적 선택 조건
- 현재 선택이 다음 선택의 기준에 영향을 미치지 않습니다.
- 우선적으로 큰 단위의 동전을 최대 사용하면, 전체적으로 사용되는 동전의 수를 최소화 할 수 있습니다.
최적 부분 구조
- 큰 단위의 동전을 사용한 후, 남은 거스름돈에 대해서도 동일한 방식을 적용할 수 있습니다.
반례
- 작은단위는 큰 단위의 배수여야 합니다.
- 작은 단위의 동전들을 조합했을 때, 전체 거스름돈 갯수가 더 적어지는 경우가 발생할 수 있습니다.
- 6원, {1, 3, 4}
Activity Selection Problem - 활동 선택 문제
- 한 사람이 참여할 수 있는 최대 활동 수를 구하는 문제입니다.
- 한 사람이 동시에 두 가지 활동을 참여할 수 없습니다.
해결 방법
- 가장 먼저 끝나는 활동부터 선택합니다.
탐욕적 선택 속성
- 현재 선택이 다음 선택의 기준에 영향을 미치지 않습니다.
- 선택할 수 있는 가능 시간을 최대화하여, 남은 활동들을 선택할 수 있는 여지를 최대화합니다.
최적 부분 구조
- 먼저 끝나는 활동을 선택하고, 남은 시간에 대해서도 동일한 방식을 적용할 수 있습니다.
Minimum Spanning Tree - 간선 연결 문제
- 주어진 점들을 모두 연결하는데 필요한 최소한의 간선과 비용을 찾는 문제입니다.
해결방법
- 모든 점이 연결될 때까지 가장 가까운 점들을 연결합니다.
출처
'Algorithm' 카테고리의 다른 글
| [기초 알고리즘] String (0) | 2023.11.08 |
|---|---|
| [기초 알고리즘] 수학 (0) | 2023.11.08 |
| [알고리즘] Two Pointer (0) | 2023.11.08 |
| [알고리즘] Binary Search (0) | 2023.10.26 |
| [기초 알고리즘] Sort (0) | 2023.10.26 |