[Swift 알고리즘] 백준_1700 멀티탭 스케줄링

 

 

기숙사에서 살고 있는 준규는 한 개의 멀티탭을 이용하고 있다. 준규는 키보드, 헤어드라이기, 핸드폰 충전기, 디지털 카메라 충전기 등 여러 개의 전기용품을 사용하면서 어쩔 수 없이 각종 전기용품의 플러그를 뺐다 꽂았다 하는 불편함을 겪고 있다. 그래서 준규는 자신의 생활 패턴을 분석하여, 자기가 사용하고 있는 전기용품의 사용순서를 알아내었고, 이를 기반으로 플러그를 빼는 횟수를 최소화하는 방법을 고안하여 보다 쾌적한 생활환경을 만들려고 한다.

예를 들어 3 구(구멍이 세 개 달린) 멀티탭을 쓸 때, 전기용품의 사용 순서가 아래와 같이 주어진다면, 

1. 키보드
2. 헤어드라이기
3. 핸드폰 충전기
4. 디지털 카메라 충전기
5. 키보드
6. 헤어드라이기

키보드, 헤어드라이기, 핸드폰 충전기의 플러그를 순서대로 멀티탭에 꽂은 다음 디지털 카메라 충전기 플러그를 꽂기 전에 핸드폰충전기 플러그를 빼는 것이 최적일 것이므로 플러그는 한 번만 빼면 된다. 

입력

첫 줄에는 멀티탭 구멍의 개수 N (1 ≤ N ≤ 100)과 전기 용품의 총 사용횟수 K (1 ≤ K ≤ 100)가 정수로 주어진다. 두 번째 줄에는 전기용품의 이름이 K 이하의 자연수로 사용 순서대로 주어진다. 각 줄의 모든 정수 사이는 공백문자로 구분되어 있다. 

출력

하나씩 플러그를 빼는 최소의 횟수를 출력하시오.

 

해결 방법

보자마자 페이지 교체 정책을 생각하고 풀었습니다. 하지만 페이지 교체 정책에서 미래에 어떤 페이지가 올지 알 때 어떤 방법이 최적화 된 방법인지 몰라서 헤맸습니다. 후에 페이지 교체 알고리즘에 대해서 공부하니 최적 정책 이라는 것을 배워서 활용했습니다. 최적정책이란, 현재 페이지에서 후에 가장 쓰지 않을 페이지를 교체하는 정책 입니다. 이를 코드에 적용하여 해결하였습니다.

 

import Foundation

func sol() {
  let NM = readLine()!.split(separator: " ").map{Int($0)!}
  let N = NM[0]
  let M = NM[1]
  var res: Int = 0
  let arr = readLine()!.split(separator: " ").map{Int($0)!}
  var dict: [Int: [Int]] = .init()
  arr.enumerated().forEach { (ind, val) in
    dict[ind, default: []].append(val)
  }
  
  var plug: Set<Int> = .init()
  var ind = 0
  while ind < M {
    let cur = arr[ind]
    ind += 1
    
    if plug.count < N {
      plug.insert(cur)
      continue
    } else if !plug.contains(cur) {
      var tempDict: [Int: Int] = [:]
      plug.forEach{cur in
        tempDict[cur] = arr[ind...].firstIndex(of: cur) ?? Int.max
      }
      let lastKey = tempDict.max{$0.value < $1.value}!.key
      plug.remove(lastKey)
      plug.insert(cur)
      res += 1
    }
    
  }
  print(res)
}

 

 

페이지 교체 알고리즘

최적 정책 : 미래에 참조될 때 까지의 시간이 가장 긴 페이지를 교체 대상으로 선택한다.

LRU (Least Recently Used): 가장 오랜 시간동안 참조되지 않은 주기억 장치 상의 페이지를 교체한다.

FIFO: 가장 오래전에 반입된 페에지를 교체하는 정책 이다. 

 

+ (생각) 최적 정책이 어려운 이유: 페이지기 나중에 어떤 방식으로 교체될지 정확하게 예측하는 것은 미지의 영역입니다. 사용자는 정해진 루틴으로만 메모리를 활용하지 않습니다. 이를 예측하는 것은 불가능에 가깝습니다.