[알고리즘] 6. Tape Storage

1. 문제 정의

N개의 Data가 있다. 각 Data는 $D_i=(L_i, F_i)$ 으로 구성되어 있고, $L$은 Length of Data, $F$는 Frequency of Usage를 의미한다. 테이프에는 각 Data들을 단 한번만 쓸 수 있고, 읽는 것은 무제한으로 가능하다. 하지만 모든 읽기 작업은 항상 테이프의 첫부분부터 읽는다. 이때 가장 효율적으로 데이터를 배치하는 방법은 무엇일까?

직관적으로 $L_i$가 짧을수록 앞에 배치하고, $F_i$가 클수록 앞에 배치하는 것이 좋다고 생각할 수 있다. 따라서 $F_i/L_i$의 값이 큰 것부터 내림차순으로 정렬하여 테이프에 쓰면 된다. (Greedy 알고리즘)

 

2. 정당성 증명

증명에 앞서, $C_i(cost) = f_i\sum_{k=1}^n l_k$ 라 하고, 모든 데이터의 cost 총 합이 작을수록 효율적이라고 가정하자.

 $F_i/L_i$의 값이 큰 것부터 내림차순으로 정렬하여 테이프에 써야 Cost가 최소임을 증명하자. (귀류법)

$F_i/L_i < F_{i+1}/L_{i+1}$ 이라고 가정하자. 먼저 데이터가 $1,\ 2,\ ...\ ,i\ ,i+1,\ ...$ 순서로 쓰여져있을 때의 cost를 $Cost_1$ 이라 하자. 그리고 $i$와 $i+1$번째 데이터의 순서를 바꿔서  $1,\ 2,\ ...\ ,i+1\ ,i,\ ...$ 순서로 쓰여져있을 때의 cost를 $Cost_2$ 라고 하자.
\[ Cost_1 =  f_1l_1 + \cdots + f_i(l_1+\cdots+l_i) + f_{i+1}(l_1 + \cdots + l_i + l_{i+1} + \cdots \]
\[ Cost_2 =  f_1l_1 + \cdots + f_{i+1}(l_1+\cdots+l_{i-1}+l_{i+1}) + f_{i}(l_1 + \cdots + l_{i-1} + l_{i+1} + l_i) + \cdots \]
\[ Cost_2 - Cost_1 = f_il_{i+1} - f_{i+1}l_i = l_il_{i+1}\left( \frac{f_i}{l_i} - \frac{f_{i+1}}{l_{i+1}} \right) < 0 \]
\[ \therefore Cost_2 < Cost_1 \]
Cost가 더 작아지는 솔루션 $Cost_2$이 존재하게 되므로, 가정이 모순이다. 따라서 증명 끝!