1. Greedy Algorithm이란?
- Greedy: 탐욕스러운, 욕심 많은
- 탐욕 알고리즘: 선택의 순간마다 당장 눈 앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법
- 최적 해를 구하는 데에 사용하는 근사적인 방법
- 여러 경우 중 하나를 결정할 때마다 그 순간 최적이라고 생각되는 것을 선택하는 방식 > 최종적 해답에 도달
(지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지 고려 X)
- 그 순간에는 지역적으로 최적이라도, 지역적인 최적을 수집한 최종적(전역적)인 답이 최적이라는 보장은 없다.
- 탐욕 알고리즘에 적용할 수 있는 문제: 지역적, 전역적 모두 최적!
* 간단한 예시
- 문제: 노드에서 가장 합이 높은 방법을 선택하는 방법
- 그리디 알고리즘: 상황에 맞게 가장 큰 수를 고름
2. 탐욕 알고리즘을 적용하는 문제의 2가지 조건 (알고리즘 정당성 증명)
(1) 탐욕적 선택 속성(Greedy Choice Property)
- 앞의 선택이 이후의 선택에 영향을 주지 않는다.
(2) 최적 부분 구조(Optimal Substructure)
- 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.
- 문제에 대한 최적해가 부분 문제에 대해서도 역시 최적해
- 매트로이드: 탐욕 알고리즘이 언제나 최적해를 찾을 수 있는, 어떤 문제의 특별한 구조
3. 탐욕 알고리즘 문제 해결법
(1) 선택 절차(Selection Procedure)
- 현재 상태에서의 최적의 해답 선택 (순간에서의 최적 답 선택)
(2) 적절성 검사(Feasibility Check)
- 선택된 해가 문제의 조건을 만족하는지 검사
(3) 해답 검사(Solution Check)
- 원래의 문제가 해결되었는지 검사
- 해결되지 않았다면, 선택 절차로 돌아가 위의 과정을 반복
4. 탐욕 알고리즘의 장점
(1) 근사 알고리즘으로 사용 가능
- 탐욕 알고리즘이 항상 최적의 결과를 도출하진 않는다.
- But 어느정도 최적에 근사한 값을 빠르게 도출할 수 있다.
* 근사 알고리즘? 어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘
> 빠른 시간에 계산이 가능하며, 어느정도 보장된 근사해를 계산할 수 있다.
* 참고
- 근사해를 찾는 문제는 대개 출제되지 않음.
- 근사해를 구할 때는, 실제로 조합 탐색이나 메타휴리스틱 알고리즘이 더 좋은 답을 주는 경우 多
(2) 실용적인 알고리즘
- 매트로이드 구조를 가진 문제에 탐욕 알고리즘을 적용하면 빠른 계산이 가능하다.
5. 그리디 알고리즘 vs 동적 계획법
| 분류 | 그리디 알고리즘 (Greedy Algorithm) | 동적 계획법 (DP: Dynamic Programming) |
| 설명 | 각 단계에서 최적의 선택을 하는 방식으로 문제를 해결 | 작은 문제의 해를 메모이제이션하여 중복 계산을 피하고, 이를 이용하여 큰 문제를 해결 |
| 성립 조건 | 1. 탐욕 선택 속성(Greedy Choice Property) 2. 최적 부분 구조(Optimal Substructure) |
1. 중복 부분 문제 (Overlapping Subproblems) 2. 최적 부분 구조 (Optimal Substructure) |
| 중복 부분 문제 | 중복 부분 문제를 해결하지 않는다. | 중복 부분 문제를 해결할 수 있다. |
| 상황 | 모든 상황을 계산하여 최적의 경로를 구함. * 모든 상황을 계산하기에 시간이 오래 걸림. |
각 단계의 상황에서 최적을 선택하여 최적의 경로를 구함. * 최적이 아닌 경우가 될수 있거나 혹은 풀리지 않는 문제가 될 가능성 |
6. 탐욕 알고리즘의 예시
- 매트로이드
- 회의실 배정
7. 참고
- https://loosie.tistory.com/515
- https://adjh54.tistory.com/212
'Algorithm' 카테고리의 다른 글
| [알고리즘] 다익스트라(Dijkstra) 알고리즘 (0) | 2023.10.19 |
|---|---|
| [알고리즘] 너비 우선 탐색(BFS)과 깊이 우선 탐색(DFS) (0) | 2023.10.03 |
| [알고리즘] Dynamic Programming(동적 계획법) (0) | 2023.09.22 |
| [Algorithm] 8퀸 문제 알고리즘 (재귀) (0) | 2023.08.13 |
| [Algorithm] 하노이의 탑 알고리즘 (재귀) (0) | 2023.08.12 |
댓글