[스키 대여 문제 / Ski Rental Problem] 문제 정의 & Break-Even Algorithm

이번 포스트에서는 기초적인 온라인 문제 중 하나인 스키 대여 문제(ski rental problem)를 다루어 보도록 하겠습니다. 온라인 문제 및 온라인 알고리즘이 무엇인지는 이전 글을 참조해 주시기 바랍니다. 아래의 내용은 이 글을 제대로 숙지하고 있다는 전제 하에 작성되었습니다.

2020/03/14 - [온라인 알고리즘] - 온라인 알고리즘

온라인 알고리즘

이미 위 글에서 스키 대여 문제가 무엇인지 간략하게 소개되어 있습니다만 이번에는 이 문제가 정확히 어떤 것인지 알아보고 이를 해결하는 간단한 deterministic 2-competitive algorithm을 소개하도록 하겠습니다. 이 알고리즘은 break-even algorithm으로 불리기도 한답니다. 마지막으로 어떤 deterministic algorithm도 2보다 좋은 경쟁비(competitive ratio)를 가질 수 없다는 것을 보이도록 하겠습니다.

문제 정의

Photo by Emma Paillex on Unsplash

여러분은 스키장에 왔습니다. 스키 타는 것을 너무나 사랑하는 여러분은 이번 겨울 스키장이 닫을 때까지 매일 타려고 합니다. 모종의 사유로 이번 겨울이 아니면 다시는 스키를 타지 못하게 되었거든요. 스키를 타기 위해서는 두 가지 방법이 존재합니다. 하나는 스키 장비를 대여하는 것이고 다른 하나는 모든 장비를 구매하는 것이죠. 스키 장비를 하루 대여하는 데 들어가는 비용은 \(\$1\)입니다.(단위를 간소화하기 위하여 달러로 표기하였습니다.) 반면 장비를 모두 사기 위해서는 \(\$B\)의 금액이 필요합니다. 대신 스키 장비를 구매한 후에는 당연히 대여할 필요가 없습니다. 여러분은 스키장이 문을 닫을 때까지 최소의 비용으로 스키를 타고자 합니다.

 

만약 스키장이 언제 닫는지 미리 알 수 있다면, 이 문제는 쉽게 해결할 수 있습니다. 만약 스키장이 \(B\) 번째 날 이전에 닫는다면 스키를 매일 대여하는 것이 이득이고, 반대로 스키장이 \(B\) 번째 날 이후에 닫는다면 스키를 구매하는 것이 이득입니다. 하지만 여러분도 아시다시피 당장 내일 일어날 일도 모르는 게 사람입니다. 안타깝지만, 여러분은 스키장이 언제 닫는지, 심지어는 스키장 관계자도 스키장을 언제 닫을지 모른다고 합니다. 이는 큰 문제죠. 스키를 계속 대여하기로 마음먹었는데 스키장이 닫지를 않아 매일 대여료가 쌓일 수도 있지만, 반대로 스키를 구매했는데 당장 다음날 스키장이 문을 닫을 수도 있기 때문입니다. 과연 여기서 여러분은 어떤 전략을 취해야 할까요?

간단한 deterministic 2-competitive algorithm

이번 절에서는 이 문제를 해결하는 간단한 deterministic 2-competitive algorithm을 소개하겠습니다. 좀 더 자세히 말하면, 임의의 \(t\)에 대해서, 만약 스키장이 \(t\) 번째 날까지 개장한다고 하였을 때, \(\mathsf{OPT}(t)\)를 필요한 최소 비용이라고 하면, \(2 \mathsf{OPT}(t)\)보다 크지 않은 비용으로 스키를 타는 전략을 출력하는 deterministic algorithm을 제시할 것입니다.

 

우선 이전 절에서 쉽게 알아낸 내용이 있습니다. 바로 스키장이 \(B\) 번째 날보다 일찍 폐장하면 매일 스키를 대여하는 것이 이득이고, 반대로 \(B\) 번째 날 이후에도 계속 열린다면 첫날에 스키를 구매하는 것이 이득이라는 점입니다. 이를 다시 쓰면, 다음과 같습니다.

\[\mathsf{OPT}(t) = \left\{ \begin{array}{ll} t, && \text{if } t < B, \\ B, && \text{otherwise.} \end{array} \right.\]

이를 잘 살펴보면 \(t < B\)일 때는 우리 알고리즘이 \(2t\)보다 작거나 같은 비용을 내는 전략을 출력해야 합니다. 그런데 만약 \(B\)가 \(t\)보다 엄청 크다면 알고리즘 입장에서 스키 장비를 구매하는 것은 멍청한 선택이 될 것입니다. 반대로 \(t \geq B\)일 때는 우리 알고리즘이 \(2B\)의 금액을 넘지 않는 전략을 주어야 합니다. 이 경우에는 아무래도 장비를 대여하는 것보다 구매를 하는 것이 좋은 선택일 것입니다. 즉, 처음에는 대여를 하다가 개장일이 길어진다 싶으면 적절한 때에 구매를 하는 방법이 합리적인 전략이 될 것입니다. 이 아이디어를 활용하면 다음과 같은 알고리즘을 얻을 수 있습니다.

알고리즘 1. A simple deterministic 2-competitive algorithm

---

초기 입력: 스키 장비 구매 비용 \(B\)

출력: 대여/구매 전략

 

1. 만약 \(t\) 번째 날에 스키장이 개장하면 다음을 수행한다.
   1. 만일 \(t < B\)이면 스키 장비를 대여한다.
   2. 만약 \(t = B\)이면 스키 장비를 구매한다. 그 이후는 구매한 스키 장비를 사용한다.

[증명] 만약 \(t < B\)이면 이 알고리즘은 정확히 \(t\)의 비용을 발생시킵니다. 이는 정확히 \(\mathsf{OPT}(t)\)와 일치하죠. 반대로 \(t \geq B\)라면 우리 알고리즘은 지금껏 지불한 대여 비용 \(B-1\)에 구매 비용 \(B\)를 합쳐서 총 \(2B - 1\)을 지출합니다. 이 경우, \(\mathsf{OPT}(t) = B\)이므로 2-competitive 함을 보일 수 있습니다. ■

 

하한(lower bound)

지금까지 스키 대여 문제를 해결하는 deterministic 2-competitive algorithm을 알아보았습니다. 당연히 컴퓨터과학을 공부하는 사람이라면 응당 이 질문을 하겠죠. 과연 더 좋은 경쟁비를 갖는 알고리즘을 얻을 수 있을까요? 바로 답을 드리자면 deterministic algorithm의 경우에는 불가능합니다.

정리 1. Lower bound on competitive ratios of deterministic algorithms

---

스키 대여 문제를 해결하는 어떤 deterministic algorithm도 2보다 좋은 경쟁비(competitive ratio)를 가질 수 없다.

이전 포스트에서 온라인 알고리즘의 competitiveness를 분석할 때는 불공평한 상대방을 상정하여 게임하는 것으로 생각할 수 있다고 말씀드렸습니다. 어떤 고정된 상수 \(c\)에 대해, 어떤 알고리즘이 최종적으로 \(\mathsf{ADV}\)의 값을 출력하는 임의의 상대방을 상대로 마지막에 \( \rho \mathsf{ADV} + c\)보다 작거나 같은 값을 갖는 solution을 출력한다면, 우리는 이 알고리즘이 \(\rho\)-competitive algorithm라는 것을 보일 수 있다고 하였습니다. 게다가 만약 알고리즘이 deterministic 하다면 적응형 상대방(adaptive adversary)를 상정하여도 경쟁비에는 영향을 주지 않는다는 사실도 지난번에 함께 보였습니다. 이 아이디어를 역으로 생각하면 원하는 결과를 이끌어 낼 수 있습니다.

 

[증명] 귀류법을 쓰겠습니다. 어떤 알고리즘이 임의의 상대방에 대하여 최종적으로 \( (2 - \epsilon) \mathsf{ADV} + c\)보다 작거나 같은 값을 갖는 solution을 출력한다고 가정하겠습니다.(단, \(\epsilon\)은 \(0 < \epsilon \leq 1\)인 상수, \(c\)는 음이 아닌 상수, \(\mathsf{ADV}\)는 상대방이 최종적으로 출력하는 값) 이 알고리즘이 마지막에 출력한 결과의 값을 \(\mathsf{ALG}\)라고 부르겠습니다.

 

이제 다음과 같은 적응형 상대방을 고려해 보죠. 먼저 스키 구매 비용인 \(B\)는 \( \frac{c + 1}{\epsilon} \)보다 큰 임의의 수로 하겠습니다. \(\epsilon > 0\)이기 때문에 그러한 숫자를 정할 수 있습니다. 이 적응형 상대방의 전략은 간단합니다. 알고리즘이 스키를 대여하면 그 다음날 스키장을 개장할 것이고, 만약 스키를 구매하면 그날로 스키장 문을 닫아버릴 것입니다.(나쁜 놈...)

 

알고리즘이 스키 장비를 구매할 때까지 이 상대방은 계속 스키장 문을 열기 때문에 우리는 알고리즘이 언젠간 스키 장비를 구매한다는 것을 알 수 있습니다. 그날을 \(t\) 번째 날이라고 하겠습니다. 그러면 알고리즘은 정확히 \[ \mathsf{ALG} = (t - 1) + B \]만큼의 비용을 지불할 것입니다. 반대로 상대방은 항상 최적의 값을 갖는 solution을 출력할 것이므로 \[ \mathsf{ADV} = \left\{ \begin{array}{ll} t, & \text{if } t \leq B, \\ B, & \text{otherwise,} \end{array} \right. \]가 됩니다.

 

먼저 \(t \leq B\)라고 가정해 봅시다. 알고리즘이 \(\mathsf{ALG} \leq (2 - \epsilon) \mathsf{ADV} + c\)를 만족하므로, 우리는 \[(t - 1) + B \leq (2 - \epsilon) t + c\]를 이끌어 낼 수 있습니다. 이 식을 정리하면, \[B \leq (1 - \epsilon) t + c + 1 \leq (1 - \epsilon) B + c + 1\]을 얻을 수 있으며, 이를 또 정리하면 \( B \leq \frac{c + 1}{\epsilon} \)임을 알 수 있습니다. 하지만 우리는 \(B\)를 \(\frac{c + 1}{\epsilon}\)보다 큰 숫자로 골랐기 때문에 모순이 됩니다.

 

이제는 반대로 \(t > B\)인 경우를 생각해 보도록 하겠습니다. 우리는 우선적으로 다음과 같은 식을 얻을 수 있습니다.  \[ \mathsf{ALG} = (t - 1) + B > 2B - 1 \] 여기에 \(\mathsf{ALG} \leq (2 - \epsilon) \mathsf{ADV} + c\)라는 가정과 \( \mathsf{ADV} = B \)라는 사실을 적용하면 \[2B - 1 < (2 - \epsilon) B + c\]를 얻게 됩니다. 이를 정리하면 \(B < \frac{c + 1}{\epsilon}\)을 얻게 되고, 위와 같이 모순을 유도할 수 있습니다. ■

마치며

이 글에서는 스키 대여 문제가 어떤 것인지 알아보고, 간단한 deterministic 2-competitive algorithm을 살펴 보았습니다. 마지막으로 어떤 deterministic algorithm도 2보다 좋은 경쟁비를 가질 수 없다는 점을 확인하였습니다. 참고로 본문에서는 \(B\)를 정수로 가정하였지만, 해당 가정이 없어도 (약간만 수정하면) 동일한 경쟁비와 하한을 얻을 수 있습니다.

 

여러분도 잘 아시다시피 대개의 경우 알고리즘에 randomness를 가미하면 그 성능이 좋아집니다. 같은 입력에는 항상 같은 출력만 하는 멍청한 deterministic algorithm과는 다르게 같은 입력에도 다른 결과를 출력할 수 있기 때문입니다. 이 문제의 경우에는 어떻게 될까요? 놀랍게도 \(\frac{e}{e-1} \approx 1.582\)의 경쟁비를 갖는 randomized algorithm이 존재합니다.

 

사실 이 글을 쓰기 시작할 당시에는 randomized algorithm도 함께 다루려고 했습니다만, 글이 너무 길어지는 것을 보고 두 부분으로 나누었습니다. 다음 글에서는 먼저 여기서 제시된 알고리즘과 동일하게 동작하지만 복잡한 테크닉을 사용한 새로운 알고리즘을 제시하고 이를 확장하여 randomized algorithm을 소개하고자 합니다. 다음 글도 같이 읽어 보신다면 훨씬 도움이 되리라 생각합니다. 고맙습니다.