경쟁성_분석 (1) 썸네일형 리스트형 온라인 알고리즘 (Online Algorithm) 일전에 유명한 온라인 문제 중 하나인 online bipartite matching을 다룬 적이 있었습니다. 당시에는 제 지식이 그렇게 깊지 않아서 제대로 설명하지 못했을뿐더러 잘못 전달한 내용도 있었습니다. 최근 개인적으로 온라인 알고리즘을 다시 공부하기 시작했는데, 겸사로 기존의 포스트를 내리고 다시 글을 적어보고자 합니다. 기존의 포스트는 더욱 보강하여 다시 올리도록 하겠습니다. 들어가기 일반적으로 알고리즘을 설계할 때 우리는 온전한 입력을 가정합니다. 예를 들어, 두 지점 사이의 최단 경로를 구하기 위해서는 해당 지점 및 경유할 수 있는 지점, 그리고 지점 사이의 거리가 입력으로 몽땅 주어집니다. 하지만 컴퓨터가 다루어야 하는 모든 문제들이 위 특성을 가지는 것은 아닙니다. 어떤 경우에는 처음에 .. 이전 1 다음
