백준 1700번 멀티탭 스케줄링 문제 풀이

 

https://www.acmicpc.net/problem/1700

1700번: 멀티탭 스케줄링

컴공 학부 전공과목 운영체제 수업에서 프로세스 스케쥴링을 배울 때, MIN 알고리즘이었나, 이름은 정확하게 기억이 안나는데 그런 알고리즘 이 하나있었다.

 

특징이라고 하면, 지금 멀티탭 스케줄링과 같이, 제한된 리소스에 순차적으로 프로세스들을 실행을 할 때, 멀티탭에서 빼는 것 처럼, 메모리에 로드된 프로세스를 제거하는 횟수를 최소화 하는 알고리즘 중, 실제로 최적이라고 수학적으로 증명된 스케쥴링 기법이다.

 

하지만, 이 알고리즘을 사용하려면 제약 조건이 하나 있는데, 앞으로 미래에 프로세스가 어떤것이 먼저 실행될 것인지를 전부 알아야 한다는 점이다. 따라서 성능 측정에서만 사용한다고 들었다.

 

요놈 알고리즘의 특징은, 프로세스를 제거해야 하는 상황일 때에는, 앞으로 사용되기 까지 가장 오래 걸리는 프로세스를 제거하는 식으로 동작한다. 앞으로 사용되지 않는 프로세스라면 우선순위 1순위로 제거될 것이다.

 

 

#include <bits/stdc++.h>
using namespace std;
vector<int> O[101];
int ptr[101];
vector<int> A;
set<int> tap;
int main() {
	int N, K;
	cin >> N >> K;
	for (int i = 0; i < K; i++) {
		int t;
		cin >> t;
		A.push_back(t);
		O[t].push_back(i);
	}
	int ans = 0;
	for (int i = 0; i < K; i++) {
		auto cur = A[i];
		if (tap.size() >= N && tap.find(cur) == tap.end()) {
			//should remove
			int victim, val;
			victim = -1, val = 0;
			for (auto& t : tap) {
				if (O[t].size() <= ptr[t]) {
					victim = t;
					break;
				}
				if (val < O[t][ptr[t]]) {
					val = O[t][ptr[t]];
					victim = t;
				}
			}
			ans++;
			tap.erase(victim);
		}
		ptr[cur]++;
		tap.insert(cur);
	}
	cout << ans << endl;
	return 0;

}