알고리즘8 Deadline Scheduling

N개의 할일. 각 할일의 분량은 1시간

1시간동안 한 가지 일만 가능

 

(example: 데드라인이 전부 2이다. 1,2 슬롯 안에 다 넣어야 하는데 2개밖에 못 넣는다

3개를 다 넣을 수 없으므로 profit이 가장 높은 방법을 찾아야 한다.)

=> 이런 식의 직관을 코드로 바꾸기는 굉장히 어려움! 간단한 작전이 있다!

 

 

가정1

꼭 필요한 것 같지는 않지만, deadline이 n보다 큰 건 의미가 없다.

앞으로 당기면 됨(?)

가정2

profit이 큰거부터! 문제에서 순서는 상관없지만(Set) 나중에 편하기 위해서

(데드라인이 같은 게 있으면 큰 거부터 해야하니까)

 

가정3

deadline 이후에 job이 등장하지 않는다.

데드라인 이후의 job을 지워도 profit이 똑같기 때문에

---

 

높은 이익을 가진 job부터 스케쥴을 한다 (이것도 그리디 알고리즘이다.)

새로운 job을 넣어야 하는데 다른 job으로 꽉 차있음

내가 profit이 가장 작은데 스케쥴하려면 나보다 profit이 더 큰 애를 빼야 하므로 더 안 좋아짐

(하지만 완전한 증명이 아님. 지금은 안좋지만 나중에 더 좋아질 수 있기 때문에)

 

빈자리가 있다면 뒤쪽에 넣는게 좋다.

다른 job을 방해하는지 봐야한다.

 

뒤쪽에 있을 수록 방해할 가능성이 더 낮다. (직관)

 

deadline 앞쪽을 보고 빈자리가 없으면 버리고

빈자리가 있으면 빈자리 중 제일 늦은 시간에 스케줄한다.

---

문제: 왜 이게 답인가? 증명 시작!

 

그리디 알고리즘의 스탠다드 증명을 따라간다.

알고리즘의 선택이 정답을 벗어나지 않는다는 것을 계속 증명

답이 여러 개 있다는 것이 어려움~

여기서도 정답을 바꾸어가면서 할 것~ job이 어디에 위치하느냐까지 알아야해서 약간 더 복잡

 

빈 스케줄로 시작

 

1, 2번 스케줄이 들어옴 

 

A = 스케줄이 들어올 떄마다 변화 (알고리즘이 만들고 있는 스케줄)

S = 정답

---

 

Ji까지 처리한 후에 이 것이 성립한다.

 

 

 

A에는 일부가 들어있다. (일부는 들어있지 않다.)

 

S에는 전체 중에 일부가 들어있다.

 

 

오른쪽은 S에 등장하든말든이고 J(i+1)

왼쪽(i보다 작거나 같은)은 A에 등장하면 어떤 정답 S에도 등장한다.

j(3)이 A에 있다면 S에도 있다.

j(2)이 A에 없다면 S에도 없다.

 

등장하는 J(i)는 A와 S에서의 위치도 같다.

(아직까지 알고리즘의 주장임. 사실이라면 알고리즘이 끝났을 때 정답이 찾아진다는 이야기)

알고리즘이 끝났을 때는 J(n)을 고려한 결과이기 떄문이다.

즉, j<=N 은 모든 job에 대해서 A에 있으면 S에 있다는 것임

=> A는 정답 중 하나

 

---

이제 두 개를 증명하면 된다.

왼쪽(i보다 작거나 같은)은 A에 등장하면 어떤 정답 S에도 등장한다.

등장하는 J(i)는 A와 S에서의 위치도 같다.

 

 

base: i=0

아무것도 안 본 상태 (A가 비어있는 상태)

i보다 작거나 같은 값은 없음. S도 비어있음

(A==S) 아무것도 없기 떄문에 사실임

 

step: J(i)에서 J(i+1)까지 갔을 때 true라는 것을 증명하겠다.

 

 

J(k) k<=i

A에 있는 것들은 S에 같은 자리에 있고

S에는 추가적으로 다른 값이 있을 수 있음 (★)

 

빈자리가 있다면 J+1이 여기 들어가겠지

---

1. 알고리즘이 버림 = 빈자리가 없음

정답의 데드라인 이전에 꽉 차있다는 뜻임 (1~i번까지)

j+1이 등장한다면 데드라인 이후에 등장해야 한다. => 등장하지 않는다는 뜻

J(i+1) not in S

 

2. 알고리즘이 안버림 = 빈자리 중 가장 뒤에 스케줄링하겠다

(A에 등장하는 것은 S의 같은 자리에 등장한다는 것 잊지 말기)

 

알고리즘이 x번째 슬롯에 스케줄시켰다. 

2-1. S에 J(i+1) 등장하지 않음

2-1-1. S의 x번째 slot이 비어있는 경우

빈 곳에 i+1을 넣는다. => S가 최적이라는 것에 모순(더 좋은 답이 있다는 것)

 

2-1-2. S의 x번째 slot에 P ( J(p) 가 배치됨 )

p > i+1 이다.

1번부터 i번까지는 없으면 없고 있으면 있고&같은 자리에 있다.

i+1놓은 자리에 이미 뭐(p)가 있다면 그 p는 i+1보다 profit이 좋을 수 없다. (profit이 높은 순대로 나오니까)

얘도 p를 버리고 i+1로 바꾸면 더 좋은 답이 된다. (S가 최적이라는 것에 모순)

 

2-2. S에 J(i+1) 등장함

2-2-1. S의 x번째에 J(i+1) 등장 

같은 자리에 i+1나오는거니까 OK

 

2-2-2. S의 y번째에 (y<x) J(i+1) 등장

job이 있으면 있는 채로 교환

i+1은 같은 자리로 갔다!

앞쪽으로 간 profit은 없어질 수 없다.

위치만 바꼈고 얻는 profit은 같기때문에 정답 유지(답이 바꼈지만)

 

2-2-3. S의 y번째에 (y>x) J(i+1) 등장 => 불가능

1부터 i까지 데드라인에 꽉차있다.