프로그래머스 Lv3 선입 선출 스케줄링(복습필요)

문제 해석

n	처리해야 할 작업의 개수
cores	각 코어의 처리시간이 담긴 배열

cores에 담긴 시간이 경과 할 때 처리 작업의 개수를 하나씩 줄여나간다. (2개 이상의 코어가 남을 경우)

---

접근법

완전 탐색의 경우 BigO(n * 코어의 개수) 이므로 시간 초과가 발생한다. 따라서 Parametric Seach를 이용해야한다.

---

1. 파라메트릭 서치란?

 

파라메트릭 서치는 최적화 문제를 결정 문제로 바꾸어 풀어 나가는 기법입니다. 여기서 결정 문제란 'yes' or 'no' 즉 '예' 또는 '아니오:로 답하는 문제를 말합니다. 파라메트릭 서치는 주로 특정 조건을 만족하면서 동시에 가장 적합한 변숫값을 찾아나가는 문제에서 활용되며, 이진 탐색(Binary Search)을 이용하여 구현합니다. 예를 들어, 특정 조건을 만족하는 가장 큰 값을 구하는 최적화 문제에서 이진 탐새을 통해 적합한 해(solution)의 범위를 절반씩 좁혀 나갈 수 있습니다.

 

2. 파라메트릭 서치는 언제 사용하면 좋을까?

앞서 파라메트릭 서치 문제는 이진 탐색을 활요해 해결할 수 있다고 했습니다. 이진 탐색 알고리즘은 입력 데이터가 많거나(e.g 1,000만개 이상) 탐색 범위의 크기가 매우 넓을 때(e.g 1000억 이상) 효율적으로 문제를 해결할 수 있는 방법입니다. 파라메트릭 서치 역시 마찬가지로 입력 데이터가 많거나 탐색 범위의 크기가 매우 넓을 때 사용하면 좋습니다.

 

3. 파라메트릭 서치와 이진 탐색 간의 차이점

그렇다면 파라메트릭 서치와 이진 탐색 간의 차이점은 무엇일까요? 바로 결정 문제냐 아니냐입니다. 파라메트릭 서치는 특정한 조건을 만족하는 해(solution)를 찾을 때 결정 문제를 해결해 나갑니다. 즉, 특정 조건을 만족하느나(yes) 혹은 만족하지 않느냐(no)에 따라 해의 범위를 좁혀 나가는 방법입니다.

 

4. 파라메트릭 서치 동작 과정

이제 파라메트릭 서치의 동작 과정에 대해 알아봅니다. 파라메트릭 서치는 이분 탐색을 기반으로 구현하기 때문에 리스트 내 특정 값을 찾기 위해 시작 인덱스, 중간 인덱스, 마지막 인덱스를 사용합니다. 구체적인 동작 순서는 아래와 같습니다. 예제없이 풀어서 설명하다 보니 이해가 쉽지 않으실 수 있습니다. 아래에 예제와 함꼐 살펴보시면 쉽게 파라메트릭 서치의 동작 과정을 이해하실 수 있을거로 생각합니다.

 

1️⃣ 시작 인덱스와 마지막 인덱스 사이의 중간 값에서 소수점 이하를 버려 중간 인덱스를 정합니다.

2️⃣ 중간 인덱스에 해당하는 값을 활용했을 때 문제에서 주어진 조건을 만족하는지 여부를 확인합니다. 조건에 만족하지 않는다면 시작 인덱스 또는 마지막 인덱스를 수정하여 조건을 만족하는 중간 인덱스를 구합니다.

3️⃣ 조건을 만족한다면 2️⃣ 에서 구한 값이 최적의 해인지 여부를 확인합니다. 최적의 해라면 동작을 중단합니다.

4️⃣ 문제에서 주어진 조건을 만족하며 최적의 해를 구할 때까지 1️⃣~ 3️⃣ 과정을 반복합니다.

 

4.1 파라메트릭 서치 예시

예를들어, 아래 그림1과 같이 사람마다 고유 번호가 있는 10명의 사람이 성적에 따라 오름차순 정렬되어 있다고 가정해 보겠습니다. 여기서 "학점이 A(4.0) 이상"을 결정 문제의 조건이라고 하겠습니다. 해당 조건의 A 학점을 받은 사람 중 성적이 가장 낮은 사람을 찾는 문제를 파라메트릭 서치 기법으로 풀어보겠습니다.

 

그림 1. 파라메트릭 서치 동작 예시

(1) 먼저 시작점인 1과 끝점인 10의 중간점은 (1 + 10) / 2 = 5.5 에서 소수점 이하를 버린 5입니다. 중간점이 조건을 만족하는지 확인합니다(그림 2 참고). 편의상 시작점과 끝점은 녹색으로, 중간점은 파란색으로 표현하겠습니다. 중간점인 5가 조건을 만족하지 않는다면, 이미 1부터 10번까지의 사람이 성적 순으로 정렬되어 있다는 점에서, 사실상 5번을 포함해 번호가 낮은 사람들에 대해서는 조건의 만족 여부를 검증해 볼 필요가 없습니다.

 

그림 2. 파라메트릭 서치 동작 과정1

(2) 아래의 그림3과 같이 검증이 불필요한 사람은 회색으로 표현하겠습니다. 이제 시작점은 6, 끝점은 여전히 10이기 때문에 중간점은 8이 됩니다. 이번에는 중간점 8번 사람이 학점이 A이 이상이라고 답했습니다. 따라서 끝점은 중간점 한 칸 앞인 7이 됩니다.

그림 3. 파라메트릭 서치 동작 과정2

(3) 마찬가지로 8번 사람이 A 학점 이상이며 9번, 10번 사람은 8번 사람보다도 성적이 높기 때문에 8번 사람 이후로는 학점을 물어보지 않아도 됩니다. (그림4 참고). 이제 끝점을 중간점의 한 칸 앞인 7로 옮기면 새로운 중간점은 시작점과 같은 6이 됩니다. 중간점에 해당하는 사람이 A 학점 이상이라고 답했기 때문에, A 학점이면서 성적이 가장 낮은 사람은 6번 사람임을 알 수 있습니다. 만일 6번이 A 학점이 아닐 경우에는 7번 사람의 학점도 알 수 없지 때문에 한 번 더 학점을 물어봐야 합니다.

 

4.2 파라메트릭 서치의 시간 복잡도

이진 탐색은 시작, 중간, 끝 인덱스를 활용하며 탐색 횟수별로 확인하는 데이터의 개수가 절반씩 줄어들기 때문에 시간 복잡도가 O(logN) 입니다. 마찬가지로 파라메트릭 서치 역시 O(logN) 의 시간 복잡도를 갖습니다.

 

---

문제 풀이

총 작업 시간과 총 작업량으로 접근한다.

먼저 가장 작은 작업 시간을 갖는 maxcore, 가장 큰 작업 시간을 갖는 mincore를 구한다.

    // 시간당 작업량의 최소와 최대를 구한다.
    for(int i = 0; i < size; i++)
    {
        if(mincore > cores[i]) mincore = cores[i];
        if(maxcore < cores[i]) maxcore = cores[i];
    }

 

최소 시간을 갖는 코어가 (2, 2, 2, 2) 있을 때 n의 작업량을 처리하기 위해서 걸리는 시간은 mincore * (n - size) / size이다.

최대 시간을 갖는 코어가 (4, 4, 4, 4) 있을 때 n의 작업량을 처리하기 위해서 걸리는 시간은 maxcore * (n - size) / size이다.

    mintime = (mincore * (n - size)) / size;
    maxtime = (maxcore * (n - size)) / size;

 

파라메트릭 서치를 사용하기 하기 위해서 조건 반복문을 설정한다. 그리고 중간 시간 값을 구하고, 문제에서 모든 코어가 한번씩 처리 했다고하므로 현재 처리 된 일을 size가 된다.

    while(mintime <= maxtime)
    {
        // 작업 시작부터 코어 개수 만큼 작업이 할당 된다.
        int corework = size;
        int currentwork = 0;
        
        // 최소와 최대의 중간 시간을 구한다.
        midtime = (mintime + maxtime) / 2;

 

중간 시간을 각 코어의 일을 처리하는데 걸리는 시간으로 나누면 코어가 처리한 일의 양이 되므로 

모든 코어를 순회하면서 처리 된 일의 양을 구한다. 그리고 midtime % i == 0 이면 새로운 코어가 추가 되는 것이므로

currentwork를 증가시킨다.

        // 중간 시간을 현재 시점으로 해서 코어별로 작업량을 구한다.
        for(int i : cores)
        {
            // 현재 시간을 시간당 작업량으로 나누면 현재 코어의 작업량이 된다.
            corework += (midtime / i);
            // 현재 막 작업을 할당 받은 코어의 개수를 구한다.
            if((midtime % i) == 0) ++currentwork;
        }

 

처리한 일의 양이 n보다 작다면 시간이 부족한 것이므로 시간 범위를 큰 쪽으로 좁혀준다.

if(n > corework) mintime = midtime + 1;

 

처리한 일의 양이 n - currentwork 보다 크거나 같다면 시간이 넘치는 것이므로 시간 범위를 작은 쪽으로 좁혀준다.

else if(n <= (corework - currentwork)) maxtime = midtime -1;

 

처리한 일이 양이 n - currentwork < n <= corework 일 경우 우리가 지정한 범위안에 있는 거이므로 현재 중간 시간을 기준으로 마지막으로 작업한 코어의 인덱스를 찾는다.

            int tmpwork = corework - currentwork;
            for(int i = 0; i < size; ++i)
            {
                //min과 max사이에서 현재 작업량을 찾고, 어떤 코어에서 n만큼 작업량을 채우는지 확인하는 코드
                if((midtime % cores[i]) == 0) ++tmpwork;
                
                if(tmpwork == n) return (i + 1);
            }
        }

 

마지막으로 n이 size보다 작거나 같다면 한 사이클안에 모든 일이 처리 되므로 n을 리턴하면 된다.

if(n <= size) return n;

 

아래는 전체 코드이다.

// Case3: Parametric Search를 이용, 대략 BigO(log n)
// 매개체인 작업 시간을 통해 최소 최대 범위에서 Binary Search하면서
// 작업시간과 연관된 현재 작업시점의 작업량을 구한다
// 그 작업량이 n과 같을 때 해당 코어를 반환한다
#include <vector>

using namespace std;

#define MIN_CORE_WORKTIME 10000
int solution(int n, vector<int> cores) {
    int size = cores.size();
    int mincore = MIN_CORE_WORKTIME +1;
    int maxcore = 0;
    int mintime = 0;
    int maxtime = 0;
    int midtime = 0;
    
    // 작업 시작 시점부터 하나씩 작업이 할당되기 떄문에 코어수 보다 작으면 바로 해당 코어를 반환한다.
    if(n <= size) return n;
    
    // 시간당 작업량의 최소와 최대를 구한다.
    for(int i = 0; i < size; i++)
    {
        if(mincore > cores[i]) mincore = cores[i];
        if(maxcore < cores[i]) maxcore = cores[i];
    }
    
    // 모든 코어가 동일한 최소, 최대 값을 가진다고 가정할 때 최대와 최소 걸리는 시간을 구한다.
    mintime = (mincore * (n - size)) / size;
    maxtime = (maxcore * (n - size)) / size;
    
    while(mintime <= maxtime)
    {
        // 작업 시작부터 코어 개수 만큼 작업이 할당 된다.
        int corework = size;
        int currentwork = 0;
        
        // 최소와 최대의 중간 시간을 구한다.
        midtime = (mintime + maxtime) / 2;
        
        // 중간 시간을 현재 시점으로 해서 코어별로 작업량을 구한다.
        for(int i : cores)
        {
            // 현재 시간을 시간당 작업량으로 나누면 현재 코어의 작업량이 된다.
            corework += (midtime / i);
            // 현재 막 작업을 할당 받은 코어의 개수를 구한다.
            if((midtime % i) == 0) ++currentwork;
        }
        
        // corework - currentwork < n <= corework 인 경우를 찾고, corework - currentwork부터 추가되는 코어 수를 n과 비교화며
        // 정답을 찾는다.
        // n이 현재 시점(midtime)에서 코어들의 총 작업량보다 크다면 최소 시간(mintime)을 midtime으로 끌어 올린다.
        // n <= (corework - currentwork) 경우는 반대쪽에 있으므로 최대 시간(maxtime)을 끌어 내린다.
        if(n > corework) mintime = midtime + 1;
        else if(n <= (corework - currentwork)) maxtime = midtime -1;
        else
        {
            // corework - crrentwork < n <= corework 사이에 있으면
            // 현재 막 작업을 할당 받은 코어 중에 n개가 되는 코어를 구할 수 있다.
            // 참고 : corework - currentwork <= n <= corework 라고 가정하면
            // n = corework - currentwork 일수도 있다는 뜻인데 실제 들어가면 아닐 수도 있다.
            // 이유는 (midtime % cores[i]) == 0 이면 바로 tmpwork가 하나 증가하기 때문에
            // n != corework - currentwork가 아닐 수 있다.
            int tmpwork = corework - currentwork;
            for(int i = 0; i < size; ++i)
            {
                //min과 max사이에서 현재 작업량을 찾고, 어떤 코어에서 n만큼 작업량을 채우는지 확인하는 코드
                if((midtime % cores[i]) == 0) ++tmpwork;
                
                if(tmpwork == n) return (i + 1);
            }
        }
    }
    return 0;
}

 

참조 블로그

https://www.mstst33.com/programmers-first-in-first-out-scheduling/162/

[Programmers] 선입 선출 스케줄링 - 개발자의 소소한 일상

https://heytech.tistory.com/97

[알고리즘] 파라메트릭 서치(Parametric Search)에 대해 알아보자!