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

19 Apr 2021

문제

페이징 교체 알고리즘에 대해 들어보셨나요? 운영체제 과목에서 배우는 알고리즘 중 하나인데요. 해당 알고리즘을 차용해서 만든 문제라고 생각됩니다. 안배워보신 분이라면, 페이지 교체 알고리즘에 대해 설명한 medium 포스팅을 한 번 읽어보시면 좋겠습니다. 특히 현실 내에서는 구현이 불가능한 최적 페이지 교체 기법을 공부해보시고, 해당 기법을 바탕으로 코드 구현하시면 되겠습니다.

페이징이란 프로세스를 작은 크기로 나누어서 외부 단편화를 해결하기 위한 방법입니다.

외부단편화 : 프로세스가 메모리에 적재될 때, 프로세스가 요구하는 메모리는 70MB이고, 메모리에 남아있는 공간은 100MB이라고 생각해봅니다. 당연히 들어갈 수 있어야 마땅하겠지만, 만약 메모리가 50MB, 50MB씩 나뉘어있다면 어떻게 될까요? 프로세스가 적재되지 못하는 현상이 발생합니다. 이를 해결하기 위해 빈 자리를 남기고 나머지를 다 메모리에서 위로 몰아버리는 Compaction도 가능하지만, 이렇게 빈 메모리를 모으는 데에 생기는 오버헤드와 비효율성때문에 페이징이 고안되었습니다.

프로세스를 작은 크기로 나눈 것을 페이지라고 이야기합니다. 프로세스의 요청에 따라 운영체제는 이러한 페이지를 메모리에서 빈 프레임으로 로딩하게 됩니다. 프레임에 페이지를 올릴 때에는 PCB 등을 저장해주어야 하므로, Page fault가 발생하게 됩니다. 빈 프레임이 없을 때에는 어떤 프레임을 비우고 다른 페이지를 올려주어야겠죠? 이 때 비워낼 프레임을 선택하는 알고리즘을 페이지 교체 알고리즘이라고 합니다.

해당 문제 풀이에 사용되는 페이지 교체 알고리즘은, 최적 페이지 교체 입니다. 가장 오랫동안 사용되지 않을 페이지를 비우고, 그 자리에 페이지를 넣게 됩니다. 이는 반드시 최적입니다. (최적이라는 뜻은, page-fault가 가장 적게 발생한다는 의미입니다.) 다만 이는 오랫동안 사용되지 않을 페이지가 무엇인지 알아야만 구현 가능한 알고리즘인데, 실제 컴퓨터의 동작에서는 앞으로 사용될 페이지의 리스트를 받을 수 없기 때문에 현실에서는 구현이 불가능한 알고리즘입니다. 다른 알고리즘과의 비교 연구 목적으로만 사용되는 이론상의 알고리즘입니다.

위의 내용을 이해하셨다면 이제 문제를 풀 수 있습니다.

pseudo-code

for 사용할 전자기기 목록을 순회하며
	if 이번에 사용할 전자기기가 멀티탭에 존재하는 경우 : continue
	
	if 교체해야하는 경우 :
		for 현재 멀티탭에 꽂혀있는 전자기기 목록을 순회하며 :
			앞으로 사용될 전자기기 목록에서, 가장 멀리 스케쥴되어 있는 전자기기를 고르고 교체한다.
			단, 앞으로 전혀 사용될 예정이 없다면 해당 전자제품을 교체한다.

답

def _1700() :
  ans = 0

  N, K = map(int, input().split())
  elecs = list(map(int, input().split()))
  
  tabs = []
  for index, elec in enumerate(elecs) :
    # 이미 멀티탭에 존재하는 경우
    if elec in tabs :
      continue

    # 교체해야 하는 경우
    if len(tabs) == N :
      # 가장 멀리 스케쥴되어있는 전자기기를 고른다.
      # 단, 다시는 스케쥴되어있지 않은 경우에는 해당 전자제품을 교체한다.
      ans += 1

      farthestElecIndexInTab = -1
      deleteElec = -1
      for tab in tabs :
        # get schedule
        if tab in elecs[index+1:] :
          elecIndex = elecs[index+1:].index(tab)
        else :
          elecIndex = -1
        if elecIndex == -1 :
          deleteElec = tab
          break
        # find the farest schedule
        if elecIndex > farthestElecIndexInTab :
          farthestElecIndexInTab = elecIndex
          deleteElec = tab

      tabs.remove(deleteElec)

    tabs.append(elec)

  return ans


print(_1700())