728x90 최적화 썸네일형 리스트형 [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 순서대로 처리가 되어져야한다.. 더보기 [알고리즘]Knuth's optimization 크누스 최적화 백준의 11066번 문제를 풀다가 발견한 최적화 기법이다. (문제를 해결했던 코드) 이 알고리즘은 동적 계획법으로 해결하는 문제에서 특수한 조건일 때 시간 복잡도를 \(O(n^3)\)에서 \(O(n^2)\)까지 줄일 수 있는 강력한 알고리즘이다. 사용할 수 있는 동적 계획법의 종류에는 이차원 배열인 \(C\)와 \(C\)를 이용한 Dynamic Programming을 적용한 이차원배열인 \(DP\)가 있다고 했을 때 다음과 같은 조건이 필요하다. 점화식의 형태: \(DP[i][j] = min(DP[i][k] + DP[k][j]) + C[i][j]\) \((i < k < j)\) 사각 부등식: \(C[a][c] + C[b][d] 더보기 이전 1 다음