온라인 알고리즘

온라인 알고리즘은 입력 데이터 전체가 미리 주어지는 것이 아니라 순차적으로 주어지는 환경에서 작동하는 알고리즘을 의미한다. 전통적인 알고리즘은 모든 입력 데이터를 알고 시작하는 반면, 온라인 알고리즘은 각 시점에서 입력의 일부만 알고 있으며, 그 시점에서 결정을 내려야 한다. 미래의 입력에 대한 정보 없이 현재까지의 입력만을 기반으로 결정을 내리기 때문에 최적의 해를 보장하기는 어렵지만, 실시간으로 변화하는 환경에 대응해야 하는 다양한 문제에 적용될 수 있다.

특징

• 순차적 입력: 입력 데이터가 한 번에 주어지는 것이 아니라 시간 순서대로 제공된다.
• 즉각적인 결정: 각 시점에서 현재까지의 정보를 기반으로 결정을 내려야 한다. 미래의 입력에 대한 예측은 불가능하거나 제한적이다.
• 경쟁적 분석 (Competitive Analysis): 온라인 알고리즘의 성능을 평가하는 방법으로, 최적의 오프라인 알고리즘의 성능과 비교하여 경쟁률 (competitive ratio)을 계산한다. 경쟁률은 온라인 알고리즘이 내는 결과가 최적의 결과에 비해 얼마나 나쁜지를 나타내는 지표이다.
• 후회 최소화 (Regret Minimization): 온라인 알고리즘의 또 다른 성능 평가 방법으로, 각 시점에서 온라인 알고리즘이 내린 결정으로 인해 발생하는 손실과 사후적으로 최적의 결정을 내렸을 때의 손실의 차이를 누적하여 평가한다.

예시

• 캐싱 (Caching): 자주 사용되는 데이터를 저장해두고 필요할 때마다 빠르게 접근할 수 있도록 하는 기술이다. 캐시 용량이 제한되어 있기 때문에 새로운 데이터가 들어올 때 어떤 데이터를 제거할지 결정하는 온라인 알고리즘이 필요하다. Least Recently Used (LRU) 알고리즘은 가장 오랫동안 사용되지 않은 데이터를 제거하는 방법의 대표적인 예시이다.
• 주식 거래: 주식 가격이 실시간으로 변동하는 상황에서 주식을 사고팔 시점을 결정하는 알고리즘은 온라인 알고리즘으로 볼 수 있다.
• 페이지 교체 알고리즘 (Page Replacement Algorithms): 운영체제에서 가상 메모리 관리 시 페이지 부재가 발생했을 때 어떤 페이지를 교체할지 결정하는 알고리즘도 온라인 알고리즘의 한 종류이다. FIFO (First-In, First-Out), LRU (Least Recently Used), Optimal Page Replacement 등이 있다.

관련 분야

• 강화 학습 (Reinforcement Learning): 에이전트가 환경과 상호작용하며 보상을 최대화하는 방향으로 학습하는 방법으로, 온라인 알고리즘과 밀접한 관련이 있다.
• 온라인 학습 (Online Learning): 데이터가 순차적으로 주어지는 환경에서 모델을 학습하는 방법이다.
• 경매 이론 (Auction Theory): 실시간으로 입찰이 진행되는 경매에서 최적의 입찰 전략을 결정하는 문제도 온라인 알고리즘으로 모델링할 수 있다.

참고 문헌

• Borodin, Allan; El-Yaniv, Ran (2005). Online Computation and Competitive Analysis. Cambridge University Press.