TwentyTwentyOne

CDQ 분할 정복 – 다차원 쿼리를 분할로 해결한다“이 문제, 쿼리는 오프라인인데, 좌표가 2~3차원 이상이라 정렬이 안 되는데요…?”이런 상황에서 진가를 발휘하는 고급 쿼리 최적화 기법,바로 **CDQ 분할 정복(CDQ Divide & Conquer)**입니다.이번 글에서는단순 정렬로는 해결이 어려운다차원 범위 쿼리 문제를 CDQ 방식으로 풀어내는고급 오프라인 쿼리 전략을 소개합니다.📌 언제 사용하는가?쿼리를 미리 다 받아서 오프라인 처리할 수 있을 때쿼리가 2차원~3차원 좌표 조건으로 구성될 때예) 시간 기준 정렬 + 누적 카운트 + 조건 만족하는 개수 세기 등💡 핵심 아이디어분할정복을 활용하여좌표 공간을 시간 순서나 한 축 기준으로 쪼개며쿼리의 영향을 분리 정리하는 방법입니다.쿼리/데이터를 시간..

🧠 ARIMA + Neural Networks in JAX – Hybrid Time Series Forecasting That WorksSometimes deep learning models overkill simple patterns — like a steady trend or seasonality.But classical models like ARIMA handle those beautifully.So… what if we combined them?That’s the idea behind hybrid models:Let ARIMA model the easy, linear stuffLet a neural net learn the leftover noiseHybrid = classical stats +..

🔭 Forecasting with Transformers in JAX – Time Series Gets an Attention UpgradeIn our last post, we trained a simple LSTM forecaster in JAX.It was lightweight and interpretable — but it struggles with long sequences and parallelism.This time, we're bringing out the big guns:🧠 Transformers.Yes, the same architecture behind ChatGPT can be applied to time series forecasting — and it works surprisi..

Persistent Segment Tree – 과거의 배열로도 쿼리할 수 있다?“업데이트를 했는데, 예전 배열 상태에 대해 다시 쿼리해야 한다?”이런 상황이 오프라인 쿼리에서 꽤 자주 등장합니다.이럴 때 정말 유용한 자료구조가 바로 Persistent Segment Tree입니다.한마디로 말하자면,세그먼트 트리의 모든 시점(버전)을 저장하는 트리입니다.시간은 흐르지만, 과거도 기억하는 구조라고 생각하시면 됩니다.🎯 언제 사용하는가?배열이 지속적으로 업데이트되는데,이전 버전 상태에서 구간 쿼리를 자주 해야 할 때예:K번째 수 문제히스토리 기반의 데이터 분석롤백 가능한 시뮬레이션💡 핵심 아이디어기존 세그먼트 트리는 값이 바뀌면 트리 전체를 수정하지만,Persistent Segment Tree는변화가 생긴..

이벤트 기반 Sweep Line – 쿼리를 정렬로 해결하는 시공간 최적화 기법“쿼리도 정렬로 해결할 수 있다?”네, 1차원~2차원 공간 쿼리에서 가장 많이 쓰이는 전략 중 하나입니다.바로 이벤트 기반 Sweep Line입니다.이번 글에서는직선, 점, 사각형, 좌표 범위 같은 쿼리를이벤트(Event)로 치환해 정렬하고 처리하는고전적이면서도 현대까지 사랑받는 쿼리 최적화 기법을 소개할게요.🎯 언제 사용하는가?쿼리와 데이터가 모두 “좌표 기반”일 때예: 점 안에 포함된 사각형 개수 구하기, 사각형 교차 판정, x ≤ ?, y ≤ ? 조건에 해당하는 점 개수 등"쿼리 vs 데이터" → 같은 기준(x좌표 등)으로 정렬 가능할 때💡 기본 아이디어좌표/이벤트들을 한 축 기준으로 정렬그리고 차례차례 훑으면서현재 상..

오프라인 쿼리 + 유니온파인드 – 쿼리 순서를 바꾸면 보이지 않던 최적화가 보인다“유니온 파인드도 쿼리 최적화 알고리즘이라고요?”네, 맞습니다. 특히 오프라인 쿼리 방식과 결합되면굉장히 강력한 쿼리 처리 도구가 됩니다.이번 글에서는 오프라인 쿼리 처리 + 유니온 파인드 조합으로연결성 쿼리, 삭제 쿼리, 시간축을 활용한 쿼리 처리까지한 방에 해결하는 방법을 알려드릴게요.🎯 오프라인 쿼리란?쿼리를 입력 순서대로 처리하지 않아도 되는 상황모든 쿼리를 미리 모아서,쿼리 순서를 전략적으로 정렬 또는 역순 처리해도 문제 없음📌 대표 문제 예:1. x, y가 연결되어 있었나요?2. 그래프에서 간선이 사라질 때, 연결성을 유지하는 쿼리🧠 대표 전략: 시간 역순 처리 (Reverse Time Trick)간선을 "삭..

Time Series Forecasting with LSTM in JAX – A Clean, Minimal ImplementationWelcome back to the JAX Time Series series.We’ve preprocessed our data, normalized it, created sliding windows, and now… it’s time for our first model:a simple LSTM for sequence-to-sequence prediction.If you’re used to PyTorch or Keras, Flax might feel minimal — in a good way.We’ll build a model from scratch and train it o..

🧪 Time Series Preprocessing with JAX – The Foundation for Accurate ForecastsWelcome back to the JAX for Time Series series.Before we dive into deep models like LSTM or Transformer, we need to do something that most tutorials skip over:proper time series preprocessing.Why? Because garbage in = garbage out.Even the most powerful neural networks can’t save you from bad input structure.⚙️ Step 1: L..

Sqrt Decomposition – 블럭으로 나누면 쿼리가 빨라진다“쿼리 수는 많은데, 세그먼트 트리 쓰기엔 과하다고 느낀 적 있나요?”이런 상황에서 정말 유용한 게 바로 Sqrt Decomposition,한국말로는 제곱근 분할 기법입니다.단순하면서도 강력한 쿼리 최적화 알고리즘으로,초보자도 이해하기 쉽고 구현도 간단한 구조예요.🎯 언제 쓰는가?배열 길이: N ≤ 1e5쿼리 수: Q ≤ 1e5요구 연산이 너무 복잡하지 않을 때예: 구간 합, 최댓값, 특정 값의 개수, 구간 곱 등🧠 핵심 아이디어배열을 √N 크기의 블럭으로 나눈다.각 블럭에 대한 요약 정보를 미리 저장해둔다.질의할 땐:전체 블럭이면 O(1)부분 블럭이면 O(√N) 이내→ 결국 전체 쿼리는 O(√N × Q) 정도로 처리됨📌 구조 설계..

Mo’s Algorithm on Tree – 트리에서 구간 쿼리 최적화하는 마법“모스 알고리즘은 1차원 배열에서만 쓴다?”No. 트리에서도 사용할 수 있습니다!그게 바로 Mo’s Algorithm on Tree, 줄여서 Mo on Tree예요.트리 위에서“이 노드부터 저 노드까지의 경로에서 다른 수의 개수는?”“서브트리 내에서 값이 k인 노드의 수는?”이런 문제는 전통적인 Mo’s 알고리즘만으론 풀기 어렵습니다.하지만 잘 응용하면 트리 위에서도 빠르게 처리 가능하다는 걸 지금부터 보여드릴게요.📌 핵심 아이디어 요약Mo’s Algorithm on Tree는트리 구조를 일차원 배열처럼 펼쳐서,그 배열 위에서 Mo’s Algorithm을 수행합니다.이걸 가능하게 하는 기술이 바로 **Euler Tour(오일..