알고리즘 - Greedy (dead-line Scheduling Problem)

Scheduling problem은 운영체제에서 다루는 개념이다.

• 최대한 적은 시간을 사용하면서 많은 작업을 해야 효율적이다

어떻게 하면 효율적으로 배치할 수 있을까?

●FCFS(First-come , First served)

• 들어온 순서대로 일을 시작한다.
• 도착 순서는 P1->P2->P3이라고 가정하자.

• FCFS의 방식은 p1이 먼저 도착했으니까 p1의 일을 다 끝내기 전까지 p2, p3는 일을 시작하지 못한다.
• P1, P2, P3의 모든 작업이 끝나는데 소요되는 시간은 30이지만, P1, P2, P3가 기다리는 시간은 24+27 = 51이다.
• p2, p3는 p1에 비해 굉장히 적은 시간을 사용하는 작업임에도 불구하고 p1이 끝날 때까지 기다려야 한다.
• 이러한 알고리즘은 굉장히 효율적이지 못하다.

●SJF(Shortest-Job-First)

• 사용하는 시간이 적은 작업부터 시작한다.
• 도착 순서는 P1->P2->P3로 가정하자. (단 같은 시간을 사용할 경우에는 먼저 도착한 사람부터 작업을 시작)

• SJF방식은 도착 순서와 무관하게 적은 시간을 사용하는 작업부터 일을 시작한다. 
• P1이 P2, P3보다 먼저 도착했지만, 많은 시간을 필요로 하는 작업이기에 후순위로 밀리고 시간이 적은 순서대로 P2->P3->P1으로 작업순서가 정해진다.
• 이렇게 된다면 소요되는 시간은 FCFS와 동일하다. 하지만 기다리는 시간 측면에서 엄청난 차이를 보인다.
• P2= 0, P3=3, P1=6으로 FCFS에서의 51 --> SJF에서의 6으로 엄청나게 줄어든 것을 알 수 있다.
• 굉장히 효율적인 알고리즘이라고 볼 수 있다.

●Scheduling with deadline

• 만약 각각의 job이 deadline을 가지고 있다고 가정하자.
•  job은 deadline안에 처리해야 한다.
• 각 job의 deadline과 profit을 고려해서 효율적으로 스케줄링해보자.

 

무식하게 모든 경우의 수를 고려하면 결과는 도출할 수 있을 것이다.

그렇게 한다면 factorial time의 시간 복잡도를 가진다.

-->굉장히 비효율적인 알고리즘이다.

 

효율적인 접근법은 Greedy 하게 푸는 것이다.

1. Profit이 큰 순서대로Sort 한다.
2. 이 작업을 추가하는 게 possible 한 지 impossible 한 지 검사해준다. ->(deadline을 고려)

※sequence와 set의 의미를 명확하게 구분할 줄 알아야 한다.

• 위 그림에서 [2,3]은 possible Scheduling이다. 하지만 [3,2]인 경우에는 impossible Scheduling이다.
• 이러한 경우에 [2,3]은 feasible sequence라고 하고 [3,2]은 feasible set이라고 한다

feasible 한 지 어떻게 검사해야 할까?

• job을 선택하고 job을 feasible set에 넣는다.
• feasible set에 있는 job을 deadline이 작은 것부터 정렬한다.
• 만약 job에 순서가 deadline보다 크다면 그것은 not feasible 하다고 할 수 있다.

궁극적으로 우리는 feasible sequence 중에서 total profit이 maximum 한 것을 찾는 것이다.

 

/*
deadline 스케쥴링 문제
시간을 최대한 적게쓰면서 이익을 최대로 해야한다.
어떤식으로 배치해야 적은 시간을 쓰면서 최대한의 효율을 낼 수있을까?
각각의 job에는 deadline이 존재한다. deadline안에 해야 그 job은 유효하다.
deadline을 넘어선 시간대에 job을 선택하면 그것은 impossible하다.
*/
#include <iostream>
#include <vector>
using namespace std;
vector<int> j, k;
typedef struct Schedule
{
    int deadline;
    int profit;
};
void schedule(int n, Schedule* s, vector<int>& j, vector<int>& k);
bool is_feasible(vector<int>& k, Schedule* s);
int main()
{
    int n;
    cin >> n;
    Schedule* s = new Schedule[n + 1];
    vector<int> deadline;
    vector<int> profit;
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i].deadline;
    }
    for (int i = 1; i <= n; i++)
    {
        cin >> s[i].profit;
    }
    for (int i = 1; i <= n; i++) //profit이 큰 순서대로 정렬한다.
    {
        for (int j = i + 1; j <= n; j++)
        {
            if (s[i].profit < s[j].profit)
            {
                swap(s[i], s[j]);
            }
        }
    }
    schedule(n, s, j, k); //n은 회의 갯수,s는 구조체,j
    int sum = 0;
    //j가 feasible set이다.
    for (int i = 1; i < j.size(); i++)
    {
        sum = sum + s[j[i]].profit; //j배열에 순서대로 넣어줌.
    }
    cout << sum << "\n";
    for (int i = 1; i < j.size(); i++) //j배열에 순서가 job의 순서임.
    {
        if (i < j.size() - 1)
            cout << s[j[i]].profit << " ";
        else
            cout << s[j[i]].profit;
    }
}
void schedule(int n, Schedule* s, vector<int>& j, vector<int>& k)
{
    j.clear();
    j.push_back(0);
    j.push_back(1);
    for (int i = 2; i <= n; i++)
    {
        k.resize(j.size()); //만약 적절하지않다면 k를 원래대로 돌려놓음.
        copy(j.begin(), j.end(), k.begin());
        int cnt = 1;
        //i가 내가 넣어줄려는 job cnt만큼 증가시켜주고 그 자리에 넣어줌.
        //그 자리가 들어가야할 위치임 k에 들어가는 job은 데드라인이 작은순서대로 정렬되어있음. deadline이 같더라더 그 이익이 더 작기때문에 후순위에 배치됨.
         //s[i]의 deadline보다 k배열에 deadline이 커질때 그 자리에 넣어줌. 같으면 넣어주면 안됨. 후순위로 배치해야함.
        while (cnt < k.size() && s[k[cnt]].deadline <= s[i].deadline)
            cnt++;
        k.insert(k.begin() + cnt, i); //해당위치에 job을 넣어줌.
        if (is_feasible(k, s)) //지금 넣어준 job의 집합이 적절한지 체크함.
        {
            j.resize(k.size()); //적절하면 j에 k를 복사.
            copy(k.begin(), k.end(), j.begin());
        }
    }
}
bool is_feasible(vector<int>& k, Schedule* s)
{
    for (int i = 1; i < k.size(); i++)
    {
        if (i > s[k[i]].deadline) //job이 위치한 i와 job에 deadline을 비교해서 만약 i가 크다면 그 작업은 유효하지않다.
            return false;
    }
    return true;
}

시간 복잡도는 n^2를 가진다.

---

👀정리

• job의 이익을 내림차순 정렬한다.
• 일단 무조건 이익이 큰 job을 넣는다.
• 그다음에 내가 이미 넣은 deadline보다 작거나 같은 애들 중에서 자리를 찾아서 넣어줌.
  • deadline별로 k에 정렬되는데 내가 넣어주려는 작업의 deadline [s [i]. deadline]이 s [k [cnt]]의 deadline보다 커질 때 그 자리에 넣어줘야 함. 
    • 왜냐하면 이미 이익이 크고 작은 순서대로 정렬되어있기 때문에 늦게 들어온 job은 deadline이 같더라도 앞에 job보다 우선순위가 낮음.
• 그리고 그 작업이 적절한지체크함
  • 그 적절한지의 체크는 k배열은 job에 배정순위이다.
  • 작업의 배정순위와 작업에 deadine 중에서 작업의 배정순위가 deadline보다 당연히 작아야 한다.
  • 만약 크다면 deadline안에 못했다는 뜻이므로 적절하지 않다.
• 모든 작업이 끝나면 feasible 배열의 순서가 job의 순서이다.