온라인 알고리즘/Basic (2) 썸네일형 리스트형 동적, 스트리밍, 온라인 알고리즘 비교 (Dynamic, Streaming, and Online Algorithm) 최근, 저널에 제출했던 논문에 대한 심사 결과를 받았습니다. 논문의 주제는 온라인 알고리즘인데 스트리밍 알고리즘에 대한 문헌 검토가 부족하니 이를 보충하라는 평가를 받았습니다. 논문을 쓸 때 참조했던 다른 논문들에서는 스트리밍 알고리즘에 대한 내용을 발견하지 못했었는데 이런 평가를 받아서 처음에는 적잖이 당황했습니다. 그런데 이 내용들을 공부해 보니 서로 비슷하면서도 다른 특징들이 있더군요. 우리말로 적힌 자료는 찾기 어려웠어서, 제 공부를 겸해 이번에 알게 된 내용들을 여기에 정리하고자 합니다. 아래 내용을 미리 요약을 하자면 다음과 같습니다. 동적 알고리즘(dynamic algorithm)은 입력에 무언가 추가되거나 삭제되는 등의 수정(update)이 발생하며 그때마다 바뀐 입력에 맞는 올바른 답을 .. 온라인 알고리즘 (Online Algorithm) 일전에 유명한 온라인 문제 중 하나인 online bipartite matching을 다룬 적이 있었습니다. 당시에는 제 지식이 그렇게 깊지 않아서 제대로 설명하지 못했을뿐더러 잘못 전달한 내용도 있었습니다. 최근 개인적으로 온라인 알고리즘을 다시 공부하기 시작했는데, 겸사로 기존의 포스트를 내리고 다시 글을 적어보고자 합니다. 기존의 포스트는 더욱 보강하여 다시 올리도록 하겠습니다. 들어가기 일반적으로 알고리즘을 설계할 때 우리는 온전한 입력을 가정합니다. 예를 들어, 두 지점 사이의 최단 경로를 구하기 위해서는 해당 지점 및 경유할 수 있는 지점, 그리고 지점 사이의 거리가 입력으로 몽땅 주어집니다. 하지만 컴퓨터가 다루어야 하는 모든 문제들이 위 특성을 가지는 것은 아닙니다. 어떤 경우에는 처음에 .. 이전 1 다음
