테이프 스토리지 — 접근 시간을 최소로 만드는 greedy 배치

크기도 다르고 얼마나 자주 쓰는지도 다른 데이터들이 있다. 이것들을 하나의 테이프에 차례로 적어 둘 때, 어떤 순서로 놓아야 읽는 데 걸리는 시간이 가장 짧을까?

이 포스트에서 다루는 내용

테이프 스토리지 문제의 정의: 길이 $L_i$ 와 빈도 $F_i$ 를 가진 데이터의 배치
접근 시간 모델: 읽을 때마다 시작점으로 돌아오는 순차 접근
Greedy 전략: 빈도 대비 길이의 비율 $F_i / L_i$ 가 큰 데이터부터 앞에 놓기
정확성 증명: 이웃한 두 데이터를 맞바꾸는 교환 논증(exchange argument)

문제 정의

$N$ 개의 데이터 $D_1, \cdots, D_N$ 이 있다. 각 데이터는 크기가 제각각이며, 두 값으로 표현된다.

D_i = (L_i, F_i)

$L_i$ : 데이터의 크기 — 테이프 위에서 차지하는 길이.
$F_i$ : 사용 빈도 — 이 데이터를 읽는 횟수.

이 데이터들을 하나의 테이프 위에 일렬로 배치한다. 목표는 데이터를 읽는 데 드는 총 접근 시간을 최소로 만드는 배치 순서를 찾는 것이다.

읽기·쓰기 모델

비용을 따지려면 먼저 테이프를 어떻게 쓰고 읽는지 정해야 한다.

쓰기: 모든 데이터를 처음에 한 번에 적는다. 한 번 배치한 순서는 바뀌지 않는다.
읽기: 데이터를 여러 번 읽는다. 단, 한 번 읽으면 테이프의 시작 지점으로 되돌아온다.

이 모델에서 어떤 데이터를 읽으려면, 시작점부터 그 데이터까지 앞에 놓인 데이터를 모두 지나가야 한다. 즉 배치 순서대로 $1, 2, \cdots, N$ 번이라 할 때, $i$ 번째 데이터를 한 번 읽는 비용은 그 앞부터 자기 자신까지의 길이 합이다.

L_1 + L_2 + \cdots + L_i

테이프 접근 모델 — i번째 데이터를 읽으려면 앞 데이터를 모두 지나야 하고, 읽은 뒤 시작점으로 돌아온다. 총 접근 시간은 Σ Fᵢ(L₁+⋯+Lᵢ)

이 데이터를 $F_i$ 번 읽으므로, $i$ 번째 데이터가 전체 접근 시간에 기여하는 양은 $F_i \cdot (L_1 + \cdots + L_i)$ 이다. 모든 데이터에 대해 합하면 우리가 최소화하려는 총 접근 시간 $P$ 가 된다.

P = \sum_{i=1}^{N} F_i \,(L_1 + L_2 + \cdots + L_i)

이 식에서 한 가지가 분명해진다. 앞쪽에 놓인 데이터의 길이는 그 뒤의 모든 데이터를 읽을 때마다 반복해서 더해진다. 앞 자리를 누구에게 줄지가 비용을 좌우한다.

직관: 무엇을 앞에 둘까

위 식을 보면 두 가지 욕심이 생긴다.

자주 쓰는 데이터( $F_i$ 큰 것)는 앞에 두고 싶다. 그래야 그 큰 빈도가 작은 누적 길이와 곱해진다.
긴 데이터( $L_i$ 큰 것)는 뒤에 두고 싶다. 앞에 있으면 그 긴 길이가 뒤따르는 모든 데이터의 접근 비용에 매번 더해지기 때문이다.

두 욕심을 하나로 합치는 기준이 바로 빈도 대비 길이의 비율 $F_i / L_i$ 다. 자주 쓰일수록(분자가 클수록), 짧을수록(분모가 작을수록) 비율이 커진다. 작은 예로 확인해 보자.

배치 직관 — A=(길이4,빈도1), B=(길이1,빈도4)일 때 A→B는 비용 24, B→A는 비용 9. F/L이 큰 B를 앞에 두는 것이 유리하다

데이터 $A = (4, 1)$ 과 $B = (1, 4)$ 두 개만 놓자.

$A \to B$ 순서: $1 \cdot 4 + 4 \cdot (4 + 1) = 4 + 20 = 24$ .
$B \to A$ 순서: $4 \cdot 1 + 1 \cdot (1 + 4) = 4 + 5 = 9$ .

$B$ 의 비율은 $F/L = 4$ , $A$ 의 비율은 $0.25$ 다. 비율이 큰 $B$ 를 앞에 둔 쪽이 비용 9로 훨씬 적다. 그렇다면 $F_i / L_i$ 가 큰 순서로 내림차순 정렬해 앞에서부터 배치하면 될 것 같다.

직관은 그럴듯하다. 하지만 그리디 알고리즘에서 보았듯, 매 단계의 국소 최적이 늘 전역 최적이 되지는 않는다. 이 비율 기준이 정말 최적인지 증명이 필요하다.

정확성 증명

증명의 도구는 스케줄링 문제에서도 썼던 교환 논증(exchange argument) 이다. 여기서는 그중에서도 이웃한 두 데이터를 맞바꾸는 형태를 쓴다.

전략은 귀류법이다. 최적이라고 주장하는 배치가 $F_i / L_i$ 내림차순이 아니라고 가정하면, 그 배치에서 언제나 더 나은 배치를 직접 만들어 낼 수 있음을 보인다. 더 나은 배치가 존재한다는 것은 곧 원래 배치가 최적이 아니었다는 뜻이므로, 결국 최적 배치는 내림차순일 수밖에 없다. 정리하면 다음을 증명한다.

어떤 배치가 $F_i / L_i$ 내림차순이 아니라면, 그 배치는 최적이 아니다.

왜 이웃한 두 개만 보면 되나

배치가 내림차순이 아니라는 것은, 순서대로 비율을 훑었을 때 값이 한 번이라도 올라가는 지점이 있다는 뜻이다. 이 사실은 곧 이웃한 두 데이터에서 역전이 일어남을 보장한다.

거꾸로 생각해 보자. 만약 모든 이웃 쌍 $(i, i+1)$ 에서 $F_i / L_i \ge F_{i+1} / L_{i+1}$ 이 성립한다면, 비율은 앞에서 뒤로 가며 한 번도 올라가지 않으므로 전체가 이미 내림차순이다. 이는 가정에 어긋난다. 따라서 내림차순이 아니라면, 적어도 한 곳에서

\frac{F_i}{L_i} < \frac{F_{i+1}}{L_{i+1}}

인 이웃한 $i, i+1$ 쌍이 반드시 존재한다. 이제 이 한 쌍만 맞바꿔 비용이 줄어듦을 보이면, “더 나은 배치”를 만든 셈이 된다.

맞바꾸기 전후의 비용

찾은 이웃 쌍을 $i, i+1$ 번째 자리라 하자. 그 앞에 놓인 데이터들의 길이 합을 $S = L_1 + \cdots + L_{i-1}$ 로 둔다.

맞바꾸기 전. $i$ 번째 데이터를 읽으려면 앞의 $S$ 와 자기 자신 $L_i$ 를 지나야 하므로 누적 길이는 $S + L_i$ , 이어지는 $i+1$ 번째는 거기에 $L_{i+1}$ 이 더해져 $S + L_i + L_{i+1}$ 이다. 두 데이터가 총 접근 시간 $P$ 에 기여하는 몫은 다음과 같다.

F_i\,(S + L_i) \;+\; F_{i+1}\,(S + L_i + L_{i+1})

맞바꾼 후. 이번엔 $i+1$ 번째가 앞으로 와 누적 길이 $S + L_{i+1}$ , $i$ 번째가 뒤로 가 $S + L_{i+1} + L_i$ 가 된다. 바뀐 배치의 같은 두 자리가 기여하는 몫을 $P'$ 의 해당 항이라 하면,

F_{i+1}\,(S + L_{i+1}) \;+\; F_i\,(S + L_{i+1} + L_i)

왜 나머지 데이터는 그대로인가. 두 자리를 맞바꿔도 다른 데이터의 접근 비용은 전혀 변하지 않는다.

$i$ 앞(위치 $< i$ )의 데이터들 — 누적 길이에 $L_i$ 도 $L_{i+1}$ 도 들어가지 않는다. 맞바꾼 두 데이터보다 앞에 있으니 아무 영향이 없다.
$i+1$ 뒤(위치 $> i+1$ )의 데이터들 — 누적 길이에 $L_i$ 와 $L_{i+1}$ 이 둘 다 포함된다. 그런데 둘의 순서만 바뀌었을 뿐 합 $L_i + L_{i+1}$ 은 그대로이므로, 누적 길이도 그대로다.

결국 달라지는 것은 위에 적은 두 자리의 기여분뿐이다.

교환 논증 — 공통 구간 S는 그대로 두고 i와 i+1의 자리만 맞바꾼다. P−P′ = Fᵢ₊₁Lᵢ − FᵢLᵢ₊₁ = LᵢLᵢ₊₁(Fᵢ₊₁/Lᵢ₊₁ − Fᵢ/Lᵢ)

두 비용의 차이

이제 $P - P'$ 을 구하면, 방금 본 대로 두 자리의 기여분만 남는다.

P - P' = \big[F_i(S + L_i) + F_{i+1}(S + L_i + L_{i+1})\big] - \big[F_{i+1}(S + L_{i+1}) + F_i(S + L_{i+1} + L_i)\big]

같은 빈도끼리 묶으면 어떤 항이 사라지는지 한눈에 보인다.

\begin{aligned} P - P' &= F_i\big[(S + L_i) - (S + L_{i+1} + L_i)\big] \\ &\quad + F_{i+1}\big[(S + L_i + L_{i+1}) - (S + L_{i+1})\big] \end{aligned}

각 대괄호 안에서 $S$ 와 겹치는 길이가 모두 지워지고, $F_i$ 쪽은 $-L_{i+1}$ , $F_{i+1}$ 쪽은 $+L_i$ 만 남는다.

P - P' = -F_i L_{i+1} + F_{i+1} L_i = F_{i+1} L_i - F_i L_{i+1}

여기서 $L_i L_{i+1}$ 로 묶으면, 우리가 세운 비율의 모습이 그대로 드러난다.

P - P' = L_i L_{i+1}\left(\frac{F_{i+1}}{L_{i+1}} - \frac{F_i}{L_i}\right)

가정에서 $\dfrac{F_{i+1}}{L_{i+1}} > \dfrac{F_i}{L_i}$ 였고 길이 $L_i, L_{i+1}$ 은 양수이므로, 괄호 안과 앞의 곱이 모두 양수다. 따라서

P - P' > 0 \quad\Longrightarrow\quad P > P'

즉 두 데이터를 맞바꾼 배치 $P'$ 의 총 접근 시간이 더 작다. 비율이 더 큰 $i+1$ 을 앞으로 당기면 비용이 줄어든다는 뜻이다.

이로써 ” $F_i / L_i$ 내림차순이 아닌 배치에는 항상 더 나은 배치가 존재한다”가 증명됐다. 대우를 취하면, 최적 배치는 반드시 $F_i / L_i$ 내림차순이다.

같은 식은 한 가지를 더 알려 준다. 두 비율이 같을 때( $F_i / L_i = F_{i+1} / L_{i+1}$ )는 $P - P' = 0$ 이라 맞바꿔도 비용이 그대로다. 즉 비율이 같은 데이터끼리는 앞뒤 순서를 자유롭게 바꿔도 최적성이 유지된다.

증명의 뼈대

“내림차순이 아니면 이웃한 역순 쌍이 존재한다”에서 출발해, 그 쌍을 맞바꾸면 비용이 줄어든다는 것을 보였다. 차이가 $L_i L_{i+1}\left(\frac{F_{i+1}}{L_{i+1}} - \frac{F_i}{L_i}\right)$ 라는 깔끔한 식으로 떨어지는 덕분에, 비율의 대소만으로 어느 쪽이 이득인지 즉시 판단된다.

시간 복잡도

증명이 알려 준 답은 단순하다. 모든 데이터를 $F_i / L_i$ 기준 내림차순으로 정렬하면 끝이다.

최적 배치 — F/L 내림차순으로 정렬한 테이프. 정렬 한 번이면 끝나므로 O(N log N)

배치 자체는 정렬 결과를 그대로 따르면 되므로, 전체 비용은 사실상 정렬 비용이 지배한다.

정렬: 비교 기반 정렬로 $O(N \log N)$ .

따라서 테이프 스토리지 문제는 $O(N \log N)$ 에 해결된다.

핵심 정리

테이프 스토리지는 길이 $L_i$ 와 빈도 $F_i$ 를 가진 데이터들을 하나의 테이프에 배치해, 읽기 위해 매번 시작점부터 훑는 총 접근 시간 $\sum F_i (L_1 + \cdots + L_i)$ 을 최소로 만드는 문제다.
앞 데이터의 길이는 뒤 데이터를 읽을 때마다 반복해서 더해진다. 그래서 자주 쓰고(F 큰) 짧은(L 작은) 데이터를 앞에 두는 것이 이득이다.
Greedy 전략은 두 욕심을 하나로 합친 비율 $F_i / L_i$ 가 큰 순서로 내림차순 배치하는 것이다.
최적성은 이웃 교환 논증으로 증명한다. 비율이 역순인 이웃 쌍을 맞바꾸면 비용이 $L_i L_{i+1}\left(\frac{F_{i+1}}{L_{i+1}} - \frac{F_i}{L_i}\right)$ 만큼 줄어들므로, 최적 배치는 반드시 비율 내림차순이다.
구현은 정렬 한 번이면 충분해 전체 $O(N \log N)$ 이다.

그리디 증명 도구로서의 교환 논증

데드라인 스케줄링과 구간 스케줄링에서는 "부분 답에 일치하는 최적해가 늘 존재한다"는 불변식을 단계마다 교환으로 유지했다. 테이프 스토리지에서는 더 간결하게, "정렬 기준을 어긴 이웃 쌍을 맞바꾸면 항상 나아진다"는 이웃 교환(adjacent swap)만으로 최적성이 증명된다. 같은 교환 논증이라도 문제 구조에 따라 모습이 달라진다.