Coding Story

머신 스케줄링 어떤 작업을 처리하는 동일한 기계가 m개 존재하고 처리해야 할 작업이 n개 있다고 하자. 이 기계를 풀가동하여 가장 최소의 시간에 작업들을 끝내고자 한다. 이것을 머신 스케줄링이라한다. 이 문제의 최적의 해를 찾는것은 어렵지만 LPT(longest processing time first) 방법을 통해 근사의 해를 찾을 수 있다. LPT(Longest Processing Time first) LPT는 가장 긴 작업을 우선적으로 가장 먼저 사용가능하게 되는 기계에 할당하는 것이다. 맨 위의 표는 각 작업의 기계 사용 시간이다. 미리 정렬되어 있다고 가정한다. 최소 힙은 모든 기계의 종료시간을 저장하고 있다. 초기의 모든 기계의 종료시간은 0이고, 힙에서 최소 종료시간을 가지는 기계를 삭제하여 ..

우선순위 큐(Priority Queue) 1. 우선순위 큐란? 보통의 큐는 선입 선출(FIFO)의 원칙에 의하여 먼저 들어온 데이터가 먼저 나가게 된다. 그러나 우선순위 큐는 데이터들이 우선 순위를 가지고 있고 우선 순위가 높은 데이터가 먼저 나가게 된다. 우선순위 큐는 2가지로 구분할 수 있다. 최소 우선순위 큐는 가장 우선 순위가 낮은 요소를 먼저 삭제하고, 최대 우선순위 큐는 반대로 가장 우선 순위가 높은 요소가 먼저 삭제된다. 우선순위 큐는 대표적으로 시뮬레이션 시스템, 네트워크 트래픽 제어, 운영체제에서의 작업 스케쥬링, 수치 해석적인 계산 등 컴퓨터의 여러 분야에서 이용된다. 우선순위 큐는 배열, 연결 리스트, 힙으로 구현이 가능한데, 가장 효율적인 구조는 힙이다. 2. 우선순위 큐의 구현 방..