그리디 알고리즘 [Greedy Algorithm]
Greedy Algorithm
- 문제 해결 과정에서 그 순간 최적이라고 생각되는 결정을 하는 방식으로 진행하여 최종 해답에 도달하는 문제 해결 방식
- 미리 정한 기준에 따라서 매번 가장 좋아 보이는 답을 선택하는 알고리즘
- 최적화 문제를 풀 때 사용
그리디 알고리즘은 동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘.
동적 프로그래밍을 대체하는 것은 아니고 같이 쓰이며 서로 보완하는 개념
그리디 알고리즘은 전체 문제 해결 과정에서 항상 최적의 답을 찾지 못하는 단점이 있지만, 어느 정도 최적의 해에 근사한 값을 빠르게 도출한다는 장점이 있음.
즉, 특정 상황 또는 조건에서는 최적의 해를 보장함.
이러한 장점이 동적 프로그래밍을 보완하는 듯.
조건
2가지 조건을 만족해야 함.
- 탐욕 선택 속성(Greedy Choice Property)
- 이전의 선택이 이후에 영향을 주지 않음을 의미 (DP는 영향을 받음)
- 최적 부분 구조(Optimal Substructure)
- 부분 문제의 최적결과가 전체에도 그대로 적용될 수 있어야 한다는 것. (DP와 동일)
일반적으로 그리디임을 증명하려면 수학적 증명이 동반되어야 한다고 함.
허나, 그리디가 아니라고 보는 경우는 반례를 1개만 찾아도 되기 때문에 상대적으로 쉬움.
활동 선택(Action Selection) 문제
N개의 활동이 있고 각 활동에는 시작 시간 및 종료 시간이 있을 때, 한 사람이 최대한 많이 할 수 있는 활동(Activity)의 수를 구하는 문제
즉, 각각의 활동(Activity)에는 시간이 소요되므로 하나를 선택했다면 그 동안 해당 시간에 다른 Activity를 할 수 없음.
참고
This post is licensed under CC BY 4.0 by the author.