📝 탐욕법
현재 상황에서 가장 좋은 것(최선의 선택)을 고르는 알고리즘을 말합니다.
🎯 탐욕법의 특징
- 동적 프로그래밍을 간단한 문제 해결에 사용하면 지나치게 많은 일을 한다는 것을 착안하여 고안했다.
- 탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법이다.
- 최적해를 구할 수 있는 문제에 사용하면 매우 빠르다.
- 그리디 알고리즘을 사용하는 문제는 간단한 문제로 나올 가능성이 매우 크다
탐욕법 알고리즘 조건
그리디 알고리즘으로 최적해를 도출하기 위해서는 아래 두가지 조건을 만족해야 한다.
1. 탐욕스러운 선택 조건 (greedy choice property)
- 탐욕적인 선택은 항상 안전하다는 것이 보장되어야 한다. 여기서 "안전하다"라는 것은 이 선택으로 인해 전체 문제의 최적해를 반드시 도출할 수 있어야 한다는 뜻이다.
- 앞의 선택이 이후의 선택에 영향을 주지 않아야 한다.
2. 최적 부분 구조 조건 (optimal substructure)
- 전체 문제의 안에는 여러 단계가 존재하고, 이 여러 단계 내의 각각의 단계에서 최적해가 도출되어야 한다.
탐욕법 팁
- 문제에서 '가장 큰 순서대로', '가장 작은 순서대로'와 같은 기준을 제시해준다.
- 그리디 알고리즘 문제는 자주 정렬 알고리즘과 짝을 이뤄 출제한다.
- 그리디 알고리즘 문제 유형은 '사전에 외우고 있지 않아도 풀 수 있는 가능성이 높은 문제 유형'이라는 특징이 있다.
- 코딩 테스트 문제를 만났을 때, 바로 문제 유형을 파악하기 어렵다면 그리디 알고리즘을 의심하고 문제를 해결할 수 있는 탐욕적인 해결법이 존재하는지 확인한다.
참고자료
도라에몽 암기빵