자유처분 (1) 썸네일형 리스트형 온라인 가중치 이분 매칭 (Online Weighted Bipartite Matching) 저번 글에서는 온라인 이분 매칭 문제(online bipartite matching problem)가 무엇인지 설명하고 이를 경쟁적으로 해결하는 알고리즘에 대해서 알아 보았습니다. 문제를 간략히 다시 소개하도록 하겠습니다. 처음에는 가용할 수 있는 택시 몇 대가 주어진다. 이후 시간이 흐르면서 승객이 한 명씩 들어오며, 그때마다 그 승객을 태울 수 있는 택시가 무엇인지 정해진다. 이 승객을 태울 수 있는 택시 중 이전에 승객을 태운 적이 없는 택시 가운데 하나를 골라 이 승객을 태우든지, 아니면 승객을 태우지 않을 것을 매번 바로 결정해야 한다. 이 결정은 차후에 번복될 수 없다. 이때, 최대한 많은 승객을 태우시오. 위 예시에서 한 가지 현실과는 약간 동떨어진 점이 있다면 바로 건당 정액을 받는 수익 .. 이전 1 다음
