이번 예선 통틀어 최악의 정답율을 기록한 문제입니다(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) 기법등 여러가지 방법을 사용하고 있습니다.
admin
이번 예선 통틀어 최악의 정답율을 기록한 문제입니다(8.68%). 서울대회의 특성상 보통 A,B 번이 쉽게 출제되어 다들
풀고 시작하는것이 관례였는데, 이번 대회의 경우에는 B번이 예년에 비해 조금 난이도가 있던 편이어서 인지, 속된말로 '낚이는'
팀들이 속출 했습니다.
그런데, 이 문제는 사실 운영체제 과목을 들은 적이 있는 분은'아하' 하셨을 문제 입니다. 이 문제는 운영체제에서 다루는 '페이지 교체 알고리즘' 의 전형적인 예이기 때문입니다. (위키피디아 링크)
실제로 운영체제에서는 미래의 메모리 사용 내역을 알 수 없기 때문에, 이 문제는 가상의 최적 페이지 교체 알고리즘을 구현하는 것을 골자로 하고 있습니다. 이와 같은 최적 페이지 교체 알고리즘의 구조는 다음과 같습니다.
증명은 일단 생략합니다. ^^;; 이를 소스 코드로 옮기면 다음과 같습니다.
[spoiler="더 보기..."]int main() {
int T;
int n, k;
cin >> n >> k;
while(T--) {
set
vector
for(int i=0;i
int ret = 0;
for(int i=0;i
if((int)cache.size()>n) {
++ret;
vector
set
for(it=cache.begin();it!=cache.end();++it) {
if(*it==order[0]) continue;
vector
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) 기법등 여러가지 방법을 사용하고 있습니다.
16년 전