[editorial] 2007년 서울 지역대회 인터넷 예선 B번 Multitap Scheduling

  • admin
    admin

    이번 예선 통틀어 최악의 정답율을 기록한 문제입니다(8.68%). 서울대회의 특성상 보통 A,B 번이 쉽게 출제되어 다들
    풀고 시작하는것이 관례였는데, 이번 대회의 경우에는 B번이 예년에 비해 조금 난이도가 있던 편이어서 인지, 속된말로 '낚이는'
    팀들이 속출 했습니다.
    그런데, 이 문제는 사실 운영체제 과목을 들은 적이 있는 분은'아하' 하셨을 문제 입니다. 이 문제는 운영체제에서 다루는 '페이지 교체 알고리즘' 의 전형적인 예이기 때문입니다. (위키피디아 링크)
    실제로 운영체제에서는 미래의 메모리 사용 내역을 알 수 없기 때문에, 이 문제는 가상의 최적 페이지 교체 알고리즘을 구현하는 것을 골자로 하고 있습니다. 이와 같은 최적 페이지 교체 알고리즘의 구조는 다음과 같습니다.

  • 우선 뒤에 사용될 것 중에 더이상 사용 되지 않을 경우에는 그냥 뽑는게 낫습니다.
  • 전부 사용 될 경우엔 출현 순서가 가장 늦게 나오는 것을 뽑습니다.

  • 증명은 일단 생략합니다. ^^;; 이를 소스 코드로 옮기면 다음과 같습니다.
    [spoiler="더 보기..."]int main() {
    int T;
    int n, k;
    cin >> n >> k;
    while(T--) {
    set cache;
    vector order(k);
    for(int i=0;i> order[i];
    int ret = 0;
    for(int i=0;i cache.insert(order[0]);
    if((int)cache.size()>n) {
    ++ret;
    vector::iterator p = order.begin();
    set::iterator tg, it;
    for(it=cache.begin();it!=cache.end();++it) {
    if(*it==order[0]) continue;
    vector::iterator j = find(order.begin(),order.end(),*it);
    if(p<j) { tg = it; p = j; }
    }
    cache.erase(tg);
    }
    order.erase(order.begin());
    }
    cout << ret << endl;
    }
    }[/spoiler]
    미래를 알고 있을 경우 이 알고리즘으로 최적의 페이징을 구현할 수 있다는 것이 증명되어 있습니다. 물론 실제로 미래에 사용자가 필요로 할 메모리를 파악하기란 불가능하기 때문에, 실제의 경우 LRU(Least Recently Used)
    기법, FIFO(First-in-first-out) 기법등 여러가지 방법을 사용하고 있습니다.

    • 정현환(a.k.a LIBe), 구종만, algospot.com 운영진
      [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    17년 전
0개의 댓글이 있습니다.
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.