linear_programming (2) 썸네일형 리스트형 [스키 대여 문제 / 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.. [선형 계획법] 쌍대성(Duality) Linear programming은 최적화 분야에서 잘 알려지고 연구되었으며 실제로도 많이 응용되는 기법입니다. 줄여서 LP라고도 하며, 우리말로는 선형계획법으로 불립니다. 이름이 뭔가 멋들어져서 괜스레 어렵게 느껴질 수도 있겠습니다만, 사실 별것 아닙니다. 고등학교 수학 시간에 다음과 같은 문제를 풀어보신 적이 있을 겁니다. 여러분은 빵집 사장님입니다. 식빵과 크루아상, 두 종류의 빵을 팔고 있습니다. 식빵 1kg을 만들기 위해서는 밀가루 5kg, 설탕 3kg이 필요하고 크루아상 1kg을 만들기 위해서는 밀가루 2kg, 설탕 5kg이 필요하다고 합시다. 1kg 당 식빵과 크루아상의 가격은 같습니다. (저는 제빵을 잘 모릅니다. 수치는 그저 예시일 뿐입니다.) 하루에 밀가루 20kg, 설탕 15kg이 들.. 이전 1 다음
