[백준] 1700번 : 멀티탭 스케줄링 (python 파이썬) + 벨라디의 변이

https://www.acmicpc.net/problem/1700

 

 

 

 

n, k = map(int, input().split(" "))
l = list(map(int, input().split(" ")))
c = [0 for _ in range(n)]  # 플러그

# 비어있는 플러그가 있으면 인덱스 반환
def find_blank(c):
    for i in range(len(c)):
        if c[i] == 0:
            return i
    return -1

# c 에서 i의 인덱스 반환
def getIndex(c, i):
    for idx in range(len(c)):
        if c[idx] == i:
            return idx
    return -1

# Optimal Page Replacement Algorithm을 기반으로 가장 나중에 사용될 플러그의 인덱스 반환
def getBest(c, i):
    future_use = [-1 for _ in range(n)]  # 각 콘센트가 다음에 사용될 인덱스를 저장
    for idx in range(len(c)):
        for j in range(i, len(l)):
            if c[idx] == l[j]:
                future_use[idx] = j
                break
    
    # 가장 나중에 사용될 플러그를 찾음
    if -1 in future_use:
        return future_use.index(-1)
    return future_use.index(max(future_use))

count = 0
for i in range(k):
    if l[i] in c:  # 이미 꽂혀있으면 넘어가기
        continue
    blank_id = find_blank(c)
    if blank_id != -1:  # 비어있으면
        c[blank_id] = l[i]  # 빈 곳에 꽂기
    else:  # 모든 콘센트가 사용 중이면
        best_idx = getBest(c, i)
        c[best_idx] = l[i]  # 해당 인덱스의 요소를 바꿔야 한다.
        count += 1
print(count)

 

 

이 문제는 골드 1 문제로 나에게는 좀 어려운 문제였다.

 

한동안 이 문제를 접근했다 포기하는 과정을 계속 반복하다, 최근 운영체제 프로그램에서 

얻은 알고리즘에서 해답을 얻었다.

 

운영체제에서 벨라디의 변이 (Belady's anomaly)를 아는가?

 

운영체제에서 프로세스는 메모리 위에 올라가야 실행할 수 있다.

 

하지만 프로세스가 무거우면, 전체를 다 올릴 수 없다.

 

따라서 프로그램의 일부만을 메모리에 올릴 수 있다!

이러한 방식을 사용하게 되면, 실제 물리 메모리는 크지 않아도, 엄청 큰 논리적인 메모리를 가지게 된다.

실제 실행 부분만 메모리에 올리고, 나머지 부분은 보조 기억 장치에 넣고, 계속 스왑하는 것이다.

이러한 현상을 가상 메모리 (virtual memory)라고 한다.

 

이렇게 쪼개진 프레임을 메모리에 올려놓고, 만약 메모리에 없는 프레임이 필요하면 보조 기억 장치에서 꺼내서 

메모리에서 프레임을 바꾸면서 실행한다.

 

하지만 메모리에 올려놓을 수 있는 프레임이 많다고 해도, 메모리에 프레임이 없는 경우가 많아질 수 있다.

벨라디의 변이

이러한 현상을 벨라디의 변이 라고 한다.

 

이 벨라디의 변이가 발생하지 않는 알고리즘을 OPT라고 한다.

위 설명을 보니까 뭔가 문제와 유사한 상황이지 않는가..?

 

위의 메모리를 콘센트라고 보고, reference string 이 사용되는 순서라고 보자!

 

완전 똑같은 문제가 아닌가?

 

 

 

벨라디의 문제를 해결하는 방법 중 최적 페이지 교체 (Optiaml page-replacement algorithm)을 사용하면 

이 문제를 해결할 수 있다.

 

최적 페이지 교체는 간단히 말하면

가장 오랜 기간 동안 사용하지 않은 페이지를 교체하는 것이다.

즉, 콘센트에 꽃혀있는 것 중에서, 가장 나중에 쓰이는 가전제품을 먼저 빼는 것이다.

 

 

 

만약 콘센트가 [a,b,c] 형식이고, d라는 세로운 가전제품을 써야 하는 상황이면

a,b,c 중, 남은 순서 중에서 가장 나중에 쓰이는 것과 d를 바꾸면 된다.

 

가장 나중에 쓰이는 것을 골라야지 그 사이에 쓰이는 것들을 사용할 수 있다는 것을 

직관적으로 생각 할 수 있을 것이다.

 

 

위 정답 코드 중 getBest가 해당 연산을 구현한 부분이다.