탐욕법 (Greedy Method)

1. 개념

- 알고리즘에서의 탐욕법은 우리가 원하는 답을 얻기 위해서 재귀 호출과 똑같이 여러 개의 조각으로 쪼갠 후

각 단계마다 답의 한 부분을 만들어 간다는 점이다.

( 이 부분은 완전 탐색과 DP(동적계획법)와 똑같다. )

 

-  모든 선택지를 고려해 보고 그중 전체 답이 가장 좋은 것을 찾는 완전 탐색과 DP(동적계획법)와는 달리, 탐욕법을

사용하는 알고리즘은 지금 바로 가장 좋은 방법만을 선택한다.

 

 

 

 

2. 이해하기

- 예를 들어, 외판원 문제에서 사용한 DP(동적계획법)는 다음에 도착할 수 있는 도시들을 하나하나 검사해 보고,

남은 도시들을 모두 순회하는 데 필요한 거리의 합을 최소화하는 답을 찾았지만, 탐욕적인 알고리즘은 당장

다음 도시까지의 거리만을 최소화한다.

 

- 그러므로, 탐욕적인 알고리즘은 많은 경우 최적해를 찾지 못한다.

 

 

- 따라서 탐욕적인 알고리즘이 사용되는 경우는 크게 두 가지로 제한한다.

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

 

- 탐욕적인 알고리즘은 주로 1번째 용도로만 사용된다.

 

- 실제로 2번째 근사해를 구하는 문제는 대개 없을 뿐더러 존재하여도 나중에 배울 조합 탐색이나 메타휴리스틱

알고리즘들이 더 좋은 답을 주는 경우가 많기 때문이다.

 

- 탐욕적인 알고리즘은 개념은 간단하지만 한 문제를 탐욕적으로 해결하는 방법이 한 가지만 있는 것이 아닌

경우가 많고 이 중 어느 방법을 선택해야 최적해를 구할 수 있을지를 알아내기 힘들기 때문이다.

 

- 그러므로'탐욕적인 알고리즘은 문제를 해결할 때 알고리즘의 정답성을 증명하는 과정을 빼먹지 않고

연습하는 것이 좋다.