온라인 알고리즘/Ski rental (4) 썸네일형 리스트형 예측이 있는 스키 대여 문제 (Ski Rental Problem with Predictions) 온라인 문제(online problem)의 대표격인 스키 대여 문제(ski rental problem)는 지난 수십 년간 깊이 그리고 널리 연구되어 온 매우 유서 깊은 문제입니다. 제 블로그에서도 비중 있게 다룬 적이 있는데요. 문제는 다음과 같이 정의됩니다. 우리는 스키장이 문을 닫을 때까지 스키를 타고 싶어 합니다. 스키를 타는 방법은 두 가지로, 하나는 1 원으로 스키를 하루 대여하는 것이고, 다른 하나는 \(B\) 원으로 스키를 구매하는 것입니다. 당연히 언젠가 스키를 대여하면 다음날에는 또 스키를 대여하든지 구매하든지 하여야 하며, 언젠가 스키를 구매하면 더 이상 그런 고민을 할 필요가 없어집니다. 이때 최소의 비용으로 스키장이 문을 닫을 때까지 스키를 타는 것이 문제의 목표입니다. 만약 스키장.. 스키 대여 문제의 경쟁비 하한 (Lower Bound of Competitive Ratio for Ski Rental) 스키 대여 문제(ski rental problem)는 대표적인 온라인 문제(online problem) 중 하나입니다. 이 문제에서는 스키장이 언제 폐장할지 모르는 상황에서 우리는 매일 스키를 대여하거나 구매해야 합니다. 한번 스키를 구매하면 이후 계속 사용할 수 있지만 대여를 하면 당일만 사용할 수 있습니다. 이 문제의 목표는 최소의 비용으로 폐장할 때까지 스키를 타는 방법을 찾는 것입니다. 이전 글에서는 이 문제를 결정론적(deterministic)으로 해결하는 2-경쟁 알고리즘(competitive algorithm)이 존재하고, 해당 경쟁비가 결정론적 알고리즘으로서는 이룰 수 있는 최선의 결과라는 것을 보였습니다. 2020/03/15 - [온라인 알고리즘/Ski rental] - [스키 대여 문제.. [스키 대여 문제 / Ski Rental Problem] 선형 계획법을 이용한 Randomized Algorithm 스키 대여 문제(ski rental problem)에 대해서 잘 모르시는 분들은 이 글을 읽기 전에 이전 포스트를 읽어 보시는 것을 추천드립니다. 2020/03/15 - [온라인 알고리즘/Ski rental problem] - [스키 대여 문제 / Ski rental problem] 문제 정의 & break-even algorithm [스키 대여 문제 / Ski rental problem] 문제 정의 & break-even algorithm 이번 포스트에서는 기초적인 온라인 문제 중 하나인 스키 대여 문제(ski rental problem)를 다루어 보도록 하겠습니다. 온라인 문제 및 온라인 알고리즘이 무엇인지는 이전 글을 참조해 주시기 바랍니다. 아래의.. gazelle-and-cs.tistory.co.. [스키 대여 문제 / Ski Rental Problem] 문제 정의 & Break-Even Algorithm 이번 포스트에서는 기초적인 온라인 문제 중 하나인 스키 대여 문제(ski rental problem)를 다루어 보도록 하겠습니다. 온라인 문제 및 온라인 알고리즘이 무엇인지는 이전 글을 참조해 주시기 바랍니다. 아래의 내용은 이 글을 제대로 숙지하고 있다는 전제 하에 작성되었습니다. 2020/03/14 - [온라인 알고리즘] - 온라인 알고리즘 온라인 알고리즘 일전에 유명한 온라인 문제 중 하나인 online bipartite matching을 다룬 적이 있었습니다. 당시에는 제 지식이 그렇게 깊지 않아서 제대로 설명하지 못했을뿐더러 잘못 전달한 내용도 있었습니다. 최근 개인적으.. gazelle-and-cs.tistory.com 이미 위 글에서 스키 대여 문제가 무엇인지 간략하게 소개되어 있습니다만 이.. 이전 1 다음
