[백준] 1700. 멀티탭 스케줄링

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

1700번: 멀티탭 스케줄링

도저히 어떻게 풀어야할지 감을 못잡았다. 찾아보니 페이지 교체 알고리즘과 관련이 있다는 것을 알았다.

 

 

Belady algorithm

페이지 교체 알고리즘이란 메모리에 페이지를 효율적으로 올리기 위해 나왔다.

페이지를 메모리에 올리는데 비용이 많이 들기 때문이다.

 

 

 

물론 메모리에 몇 종류의 페이지를 올려놓고, 같은 페이지가 나오면 메모리에서 가져다 쓰면 된다.

문제는 메모리에 올라와 있는 페이지 말고 새로운 페이지가 등장할 때 발생한다.

 

 

 

새로운 페이지가 등장하면 메모리에 올려야하는데, 이미 메모리에 올라와 있는 페이지 중 어느것을 빼야 나중에 더 좋을지가 문제가 된다.

예를 들어 연속적으로 나오는 페이지가 있는데, 그 페이지를 메모리에서 계속 빼버리면 등장할 때마다 메모리에 올려야하기 때문에 비용이 커진다.

 

 

 

그래서 나온 교체 알고리즘이 여러가지인데, 최적의 방법은 Belady의 알고리즘이다.

하지만 이 알고리즘은 중요한 조건이 있는데, 미래에 나올 페이지의 순서를 알고있어야 한다는 점이다.

고작 페이지 올리는 걸로 미래를 방문할 수는 없다.

따라서 실생활에서 사용할 수 있는 알고리즘은 아니다.

 

 

 

 

 

 

 

풀이

위 내용을 공부하고 다시 멀티탭 스케줄링 문제를 보니 그냥 Belady 알고리즘을 저격하고 만든 것을 알 수 있었다.

 

Belady 알고리즘은 그리디한데, 이유는 다음 원칙에 따라 페이지를 메모리에서 빼기 때문이다.

 

1. 메모리에 있는 페이지일 경우 넘어간다.
2. 메모리에 공간이 남아있는 경우 넣는다.
3. 메모리에 올라간 페이지가 현재 시점 이후에 다시는 나오지 않는다면 뺀다.
4. 메모리에 올라간 페이지들 중, 현재 시점 이후 첫번째로 나오는 시점이 가장 늦는 페이지를 뺀다.

1~2번 원칙은 base case로 그리디 알고리즘이 아니더라도 무조건 수행해야하는 동작이다.

 

 

3번은 어찌 생각하면 당연한데, 굳이 다시 등장할 페이지를 빼는 것보다 다시 등장하지 않을 페이지를 빼는 것이 비용이 더 낮기 때문이다.

 

 

4번이 조금 의아하다. 현재 보고있는 위치부터 이후에 들어올 페이지들을 본 후, 가장 적게 나오는 페이지를 빼면 된다고 생각할 수 있기 때문이다.

 

하지만 이는 생각해보면 위험이 있다.

이미 다시 나오지 않을 페이지는 3번 원칙에서 걸러냈기 때문에 남아있는 페이지는 최소 한번은 나온다.

사용 가능한 플러그가 두개라고 가정하자. 그러면 1 2 3 1 2 3 3 와 같이 페이지의 순서가 정해졌을때,

1. 3번째 위치에서 1을 빼고 3을 넣는다(현재 비용 1).

2. 다음에 1을 만났을 때는 해당 시점 이후에 2가 가장 빈도가 적기 때문에 2를 빼고 1을 넣는다(현재 비용 2).

3. 2 이후에는 다시 나오지 않는 1을 빼고 3을 넣는다.(최종 비용 3).

 

하지만 최적해는 비용이 2이다.

 

즉, 페이지를 교체하는 빈도만 쫒는 것은 최적해에 근사할 수는 있으나 최적해가 아니다.

- 플러그의 개수가 제한되어있기 때문에 중간과정에서 다시 빼버렸던 페이지로 교체되면 필요없는 비용이 발생할 수 있다.

- 또한 연달아 나온다면 비용이 발생하지 않기 때문에 빈도만 쫒는 것은 의미가 없다.

 

반면, 가장 나중에 나오는 페이지라는 것은 무엇을 의미할까?

가장 나중에 나오는 페이지를 p라고 하자.

1. 우선 다시 p가 나올때까지는 p는 나타나지 않기 때문에 p로인한 비용은 발생하지 않는다.

2. p가 다시 나타나는 위치를 $i$라고 할때, $K$번째(가장 마지막 순서)와 가깝다. 따라서 p가 나오는 빈도는 최소 $K-i$ 이다. 또한 연달아 나온다면 비용이 더 줄어들 수 있다.

 

즉, 필요없는 비용을 최소한으로 줄이면서(첫번째 설명) 가장 확실하게 빈도를 줄이는(두번째 설명) 원칙이 4번째 원칙이다.

---

처음에는 사용중인 제품 중 빈도수가 가장 적은 것 순으로 빼는 아이디어를 생각했지만, 위의 설명에 포함된 반례와 아래 반례로 바르지 않은 아이디어임을 알았다.

 

여기서 막혀버렸다. 한번에 여러 구간을 봐야하는 건지도 생각해봤는데, 의미없는 아이디어였다.

 

그래서 Belady 알고리즘을 접하고 그대로 구현했다.

 

다음은 코드이다.

#include <iostream>
using namespace std;

int N, K;
int order[101], plugged[101];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> N >> K;
	
	for(int i=0; i<K; i++) cin >> order[i]; // O(K)
	
    // O(K)
	int ret = 0;
	for(int i=0; i<K; i++) {
		bool flag = false;
		
		// 이미 사용중인 제품인가? O(N)
		for(int j=0; j<N; j++) {
			if(plugged[j] == order[i]) flag = true;
		}
		if(flag) continue;
		
		// 콘센트에 남은 공간이 있는가? O(N)
		for(int j=0; j<N; j++) {
			if(!plugged[j]) {
				plugged[j] = order[i];
				flag = true;
				break;
			}
		}
		if(flag) continue;
		
		// 이후에 나오지 않는 제품이라면 빼고
		// 그런 경우가 없다면 현재 시점 이후, 첫번째로 나오는 시점이 가장 늦는 제품을 뺀다.
        // O(NK)
		int unplug, idx = 0;
		for(int j=0; j<N; j++) {
			int count = 101;
			for(int k=i+1; k<K; k++) {
				if(plugged[j] == order[k]) {
					count = k;
					break;
				}
			}
			if(count > idx) {
				unplug = j;
				idx = count;
			}
		}
		ret++;
		plugged[unplug] = order[i];
	}
	
	cout << ret << "\n";
}

시간 복잡도는 $O(K + NK + NK + NK^2) = O(NK^2)$ 이다.

 

물론 공간을 더 사용하여 우선순위 큐와같은 자료구조를 사용한다면, 시간복잡도에 가려진 연산비용을 줄일 수도 있을 것 같다. 하지만 N과 K가 최대 100이므로 오히려 공간만 낭비하는 수가 될것이다.