탐욕법

탐욕법(Greedy Method)

• 재귀 호출과 똑같이 여러 개의 조각으로 쪼개고, 각 단계마다 답의 한 부분을 만들어감 ≒ 동적 계획법, 완전 탐색but, 동적 계획법과 완전 탐색은 모든 선택지를 고려해보고 그 중 전체 답이 가장 좋은 것을 찾음
• 각 단계마다 지금 당장 가장 좋은 방법만을 선택

 

탐욕적 알고리즘이 사용되는 경우

1. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우,
   탐욕법은 동적 계획법보다 수행 시간이 훨씬 빠르기 때문에 유용
2. 시간/공간적 제약때문에 다른 방법으로 최적해를 찾기 너무 어렵다면, 적당히 괜찮은 답(근사해)을 찾는 것으로 타협할 수 있음
   탐욕법은 이럴 때 최적은 아니지만 임의의 답보다는 좋은 답을 구하는 용도로 유용

 

정당성의 증명

: 탐욕적인 알고리즘이 항상 최적해를 찾아낼 수 있다는 것을 증명

1) 탐욕적 선택 속성

: 답의 모든 부분을 고려하지 않고 탐욕적으로만 선택하더라도 최적해를 구할 수 있다 -> 탐욕적인 선택을 해서 손해를 볼 일이 없다

2) 최적 부분 구조

: 부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있음을 보여야 함

이 속성은 문제에 대한 동적 계획법과 탐욕적 알고리즘의 유용성을 결정하는 데 사용된다.

 

탐욕적 알고리즘 레시피

1. 문제의 답을 만드는 과정을 여러 조각으로 나눕니다.
2. 각 조각마다 어떤 우선순위로 선택을 내려야할지 결정합니다. 이에 대한 직관을 얻기 위해서는 예제 입력이나 그 외의 작은 입력을 몇 개 손으로 풀어보는 것이 효율적입니다.
3. 어떤 방식이 동작할 것 같으면 두가지의 속성을 증명해 봅니다.
   
   1) 탐욕적 선택 속성 : 항상 각 단계에서 우리가 선택한 답과 다른 최적해가 존재함을 가정하고, 이것을 조작해서 우리가 선택한 답을 포함하는 최적해로 바꿀 수 있음을 보이는 형태로 이루어집니다.
   
   2) 최적 부분 구조 : 각 단계에서 항상 최적의 선택만을 했을 때 전체 최적해를 구할 수 있는 지 여부를 증명합니다. 다행히도 대개의 경우 이 속성이 성립하는지 아닌지는 자명하게 알 수 있습니다.

 

---

 

출처 : 도서 '알고리즘 문제 해결 전략 1권' 

알고리즘 문제 해결 전략 세트