[PS][BOJ][Swift] OPT Algorithm - 멀티탭 스케줄링

앞전에 LRU 알고리즘 얘기를 하면서 Programmers의 문제를 풀면서 설명했던 포스팅을 한적이 있다.

Unluckyjung님께서 OPT관련해서도 비스무리한 문제가 있다고 추천을 받아서 문제를 풀게 되었다.

먼저 간단하게 OPT 가 뭔지 알아보자.

OPT Algorithm

앞으로 가장 사용하지 않을 페이지를 내보내는 방식

사실상 가장 이상적인 페이지 교체 알고리즘이다.
FIFO에 비해 다 동작시키지 못하는 해저드나, 페이지 결함의 횟수를 줄여주는데 좋다.

하지만 설명으로 써놨던 앞으로 가장 사용하지 않는 페이지라는 어떠한 특정한 기준치는,
명확한 증거로 작용하여 내놓을 페이지를 결정할수 없다는 점에 있다.

실제 구현한다면 가장 효율적이겠으나, 사실상 불가능에 가까운 알고리즘이다.

위에 이것이 내가 이전 포스트에서 써놓았던 내용인데, 핵심은 두가지다.

• 미래를 예측 하는 알고리즘이다.
• 구현이 거의 불가능하다.

최근 들어서 머신러닝을 통해서 앱이나, 프로그램 이용에 대한 유저의 활용도를 학습시켜서 OPT 비슷한 페이지 교체 알고리즘을 써볼수 있지 않나? 라는 생각을 하지만, 이것도 역시 완벽하게 예측하여 페이지를 교체하긴 힘들것 같다.

분명 오버헤드도 많이 나고 하겠지 뭐..

여튼, 좋은 문제를 추천받아서 OPT처럼 예측하여 스케줄링하는 문제를 풀게되었다.

문제 출처 : https://www.acmicpc.net/problem/1700

문제를 먼저 읽어보고 하고자 하는것을 파악해 보자면 다음과 같다.

• 멀티탭을 사용해야 한다.
• 가장 멀티탭의 전원 교체를 적게 하고 싶다.

우리가 문제를 풀면서 해야 할 것은 이렇게 두가지로 축약해볼수 있다.

멀티탭에서 교체를 한다는 것은 결국은 이미 꽂혀있던것을 최대한 당장 쓸모가 없거나, 나중에 다시 꽂아도 괜찮은것을 빼면서 새로운 신규 코드를 넣으면 될 것이다.

문제는 굉장히 친절하게도 다음에 어떤것을 쓸것인지에 대한 모든 순서가 제시되어있고, 나중에 무엇을 꽂을지, 그리고 어떠한것이 필요 없을지에 대한 모든 근거가 제시가 되어있다.

크게 생각해보면

• 당장 쓸모가 없거나 = 앞으로 나오긴 나오겠지만, 굉장히 나중에 다시 나오는 것
• 아예 필요가 없거나 = 더 이상 쓰지 않을 것

이렇게 두가지로 될텐데 이 중에서도 가장 우선 빼야 할것은 아무래도 더 이상 쓰지 않을 녀석일 것이다.

굳이 다시 쓰지 않을걸 나중에 써야할것보다 먼저 뺄 필요가 있을까?

이것을 그대로 코드로 정리하면

import Foundation


let NK = readLine()!.split(separator: " ").map{Int(String($0))!}
let arr = readLine()!.split(separator: " ").map{Int(String($0))!}

let N = NK[0]
let K = NK[1]

var parent : [Int] = [Int](repeating: -1, count: K + 1)
var dummy : [Int] = [Int](repeating: 0, count: K + 1)

var idx = K - 1
while idx >= 0{
    let val = arr[idx]
    if parent[val] == -1 {
        dummy[idx] = idx
        parent[val] = idx
    }else{
        dummy[idx] = parent[val]
        parent[val] = idx
    }
    idx -= 1
}

var q : [(Int, Int)] = []
idx = 0
var ans = 0
for x in arr {
    var j = 0
    var isFind = false
    // 이미 Queue 내부에 존재하는가!(쓰고 있는 중인지 체크!)
    while j < q.count {
        if q[j].0 == x {
            q[j].1 = dummy[idx]
            isFind = true
            break
        }
        j += 1
    }
    if isFind == true{
        idx += 1
        continue
    }
    
    if q.count < N {// 큐가 다 차지 않은 상태에선 그냥 넣으면 된다.
        q.append((x, dummy[idx]))
    }else{
    //큐가 다 찼으면, 큐의 상태에 따라 우선순위를 두고 뺄건 뺴고, 넣어야 할것을 넣어준다.
        j = 0
        var isOver = -1
        var isDist = -1
        var len = -1
        while j < q.count {
            if q[j].1 < idx {
                isOver = j
            }
            if q[j].1 - idx > len {
                len = q[j].1 - idx
                isDist = j
            }
            j += 1
        }
        if isOver != -1 {
            q.remove(at: isOver)
        }else{
            q.remove(at: isDist)
        }
        ans += 1
        q.append((x, dummy[idx]))
    }
    idx += 1
}

print(ans)

코드는 조금 많이 더러운데, 요지는 내가 지금까지 적었던 글의 내용과 같다.

실제로 OPT가 구현이 된다면 이런식으로 생각되지않을까?
앞으로 나올 것에 대해 정리를하면 굳이 교체하지 않고 자원을 아낄수 있게 된다.