[ 알고리즘 ] Tape Storage

1. Problem Definition

• N개의 데이터 아이템이 있다.
• 각 데이터 Di는 (Li ,Fi)로 이루어져 있다. Li은 데이터의 사이즈 , Fi은 사용 빈도수이다.
• 테이프에는 데이터를 한번만 쓸 수 있고, 읽는것은 무제한이다.
• 데이터를 읽으러 가는 모든 때의 시작점은 맨 처음이다. (데이터를 읽고나서 매번 맨 앞으로 돌아간다)

직관적으로 보면 크키가 클수록 뒤에 있고 자주 쓰는 것을 앞에 배치하면 좋겠다는 생각이든다. 

 

하지만 자주 쓰는데 크기가 너무 크다면..? 이라는 애매한 상황이 생긴다,

 

2. Solution

F/L 순서대로 저장하면 된다. (greedy)

Proof

기대값은 빈도수 * 맨 앞에서 해당 데이터 까지의 L 라고 정의할 수 있다.

 

귀류법으로 증명을 해보겠다.

 

Assume : Fi / Li < Fi+1 / Li+1

데이터가 1,2,...i, i+1 의 순서로 저장됐을때를 Case1이라고 하고

1,2,...i+1 , i 의 순서로 데이터가 저장됐을 떄는 Case2 라고하자.

 

Proof

 

Case1이 더 저렴하므로 가정은 모순된다.