역연산 안 되는 슬라이딩 윈도우 집계, 스택 2개로 O(1) 끝내는 법

요약 슬라이딩 윈도우(Sliding Window) 내에서 합계나 최댓값, 최솟값 같은 집계(Aggregation)를 반복적으로 계산해야 하는 문제는 컴퓨터 공학에서 흔히 마주치는 과제입니다. 만약 정수 덧셈처럼 역연산(뺄셈)이 존재하는 연산이라면 덱(deque)을 사용해 새 원소가 들어올 때 더하고 나갈 때 빼주는 방식으로 O(1)에 쉽게 해결할 수 있습니다. 하지만 최솟값, 최댓값, 분위수, HyperLogLog 같은 근사 유니크 카운트, 심지어 NaN 처리가 까다로운 부동소수점 덧셈처럼 '역연산이 불가능한 집계'의 경우 기존 방식으로는 계산이 불가능합니다. 글쓴이는 과거 6년 전 슬라이딩 윈도우에서 최소·최댓값만을 구하는 알고리즘을 고안해 커뮤니티에 올린 적이 있었으나, 결합법칙이 성립하는 거의 모든 집계 연산에 범용적으로 적용할 수 있는 훨씬 우아한 해법을 발견하고는 자신의 옛 알고리즘이 무의미해졌다고 밝혔습니다. 이 알고리즘은 최악의 경우에도 O(1)을 달성하는 복잡한 논문을 읽던 중 발견한 것으로, 분할 상환(Amortized) O(1) 시간에 동작하면서도 구조는 훨씬 단순한 '두 개의 스택(Two-stack)'을 활용합니다. 이 방식은 원소를 담는 스택(values)과 누적 집계값을 역순으로 보관하는 스택(cum_aggs)을 유지합니다. push 연산 시에는 새 원소를 values에 넣으며 최신 집계값을 갱신하고, pop 연산 시 cum_aggs가 비어 있으면 values에 쌓인 원소들을 하나씩 꺼내며 누적 집계를 계산해 cum_aggs에 옮겨 담습니다. 윈도우 크기를 w라고 할 때, w번의 pop마다 한 번씩 O(w) 작업이 발생하므로 원소당 평균 연산 시간은 O(1)로 묶입니다. 최종 평가는 cum_aggs의 최상단 값과 values의 집계값을 결합하는 것만으로 즉시 끝나며, 메모리 또한 O(w)만 사용합니다. 윈도우 크기가 고정되지 않고 가변적인 상황에서도 완벽히 동작하는 매우 실용적이고 우아한 기법입니다.