1. Problem Definition N개의 데이터 아이템이 있다. 각 데이터 Di는 (Li ,Fi)로 이루어져 있다. Li은 데이터의 사이즈 , Fi은 사용 빈도수이다. 테이프에는 데이터를 한번만 쓸 수 있고, 읽는것은 무제한이다. 데이터를 읽으러 가는 모든 때의 시작점은 맨 처음이다. (데이터를 읽고나서 매번 맨 앞으로 돌아간다) 직관적으로 보면 크키가 클수록 뒤에 있고 자주 쓰는 것을 앞에 배치하면 좋겠다는 생각이든다. 하지만 자주 쓰는데 크기가 너무 크다면..? 이라는 애매한 상황이 생긴다, 2. Solution F/L 순서대로 저장하면 된다. (greedy) Proof 기대값은 빈도수 * 맨 앞에서 해당 데이터 까지의 L 라고 정의할 수 있다. 귀류법으로 증명을 해보겠다. Assume : Fi..
