알고리즘/programmers

[Programmers] 선입 선출 스케줄링

구데타마 2022. 6. 21. 09:11

문제 링크입니다: https://programmers.co.kr/learn/courses/30/lessons/12920

 

코딩테스트 연습 - 선입 선출 스케줄링

처리해야 할 동일한 작업이 n 개가 있고, 이를 처리하기 위한 CPU가 있습니다. 이 CPU는 다음과 같은 특징이 있습니다. CPU에는 여러 개의 코어가 있고, 코어별로 한 작업을 처리하는 시간이 다릅니

programmers.co.kr

우선순위 큐를 이용하면 쉽게 풀 수 있을 것 같은 문제이지만 주어진 조건의 범위가 크기 때문에 힙을 이용할 경우 시간 초과가 발생하는 문제입니다.

해당 문제는 코어 당 작업을 처리하는 시간을 기준으로 최소 시간과 최대 시간을 구하여 해당 범위 내 파라메트릭 서치 기법을 이용하여 풀어야 시간제한 내 AC를 받을 수 있는 문제였습니다.

 

알고리즘은 아래와 같습니다.

1. n이 코어 개수 이하일 경우 작업이 순차적으로 배치되므로 답은 n입니다.

2. 작업 시간이 가장 적게 걸리는 코어와 가장 오래 걸리는 코어를 구하여 해당 코어들만 이용했을 때 소요되는 최소 시간과 최대 시간을 구해줍니다.

3. 2번에서 구한 최소 시간과 최대 시간을 기준으로 파라메트릭 서치를 진행합니다.

3.1 변수 설명

  • mid: 현시점
  • workCnt: mid 시간 전까지 한 작업량
  • curWorkCnt: mid 시점에 한 작업량
  • sum: workCnt와 curWorkCnt의 합을 저장한 변수

3.2 파라메트릭 서치 분기 처리

  • workCnt가 n 이상일 경우: mid 시점에 처리한 작업량을 합치지 않았는데도 n 이상이므로 시점을 앞당김
  • sum이 n 미만일 경우: 시점을 뒤로 미뤄야 함
  • sum이 n 이상인 경우: 정답을 구할 수 있는 구간
    • mid 시점에 작업을 할당받은 코어 중 n개가 되는 시점의 코어가 정답
    • 코어는 0-index가 아닌 1-index인 점을 주의

 

 

개발환경: Programmers IDE

 

지적, 조언, 질문 환영합니다! 질문 남겨주세요~

반응형

'알고리즘 > programmers' 카테고리의 다른 글

[Programmers] 사라지는 발판  (0) 2022.06.25
[Programmers] 불량 사용자  (0) 2022.06.25
[Programmers] 최고의 집합  (0) 2022.06.21
[Programmers] 야근 지수  (0) 2022.06.21
[Programmers] 가장 긴 팰린드롬  (0) 2022.06.21