[Programmers] 선입 선출 스케줄링

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

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

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

해당 문제는 코어 당 작업을 처리하는 시간을 기준으로 최소 시간과 최대 시간을 구하여 해당 범위 내 파라메트릭 서치 기법을 이용하여 풀어야 시간제한 내 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

 

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