Programmers - 선입 선출 스케줄링

---

title: Programmers - 선입 선출 스케줄링
date: 2022-08-23
tags:

• Algorithm
• Parametric Search

---

https://school.programmers.co.kr/learn/courses/30/lessons/12920

문제 요약

각 CPU의 처리 시간 및 처리해야할 작업의 개수가 주어진다.
각 코어는 하나의 작업만 처리하며 작업이 빈 코어 중 앞 번호의 코어부터 작업을 처리한다.
코어 번호는 1부터 시작하며, 마지막 작업을 처리하는 코어 번호를 return한다.

문제 풀이

잘못된 풀이로 인하여 이틀이라는 시간을 헛되이 낭비한 문제이다.

Two Algorithm

10개의 작업, 그리고 코어는 [1,2,3,4]인 경우이다.
전자의 풀이는 작업이 끝나는 시각을 기준으로 하여, 해당 시각에 끝나는 코어 중 가장 작업이 긴(가장 과거에 작업을 시작한) 코어부터 작업을 진행한다.
이 경우 그림처럼 마지막 작업 순서가 배정이 되며, 이 경우 3번 코어가 마지막 작업을 담당한다.
그러나 이 문제는 마지막 작업을 처리하는 코어의 번호로, 이는 가장 마지막에 작업을 배정받은 코어를 찾는 것과 동일하다.
작업을 배정받는 시각을 기준으로 확인한다면 후자의 그림과 같이 1번 코어부터 배정이 되며, 이 경우 1번 코어가 마지막 작업을 담당하는 것이다.

후자 방식으로 접근을 하였어야 하지만 전자 방식으로 잘못 접근하여 시간을 낭비한 문제이다.


이러한 병렬 처리가 가능할 경우 복잡한 알고리즘 대신 Parametric Search를 이용하여 n개 이상의 작업이 처음으로 할당되는 시간을 찾는다.
찾은 시간은 마지막 작업이 배정되는 시각으로, 이 때 배정 가능한 코어들을 queue에 집어넣으며, 앞의 코어부터 조회하기에 넣은 순서대로 확인하면 된다.

프로그램

#include <vector>
#include <queue>

using std :: vector ;
using std :: queue ;

int solution ( int n , vector < int > cores )
{
    int answer = 0 ;
    int iCoreSize = cores.size () ;
    int iLeft = 1 ;
    int iRight = n * cores [ 0 ] ;
    int iMid = ( iLeft + iRight ) >> 1 ;
    int iTime = 0 ;
    queue < int > qCore ;



    while ( iLeft <= iRight )
    {
        long long llTemp = 0 ;

        for ( int i = 0 ; i < iCoreSize ; ++i )
        {
            llTemp += iMid / cores [ i ] + 1 ;
        }

        if ( n <= llTemp )
        {
            iTime = iMid ;
            iRight = iMid - 1 ;
        }
        else
        {
            iLeft = iMid + 1 ;
        }

        iMid = ( iLeft + iRight ) >> 1 ;
    }

    for ( int i = 0 ; i < iCoreSize ; ++i )
    {
        int iInsertTime = iTime - iTime % cores [ i ] ;        // Remove remainder

        if ( iTime == iInsertTime )
        {
            qCore.emplace ( i ) ;            // Insert time (Upper 14 bits) | Index (Lower 14 bits)
        }

        n -= ( iTime - 1 ) / cores [ i ] + 1 ;
    }
    while ( 0 != n )
    {
        answer = qCore.front () ;
        qCore.pop () ;
        --n ;
    }


    return answer + 1 ;
}