링크

선입 선출 스케줄링

난이도

  • 프로그래머스 난이도 4
    • 이분법뿐만 아니라 추가적인 계산을 구하느냐가 관건

문제요약

접근

  • 선입선출 그대로 적용
    • 효율성은 0점
  • 좀더 효율적으로 생각해보기
    • 언제 모든 코어가 일을완료하는지 알고나서 마지막 코어가 몇번인지를 계산하기
    • 마지막 코어가 중요

간단 알고리즘

  • n은 처리해야할 작업
  • 이분법
    • 이분법은 left, right로 left=1, right=10000*10000로 했다(그냥 크게 만들어보았다.)
    • right-left==1이될때까지 반복
    • mid= left+right // 2로 중간값계산
    • mid(시간)동안 하나의 코어가 작업을 완료한 개수는 mid//코어처리시간 +1 이된다.
      • 1을 더하는 이유는 시작하자마자 바로 작업을 부여받고 시작하기 때문
      • //로 몫을구해 해당 시간동안 몇개의 작업을 처리했는지를 파악가능
      • 코어 처리시간이 3, 지나간 시간 10이면 10//3==3이고 1을 더해서 4개 작업을 처리한것이다.
        • 손으로 확인해보자
    • 모든 코어가 해당 시간동안 처리한 임무의 총합이 n보다 크거나 같으면
      • 범위를 낮춘다. right=mid
    • 총합이 n보다 낮으면
      • 범위를 높인다 left=mid
    • 반복문을 나왔을때 left가 n 또는 n보다 작은것중에 최대의 작업를 수행하는 시간이된다. -> time으로 변수 저장
      • 후자의 경우 추가적인 계산이 필요하다.
  • 후처리
    • time동안 처리한 작업이 n과 같을때
      • time % 코어의 처리시간이 0이 되는것중에 마지막 코어 번호가 정답
      • 그 이유는 나머지가 0이라는 의미가 해당 시간에서 이제 코어가 작업을 부여받았다는 의미가 된다. - 중요
      • 그러므로 나머지가 0이된 코어들 중 마지막의 코어가 해당시간에 마지막으로 작업을 부여받았다는 의미가 되며 정답이된다.
        • 조건중에 2개 이상의 코어가 남을 경우 앞의 코어부터 작업을 처리 합니다.라는 조건을 통해 위와 같이 처리된다.
    • time동안 처리한 작업이 n보다 작을때
      • time을 1씩 느리면서 n보다 커지는 시간을 찾는다. - 새로운 time을 찾는다.
      • 처리한 작업량이 n보다 커졌을때의 time에서 다시 time % 코어의 처리시간들을 구해서 0이되는 코어를 배열로 정리한다. - > workCore로 변수지정
      • 정답은 workCore[처리해야할 작업-처리한 작업-1]로 나온다.
        • 파이썬의 배열에서 -1은 뒤에서 순회한다. a[-1]은 맨뒤의 요소
        • 처리해야할게 50, 처리한게 53일때 추가로 3개의 코어가 작업을 했다는 의미가 된다.
        • 그러면 해당 시간에 작업을진행한 코어들을 모아야한다(workCore로 나머지가 0인코어들)
        • 이후 배열의 뒤에서 3개의 요소는 필요없고, 마지막으로 처리하는 코어는 4번째 요소가 되기 때문에 처리해야할 작업-처리한 작업-1을 통해 뒤에서 4번째 요소를 찾아낸다.

후기

  • 시간동안 처리한 작업한 갯수를 구하는 방식을 알고나면 좀더 빠르게 접근이 가능했다.
  • 이분법을 언제나 헷갈려서 그부분이 오래 걸렸다.
    • 기준보다 같거나 클때 right에 mid를 넣는게 왜인지를 알 수 있었다.
    • 최대한 정답이 되는 기준에서 최소로 되는 값을 원하기 때문에
  • 후처리 부분도 위에서 계산 방식을 알고나니 수월했다.
  • 시간동안 처리갯수와 이분법이 핵심이었다.