[Programmers] LV.3 선입 선출 스케줄링

정재욱·2023년 4월 13일
0

Algorithm

목록 보기
16/33

Programmes LV.3 선입 선출 스케줄링

문제 설명

처리해야 할 동일한 작업이 n 개가 있고, 이를 처리하기 위한 CPU가 있습니다.

이 CPU는 다음과 같은 특징이 있습니다.

CPU에는 여러 개의 코어가 있고, 코어별로 한 작업을 처리하는 시간이 다릅니다.
한 코어에서 작업이 끝나면 작업이 없는 코어가 바로 다음 작업을 수행합니다.
2개 이상의 코어가 남을 경우 앞의 코어부터 작업을 처리 합니다.
처리해야 될 작업의 개수 n과, 각 코어의 처리시간이 담긴 배열 cores 가 매개변수로 주어질 때, 마지막 작업을 처리하는 코어의 번호를 return 하는 solution 함수를 완성해주세요.

제한 사항

  • 코어의 수는 10,000 이하 2이상 입니다.
  • 코어당 작업을 처리하는 시간은 10,000이하 입니다.
  • 처리해야 하는 일의 개수는 50,000개를 넘기지 않습니다.

문제 풀이

이분 탐색을 사용해서 풀어야 하는 생각이 들었지만, 어떤 기준을 정하고 풀어야 하는지 감이 잡히지 않아서 꽤나 고생한 문제다.

1.만약 n값이 cores의 길이보다 작을 경우, n값이 곧 정답이다.
시작과 동시에 모든 cpu에 차례로 작업이 하나씩 시작되므로, 앞에서부터 n번째 cpu가 마지막 작업을 처리하게 될 cpu이다.
ex) n = 4, cores = [1,2,3,4,5,6,7] -> answer = 4

2.이분탐색을 진행
left, right, mid 값은 시간값이 될 것이며, n과 비교할 것은 n-1 시간동안 처리된 작업의 양이다.
n = 10, cores = [1,2,3,4] 의 예시가 있을 때 다음과 같은 규칙으로 매 시간마다 작업이 진행된다.

  • 1h에는 1의 약수인 1값을 갖는 cpu만이 작업이 추가
  • 2h에는 2의 약수인 1, 2 값을 갖는 cpu가 작업에 추가
  • 3h에는 3의 약수인 1, 3 값을 갖는 cpu가 작업에 추가
  • 4h에는 4의 약수인 1, 2, 4 값을 갖는 cpu가 작업에 추가
  • 5h에는 5의 약수인 1 값을 갖는 cpu가 작업에 추가

따라서 어떤 시간 h에 대해, 진행된 총 작업 수 = 시작(0h)에 진행된 작업 수 + 매 시간(h)에 대해 새로 추가되는 작업 수 이다. 이를 이용해 시간 h일 때 진행된 총 작업 수를 구할 수 있다.

이분탐색을 통해 left, right 값을 이용해서 mid의 값을 얻을 것인데, 위에서 말했듯 이 값들은 시간(h) 이다. 즉, left = min(cores) * n // len(cores), right = min(cores) * n 에서 시작해서, mid = left + right // 2 로 계산해나가며, mid시간의 총 작업수가 타겟 작업수인 n 보다 크거나 같은 지점을 찾는 것이다.

여기서 배열내에 있는 값이 아닌 'n보다 큰 값 중 가장 작은 값'을 구하는 것이기 때문에, 이분탐색에서도 lower bound 알고리즘이라고 볼 수 있다.

3.반복문을 통해 몇 번째 cpu가 마지막이 될 것인지 확인

찾아낸 (h-1) 까지의 총 작업수를 n에서 뺀다. 그러면 남아있는 작업 수는 전부 현재 시간(h) 안에서만 이루어졌다는 것이다.

n = 10, cores = [1,2,3,4] 의 예시에서, 정답은 4h의 1번 cpu다.

3h까지의 작업 수가 9이므로, n - (h-1 까지의 총 작업 수) = 1, 즉 한 개의 작업만 더 실행하면 된다.
따라서, 4h에서 진행 가능한 cpu 중 가장 앞에 있는 cpu인 1이 정답이 되는 것이다.

즉, h - 1시간까지의 총 작업량을 구한 뒤에, h시간의 cpu를 하나씩 진행가능한 상태인지 count하며 n의 값이 채워지면, 그것이 정답이 되는 것이다.

만약 n = 12라면, 3h까지 9개의 작업을 진행하고 나서 3개의 작업이 더 필요하니, 4h의 작업가능한 세번째 cpu, 4번 cpu가 정답이 되는 것이다.

# 파라메트릭 서치
def solution(n, cores):
    if n <= len(cores):
        return n
    n -= len(cores)
    
    # 마지막 작업이 실행되는 시간을 찾아내는 이분탐색 실시
    left = min(cores) * n // len(cores)
    right = min(cores) * n
    while left < right:
        mid = (left + right) // 2
        _sum = 0
        for core in cores:
            _sum += mid // core
        if _sum >= n:
            right = mid
        else:
            left = mid + 1
            
    # 결과로 나온 rignt = 마지막 작업이 코어에 들어가는 시간.
    # 이제부터 해당 시간에 어떤 코어로 작업이 들어가는지 알아내야한다.
    for core in cores:
        n -= (right-1) // croe

    for i in range(len(cores)):
        if right % cores[i] == 0:
            n -= 1
            if n == 0:
                return i + 1





참고 : 개발하는 사막여우

profile
AI 서비스 엔지니어를 목표로 공부하고 있습니다.

0개의 댓글