competitiveanalysis (1) 썸네일형 리스트형 스키 대여 문제의 경쟁비 하한 (Lower Bound of Competitive Ratio for Ski Rental) 스키 대여 문제(ski rental problem)는 대표적인 온라인 문제(online problem) 중 하나입니다. 이 문제에서는 스키장이 언제 폐장할지 모르는 상황에서 우리는 매일 스키를 대여하거나 구매해야 합니다. 한번 스키를 구매하면 이후 계속 사용할 수 있지만 대여를 하면 당일만 사용할 수 있습니다. 이 문제의 목표는 최소의 비용으로 폐장할 때까지 스키를 타는 방법을 찾는 것입니다. 이전 글에서는 이 문제를 결정론적(deterministic)으로 해결하는 2-경쟁 알고리즘(competitive algorithm)이 존재하고, 해당 경쟁비가 결정론적 알고리즘으로서는 이룰 수 있는 최선의 결과라는 것을 보였습니다. 2020/03/15 - [온라인 알고리즘/Ski rental] - [스키 대여 문제.. 이전 1 다음
