탐욕법 (greedy method)
가장 직관적인 알고리즘 설계 패러다임
우리가 원하는 답을 재귀 호출과 똑같이 여러 개의 조각으로 쪼개고,
각 단계마다 답의 한 부분을 만들어 간다는 점에서 완전 탐색이나 동적 계획법 알고리즘과 다를 것이 없다.
But, 탐욕법은 각 단계마다 지금 당장 가장 좋은 방법만을 선택 하는 방법.
주의할점
탐욕적 알고리즘은 많은 경우 최적해를 찾지 못함.
탐욕적 알고리즘이 사용되는 경우
탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우
탐욕법은 동적 계획법보다 수행 시간이 훨씬 빠르기 때문에 유용함.시간이나 공간적 제약으로 인해 다른 방법으로 최적해를 찾기가 너무 어려운 경우
최적해 대신 적당히 괜찮은 답(근사해)을 찾는 것으로 타협할 수 있음.
프로그래밍 대회에서는 주로 1번 용도로만 사용됨.
=> 근사해를 찾는 문제는 주어지지 않음..
탐욕법 vs 동적 계획법
사실, 탐욕법으로 최적해를 찾을 수 있는 많은 문제들은 동적 계획법으로도 풀 수 있음.
탐욕법 |
|
동적 계획법 |
하나의 경우만 고려해서 답을 얻는 방법 |
∈ |
모든 경우의 수를 다 찾아 답을 얻는 방법 |
따라서 동적 계획법으로 탐욕법이 고려하는 경우를 커버하기 때문에 가능함.
하지만 동적 계획법에 필요한 메모리나 시간이 과도하게 큰 경우는 탐욕법을 사용해야 할 수도 있음.
'스터디 > 알고리즘 정리' 카테고리의 다른 글
| 동적 계획법 테크닉 (not yet) (0) | 2018.12.02 |
|---|---|
| 동적 계획법 문제 풀이 (not yet) (0) | 2018.12.02 |
| 동적 계획법 (0) | 2018.12.01 |
| 분할 정복 (0) | 2018.11.27 |
| 알고리즘 시간 복잡도 (0) | 2018.11.26 |