알고리즘 유형 3. 탐욕법

탐욕법 Greedy Algorithm

 

- 항상 현재 상태에서 최선의 경우만 탐욕스럽게 고르는 전략입니다.

- 완전탐색과 달리 모든 경우를 살펴보지는 않습니다.

- 그리디 문제들은 특별한 배경지식이 없더도 문제에서 규칙성을 찾으면 풀 수 있는 편입니다.

- 다만 난이도를 아주 쉬운 문제부터 매우 어렵게까지, 출제자 마음대로 만들 수 있습니다.

- 그리디 문제의 진짜 어려운 부분은 바로 '이 문제가 그리디 문제인지 판별하는 것'입니다.

 

 

 

 

탐욕법 대표 문제

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

위 '회의실 배정'문제는 활동 선택 문제(Activity selection problem)라는 유명한 그리디 문제입니다. 꼭 풀어보시길 바랍니다.