그리디 알고리즘
최적해를 구하는 데에 사용되는 근사적인 방법으로, 현재를 기준으로 가장 최적의 상황을 골라가며 해답을 찾는 알고리즘이다.
적용 조건
- 이전의 선택이 이후의 선택에 영향을 주지 않는다.
- 문제에 대한 최적해를 구하는 방법은, 문제를 부분적으로 쪼갰을 때도 그 부분의 최적해를 찾게 해준다. ( 문제에 대한 최적해가 부분 문제에 대해서도 최적해이다 )
특징
- 해당 알고리즘을 통해 얻은 답이 문제에 대한 정답이 아닐 수 있다.(최적이라는 보장은 없다)
- 부분의 최적해들의 집합이 곧 전체 문제의 해답이 될 때 사용할 수 있다.
예제
대표적인 문제로는 회의실 배정 문제가 있다. (백준 1931)
https://www.acmicpc.net/problem/1931
import sys
input = sys.stdin.readline
n = int(input())
times = []
for _ in range(n):
times.append(list(map(int, input().split())))
times.sort(key = lambda x : (x[1], x[0]))
now_time = 0
cnt = 0
for t in times:
if t[0] >= now_time:
now_time = t[1]
cnt += 1
print(cnt)- 그리디 알고리즘을 사용해, 시간을 기준으로 현재 가장 최적의 선택을 한다.
- 현재 시간(now_time)에서 선택할 수 있는 회의중에서, 가장 빨리 끝나는 회의를 선택한다.
- 이러한 선택을 반복하면 최적해가 나온다.
times.sort(key = lambda x : (x[1], x[0]))- 처음에 회의가 끝나는 시간만으로 정렬했는데 틀렸었다.
- 회의가 (1, 1) (0, 1) 이렇게 잡혀있는 경우는 2개의 회의를 선택할 수 있는데, 조건문을 만족시키기 위해 "종료시간을 기준으로 오름차순 정렬한 뒤, 종료시간이 같으면 시작시간을 기준으로 오름차순 정렬을 한다"
