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

1700번: 멀티탭 스케줄링

문제

멀티탭을 바꿔 끼는 최소 횟수를 구하는 문제로 일단 문제 자체는 간단해 보입니다. 간단해 "보일" 뿐입니다.

접근

문제를 봐도 떠오르는 게 없습니다. 그럼 일단 쉬운 아이디어부터 생각해 봅니다.

브루트 포스 (Failed)

멀티탭에 다 찼을 시점 부터 새로운 물건을 꽂으려고 할 때 특정 위치에 꽂는 모든 경우를 구합니다.

[2 3 1 2 7] 로 주어졌을 때 아래와 같은 방식으로 구하면 7로 도달했을 때 횟수가 2, 3이 되고 이 중 가장 작은 횟수는 2가 됩니다.

그러나 이는 멀티탭 구멍의 개수가 N이고 사용 횟수가 K일 때 N + N^2 + .... + N^(K-N) 번을 반복하고 이 크기만큼 데이터를 저장해야 하기 때문에 시간 초과 또는 메모리 초과가 발생합니다.

사용 빈도 (Failed)

아까 위의 그림을 자세히 보면 [2,3]일 때 1을 3이 있는 위치에 갈아 끼우는 것보다 2가 있는 위치에 갈아 끼우는 것이 더 적게 나타났습니다. 그 이유는 3은 더 이상 쓸 일이 없는 반면 2는 한 번 더 사용해야 하기 때문입니다. 따라서 1을 3의 위치에 꽃으면 2번은 꽂혀 있는 상태이므로 2가 필요한 상황일 때는 굳이 갈아 끼울 필요가 없어지게 됩니다. 하지만 이런 풀이에도 반례는 존재합니다.

반례

[1,2,3,4,1,2,3,4], N=3

빈도수가 같은 경우 입니다. 앞 1,2,3은 멀티탭이 일부 비어있기 때문에 건너뛰고 4부터 시작해 봅시다.

1 2 3 전부다 나중에 한 번 씩 더 사용해야 합니다. 그러나 4를 어디에 꽂느냐에 따라 그 결괏값이 달라집니다.

1을 4로 바꿨을 경우, 바로 다음 1이 들어오기 때문에 한번 더 바꿔야 합니다. 이때 4,2,3은 전부 하나씩 더 사용하게 되는 데, 4를 1로 바꾸게 되면 마지막 4가 들어올 때 [1,2,3]만 있으므로 1을 4로 한번 더 바꿔서 총 3번을 바꾸게 됩니다.

1이 아닌 3을 4로 바꾸게 된다면 [1,2,4]가 되므로 1, 2에서는 따로 바꿔 낄 필요가 없습니다. 3에서는 4를 제외한 나머지 물건을 사용하지 않으므로 [1,2] 중 하나를 선택해서 한 번 더 교환합니다. 이렇게 해서 총 2번을 바꾸게 됩니다.

따라서 사용 빈도가 낮은 물건을 교환하는 알고리즘은 정확하지가 않습니다.

가장 늦게 사용될 물건을 교체

아까 반례에서 사용 빈도가 전부 같아도 어느 위치를 고르냐에 따라 그 횟수가 달라지는 것을 볼 수가 있었습니다. 4를 사용할 때 3을 4로 교체했습니다. 그리고 이 3은

기존에 존재하던 [1,2,3]중에 가장 늦게 사용될 물건이었습니다. 즉, 어차피 가장 늦게 사용할 물건은 굳이 멀티탭에 꽂을 이유가 없기 때문에 3을 4로 교체한 것입니다. 따라서 사용 빈도가 아닌 늦게 사용될 물건들을 교체하는 알고리즘을 사용해야 합니다. 다른 예로도 확인할 수 있습니다.

[1,2,3,2,3,2,3,1,1,1] N=2

두 번째까지 멀티탭을 [1,2]로 채우고 3이 들어올 때 1은 한참 뒤에 등장하므로 1을 3으로 교체하면 이걸로 한번, [2,3] 반복될 때는 멀티탭에 [2,3]이 끼워져 있으므로 교체를 하지 않다가 다시 1이 등장하면 [2,3] 중 하나를 바꿔서 총 2번을 교체하지만 1이 아닌 2를 교체해 [1,3]으로 만들면, 1 교체해서 1번, [1,3]에서 2가 들어올 때 1을 2로 교체해서 2번, 마지막 1 들어올 때 [2,3]에서 한번 더 교체해야 하므로 총 3번 교체해야 합니다.

코드 보기 (C++)

 

#include <iostream>
#include <vector>
using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int cnt[101], dp[101], A[101];
    int N, K, x, ans;
    vector<int> multi_tap;
    
    fill_n(cnt, 101, 0);
    fill_n(dp, 101, 0);
    cin >> N >> K;
    for(int i = 0; i < K; i++) cin >> A[i];

    ans = 0;
    for(int i = 0; i < K; i++) {
        int x = A[i];
        // 똑같은게 있는 지 찾기
        bool is_exists = false;
        for(int j = 0; j < (int)multi_tap.size(); j++) {
            if(multi_tap[j] == x) {
                is_exists = true;
                break;
            }
        }
        if(is_exists) continue;

        if(multi_tap.size() < N)
            multi_tap.push_back(x);
        else {
            fill_n(dp, 101, K);
            // 처음 등판하는 인덱스 구하기
            for(int j = i+1; j < K; j++) {
                if(dp[A[j]] == K)
                    dp[A[j]] = j;
            }
            // 가장 거리가 먼 놈 구하기
            int target = 0;
            for(int j = 0; j < N; j++) {
                if(dp[multi_tap[target]] < dp[multi_tap[j]])
                    target = j;
            }
            multi_tap[target] = x;
            ans++;
        }
    }
    cout << ans << '\n';
    return 0;
}

끗

사실 여기서 사용된 알고리즘은 메모리 관리(페이지 교체) 알고리즘 중 하나인 OPT 알고리즘과 100% 일치합니다. 가장 나중에 사용하는 페이지를 교체하는 방식으로 페이지 적중률, 그러니까 이 문제로 치면 물건을 교체할 필요가 없는 확률이 높아 성능이 상당히 좋은 알고리즘입니다. 하지만 앞에 들어올 페이지의 내용을 알고 있어야 하기 때문에 실제로는 사용하지 않고 다른 페이지 교체 알고리즘의 성능을 측정할 때 같이 비교대상이 되는 알고리즘입니다.

그래서 아마 운영체제를 막 공부하기 시작하는 컴공 2 ~ 3학년인 분 아니면 이거 자체를 떠올리기가 엄청나게 어렵다고 생각하고 또 알고 있어도 쉽지 않을 거라고 생각합니다. 저도 대학생 시절에 운영체제를 배우긴 했지만 졸업 한지도 1년 넘어가고 알아도 FIFO, LRU 이런 것만 알지 OPT가 나올 거리곤 꿈에도 몰랐네요. 예전에 NMK 풀었을 때 하고 비슷한 느낌이었는데 그나마 멀티탭 스케줄링이 훨씬 쉽다고 생각합니다. NMK는 무슨 이해도 안 되는 공식이었는데... 지금도 이해 못 하고 있고요. OPT는 이 문제 풀고 난이도 기여에서 깨달았습니다.