백준 멀티탭 스케줄링

‣

문제 요약

• 멀티탭에는 N개의 구멍이 있음

• K개의 전기용품을 주어진 순서대로 사용해야 함

• 멀티탭이 꽉 찼을 때 새로운 전기용품을 사용하려면 기존에 꽂힌 플러그 중 하나를 뽑아야 함

• 플러그를 뽑는 횟수를 최소화하는 것이 목표

접근법

문제 해결을 위해 그리디 접근법을 선택

멀티탭이 꽉 찬 상황에서 플러그를 뽑을 때,

• 어떤 플러그를 뽑으면 앞으로 플러그를 뽑는 횟수를 최소화할 수 있을까?

이 질문에 대한 경우의 수는

• 앞으로 다시 사용되지 않을 플러그가 있다면 그것을 먼저 뽑자

• 앞으로 가장 나중에 사용될 플러그를 뽑자

→ 두번째 걸 생각하는데 좀 더 걸림.

앞으로 가장 나중에 사용될 플러그를 뽑아야 하는 이유

1. 곧 다시 사용할 플러그를 뽑으면 바로 다시 그 플러그를 꽂아야 하므로 추가적인 뽑기 횟수가 발생

2. 여러 플러그 중 가장 나중에 사용될 플러그를 뽑으면 그 시점까지 다른 플러그들을 뽑지 않아도 되므로 뽑는 횟수를 줄일 수 있음

→ 다른 플러그들은 더 빨리 다시 사용되어야 하므로 미리 뽑으면 안 됨.

벨레이디 알고리즘과 유사

• 벨레이디가 제안한 페이지 교체 알고리즘과 비슷함

페이지 교체 알고리즘

페이징 기법으로 메모리를 관리하는 운영체제에서 필요한 페이지가 주기억장치에 적재되지 않았을 시 어떤 페이지 프레임을 선택하여 교체할 것인지 결정하는 방법

 

벨레이디가 제안한 최적 교체 방식인 앞으로 가장 오랫동안 사용하지 않을 페이지를 교체하는 기법 과 비슷하다.

 

참고 참고

코드