[알고리즘] 탐욕
탐욕(Greedy) 알고리즘
매 순간 현재 기준으로 최선의 답을 선택해 나가는 기법
- 즉, 당장 눈앞에 보이는 최적의 답을 찾음
- 결과적으로 최적의 답이 아닐 수 있음
적용 조건
탐욕 알고리즘은 빠르지만 최적의 답을 보장하지 않는다.
아래 조건에 해당하는 경우 적용이 가능하다.
- 탐욕적 선택 특성(Greedy Choice Property) – 앞의 선택이 이후의 선택에 영향을 주지 않음
- 최적 부분 구조(Optimal substructure) – 문제에 대한 최적의 답이 부분문제에 대해서도 역시 최적의 답
예제 - 활동 시간 선택
N개의 활동과 각 활동의 시작/종료 시간이 주어졌을 때
한 사람이 최대한 많이 할 수 있는 활동의 수 구하기
| Activity | A | B | C | D | E | Activity | C | A | B | D | E | Activity | C | B | E | ||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 시작 | 1 | 4 | 2 | 4 | 6 | ➤ | 시작 | 2 | 1 | 4 | 4 | 6 | ➤ | 시작 | 2 | 4 | 6 |
| 종료 | 5 | 5 | 3 | 7 | 10 | 종료 | 3 | 5 | 5 | 7 | 10 | 종료 | 3 | 5 | 10 |
구현 코드
관련 문제
문제1. 백준[2839] 설탕 배달
작성 코드
문제2. 백준[1931] 회의실 배정
작성 코드
