문제
01. 개요
멀티탭 스케줄링 은 멀티탭에 꽂혀 있는 전자기기를 최소 횟수로 교체하는 방법을 찾는 문제이다.
전자기기 사용 순서와 멀티 탭에 몇 개의 전자기기를 꽂을 수 있는지에 대한 정보를 준다.
02. 문제 접근 방법
1 ) 내가 범한 오류
a ) 첫 번째, 제일 많이 쓰는거 계속 꽂아놓기
앞으로 사용할 횟수가 많이 남은 기기를 계속 꽂아 놓으면 된다고 생각했다.
문제를 보자마자 페이지 교체 알고리즘 이 생각났고, 파일 데이터를 읽을 때 자주 쓰는 것들은 메모리에 올려놓고 사용한 경험이 있기 때문에 단순하게 생각했던 것 같다.
첫 번째 오류 : 최소 힙에 앞으로 남은 사용 횟수를 넣어놓고 사용 횟수가 적게 남은 것 뽑기
반례
2 6
1 2 3 1 2 3왜 오류일까?
남은 횟수만 고려하게 되면, 각 전자기기가 사용될 횟수가 동일하게 남았을 때, 남은 것들 중 아무거나 하나를 빼게 된다.
예를 들어서1 2 / 3 2 / 3 1 / 3 2 이렇게 탭에 꽂히게 되므로 세 번의 교체가 필요하다.
하지만, 1 2/ 1 3/ 2 3 순으로 탭에 꽂으면 두 번의 교체만 하면 된다.
멀티탭에 전자기기를 꼽을 때, 다음 index를 이용해 가장 나중에 쓰일 전자기기를 먼저 뽑자!
b ) 두 번째, 이미 꽂혀있는 전자기기를 사용할 때 index 문제
이미 꽂혀있는 전자기기를 다시 사용할 때가 있다.
Boolean 배열을 이용하여 이미 꽂힌 전자기기를 사용할 때는 그냥 다음 전자기기로 넘어가는 방식을 사용했다.
그런데, 전자기기를 사용할 때 다음 번 index 를 저장해주어야 하는데, 이미 꽂힌 경우 continue 로 넘겨주어 오류가 발생했다.
2 ) 조금 더 효율적인 방법
멀티탭에 꽂을 수 있는 전자기기의 수는 N개로 한정되어 있다.
뒤에 사용할 전자기기 중에서 현재 꽂혀 있는 전자기기를
사용 예정리스트에 넣어둔다.
사용 예정리스트의 길이가 N이 되면 가장 뒤에 다시 사용될 전자기기를 뽑는다.사용 예정리스트의 길이가 N보다 작다면 이후에 다시 사용되지 않을 전자기기를 뽑는다.Reference
for elec_idx in range(K):
# 멀티탭이 꽉차있고 현재 사용하려는 전자기기를 새로 꼽아야 하는 경우
if len(in_use) == N and elec_usage[elec_idx] not in in_use:
will_use = set()
for future_idx in range(i+1,K):
# 다음에 사용될 전자기기가 사용 중이라면 제거 대상이 된다.
# 가장 마지막에 사용될 전자기기가 최종 제거 대상이다.
if elec_usage[future_idx] in in_use :
target = elec_usage[future_idx]
will_use.add(elec_usage[future_idx])
# 꽂혀있는 N개가 모두 이후 사용 예정이라면 더 안봐도 된다.
if len(will_use) == N :
break
# 이후 N개가 모두 사용 대상이라면 가장 나중에 사용될 전자기기를 제거
if len(will_use) == N:
in_use.remove(target)
else:
# 사용되지 않을 전자기기를 뽑는다.
for target in in_use - will_use:
in_use.remove(target)
# 하나만 뽑을 수 있으므로 break
break
cnt += 1
in_use.add(elec_usage[elec_idx])
print(cnt)상기 코드처럼 구현하는 것 말고도 멀티탭에 꽂힌 전자기기의 다음 사용 차례 (다음 번 등장할 index) 가 가장 나중인 것을 구해서 교체하는 방식으로도 구현 할 수 있다.
03. 결론
결국, 멀티탭이 꽉 차 있을 때 가장 오랫동안 사용되지 않는 걸 먼저 빼면 최소 횟수로 뺄 수 있다.
그럼, 이제 페이지 교체 알고리즘을 알아보자 !
