문제
풀이한 문제는 백준 1700 멀티탭 스케쥴링입니다.
페이징 교체 알고리즘에 대해 들어보셨나요? 운영체제 과목에서 배우는 알고리즘 중 하나인데요. 해당 알고리즘을 차용해서 만든 문제라고 생각됩니다. 안배워보신 분이라면, 페이지 교체 알고리즘에 대해 설명한 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())