탐욕법 Greedy Algorithm
- 항상 현재 상태에서 최선의 경우만 탐욕스럽게 고르는 전략입니다.
- 완전탐색과 달리 모든 경우를 살펴보지는 않습니다.
- 그리디 문제들은 특별한 배경지식이 없더도 문제에서 규칙성을 찾으면 풀 수 있는 편입니다.
- 다만 난이도를 아주 쉬운 문제부터 매우 어렵게까지, 출제자 마음대로 만들 수 있습니다.
- 그리디 문제의 진짜 어려운 부분은 바로 '이 문제가 그리디 문제인지 판별하는 것'입니다.
탐욕법 대표 문제
https://www.acmicpc.net/problem/1931
1931번: 회의실 배정
(1,4), (5,7), (8,11), (12,14) 를 이용할 수 있다.
www.acmicpc.net
위 '회의실 배정'문제는 활동 선택 문제(Activity selection problem)라는 유명한 그리디 문제입니다. 꼭 풀어보시길 바랍니다.
728x90
반응형
'Algorithm > 이론' 카테고리의 다른 글
| 알고리즘 유형 5. 이분 탐색 (0) | 2022.04.24 |
|---|---|
| 알고리즘 유형 4. 그래프 (0) | 2022.04.23 |
| 알고리즘 유형 2. 완전탐색 (0) | 2022.04.22 |
| 알고리즘 유형 1. 자료구조 (파이썬) (0) | 2022.04.21 |
| (C언어) 닫힌 해시 (0) | 2021.09.29 |
