Greedy
Greedy 알고리즘에 대해 설명하는 페이지입니다.
Greedy
Tags
Algorithm
Introduction
- Definition
- 탐욕법(Greedy Method) 은 각 단계마다 지금 당장 가장 좋은 방법만을 선택하여 답을 찾는 방법을 말한다.
- 탐욕법을 이용한 알고리즘, 혹은 탐욕적인 알고리즘(Greedy algorithm) 은 우리가 원하는 답을 재귀 호출과 똑같이 여러 개의 조각으로 나누고, 각 단계마다 답의 한 부분을 만들어 간다는 점에서 완전 탐색이나 동적 계획법 알고리즘과 유사하다. 그러나 탐욕법은 모든 선택지를 고려하지 않고 항상 각 단계마다 가장 좋은 방법만을 선택한다.
- 탐욕법은 지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지 고려하지 않는다.
- Greedy Algorithm이 사용되는 경우는 크게 다음 두 가지로 제한된다.
- 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제의 경우, 탐욕법은 동적 계획법보다 수행 시간이 훨씬 빠르기 때문에 유용하다.
- 시간이나 공간적 제약으로 인해 다른 방법으로 최적해를 찾기 너무 어렵다면 최적해 대신 적당히 괜찮은 답(근사해)을 찾는 것으로 타협할 수 있다. 탐욕법은 이럴 때 최적은 아니지만 임의의 답보다는 좋은 답을 구하는 용도로 유용하게 사용된다.
- 탐욕적 선택 속성(Greedy choice property) 란 동적 계획법처럼 답의 모든 부분을 고려하지 않고 탐욕적으로만 선택하더라도 최적해를 구할 수 있는 속성을 의미한다.
- 탐욕법으로 최적해를 찾을 수 있는 많은 문제들은 동적 계획법으로도 해결할 수 있다. 다만 동적 계획법은 탐욕법을 사용하는 것에 비해 필요한 메모리나, 시간이 과도하게 크다는 점을 고려해야 한다.
How to Use
- 탐욕적 알고리즘(Greedy algorithm)
- 문제의 답을 만드는 과정을 여러 조각으로 나눈다.
- 각 조각마다 어떤 우선순위로 선택을 내려야 할지 결정한다. 이에 대한 직관을 얻기 위해서 예제 입력이나 그 외의 작은 입력을 몇 개 손으로 풀어보는 것이 효율적이다.
- 어떤 방식이 동작할 것 같으면 두 가지의 속성을 증명한다.
- 탐욕적 선택 속성(Greedy choice property): 항상 각 단계에서 우리가 선택한 답을 포함하는 최적해가 존재함을 보이면 된다. 이 증명은 대개 우리가 선택한 답과 다른 최적해가 존재함을 가정하고, 이것을 조작해서 우리가 선택한 답을 포함하는 최적해로 바꿀 수 있음을 보이는 형태로 이루어진다.
- 최적 부분 구조: 각 단계에서 항상 최적의 선택만을 했을 때 전체 최적해를 구할 수 있는지 여부를 증명한다. 다행히도 대개의 경우 이 속성이 성립하는지 아닌지는 자명하게 알 수 있다.
Examples
This post is licensed under CC BY 4.0 by the author.