|
그리디를 활용한 문제
|
|
■ 간단한 스케줄링 문제
- 하나의 CPU, N개의
Job, nonpreemptive 스케줄링은 shortest job first가
대기시간 최소화의 최적해
- 여러개의 CPU인 경우
다양한 최적해가 있음
■ 온-라인 알고리즘과 오프-라인 알고리즘
- 온-라인 알고리즘은 자료 하나 씩 입력 즉시 처리해야
함
처리한 결과는 수정할 수 없으며,
대부분 최적화 어려움
(예)
CPU 스케줄러, bin-pack(자루에 물건 넣기) 알고리즘
- 오프-라인 알고리즘은 자료를 모아서 가공(정렬)하여
처리함
|
