1. Greedy Algorithm
  2. BOJ 1931 회의실 배정

Greedy Algorithm

탐욕적 알고리즘(그리디 알고리즘)이 사용되는 경우는 두 가지가 있다.

  1. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제
  2. 다른 방법으로 최적해를 찾기 너무 어려울 때 근사해를 구할 수 있음.

탐욕적 알고리즘으로 찾은 해가 항상 최적해라는 정당성을 증명하려면

  1. 탐욕적으로만 선택하더라도 최적해를 구할 수 있다는 것. 즉, 적어도 하나의 최적해는 이 알고리즘으로 구할 수 있다는 것.(탐욕적 선택 속성, greedy choice property)
  2. 항상 최적의 선택만을 내려서 전체 문제의 최적해를 얻을 수 있음을 증명. (최적 부분 구조, optimal substructure) ⇒ 대부분은 자명

BOJ 1931 회의실 배정

초기 시도: 재귀, 분할정복을 이용해보았지만 시간초과.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def greedy():
  global cnt, time
  time_min = time[0]
  new_time=[]
  for i in time:
    if not time_min[1]<=i[0]:
      new_time.append(i)
  time=new_time
  print(time)
  cnt += 1
  if time:
    greedy()
  else:
    print(cnt)

greedy()

탐욕법 이용:

1
2
3
4
5
6
7
8
9
10
11
import sys
N = int(sys.stdin.readline())
time = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
cnt = 1
time.sort(key=lambda t: (t[1],t[0]))
end_time = time[0][1]
for i in range(1,N):
  if time[i][0] >= end_time:
    cnt += 1
    end_time=time[i][1]
print(cnt)