728x90 SJF 썸네일형 리스트형 [CPU scheduling] SJF(Shortest Job First) & SRTF(Shortest Remaining Time First) 백준알고리즘 11399번을 풀다가 생각난김에 머리 속에 있던 내용들을 정리하려고 한다. SJF(Shortest Job First)란 CPU가 scheduling을 할때 실행시간이 짧은 프로세스부터 우선순위로 처리하는 방식으로, 가장 최적의 평균 대기시간을 제공하는 방식이다. 하지만 SJF는 실제로 적용되기 어려운 점이 있다. 프로세스마다 얼마나 CPU를 이용해야하는지 돌리기 전에는 알 방법이 없기 때문이다. 그래서 계산을 통한 예측으로 시간을 판단한다. 예를들면 다음과 같다. 프로세스 p1, p2, p3, p4가 각각 실행시간 5, 7, 2, 4의 실행시간을 갖고 CPU를 점유하기를 대기하고 있을 떄 전체 대기 시간의 합이 최소가 되기 위해서는 p3-> p4-> p1-> p2 순서대로 처리가 되어져야한다.. 더보기 [백준알고리즘] 11399번: ATM -C, Python [백준알고리즘] 11399번: ATM -C, Python https://www.acmicpc.net/problem/11399 11399번: ATM 첫째 줄에 사람의 수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 각 사람이 돈을 인출하는데 걸리는 시간 Pi가 주어진다. (1 ≤ Pi ≤ 1,000) www.acmicpc.net 그리디 알고리즘의 대표적인 예라고 생각하는 문제이다. 이 문제는 CPU scheduling 기법 중 하나인 SJF(Shortest Job First)을 알고 있다면 쉽게 풀 수 있는 문제이다. 이 문제도 마찬가지로 처리시간이 짧은 순서대로 정렬을 해서 처리를 해주면 된다. 다른 분들은 이 부분을 위해서 시간복잡도가 빠른 퀵 정렬 등을 사용해서 정렬을 해주었지만, 여기서 .. 더보기 이전 1 다음