TwentyTwentyOne

[응용편] Link/Cut Tree에 경로 합, 경로 최댓값 추가하기 – Augmented LCT 구현앞선 글에서는 Link/Cut Tree(LCT)의 **핵심 구조와 기본 연산(link, cut, access)**을 Python으로 직접 구현해보았습니다.이번에는 한 단계 더 나아가서,LCT 노드에 값을 부여하고 경로의 합이나 최댓값을 빠르게 계산할 수 있는 구조로 확장해보겠습니다.✨ 목표: 경로 질의가 가능한 LCT기본 LCT는 access(u), make_root(u), link(u, v) 등을 수행할 수는 있지만,실제로는 경로 상의 합/최댓값/최솟값을 빠르게 계산해야 할 일이 많습니다.예: "u부터 v까지 간선 가중치의 합은?", "가장 큰 값은?"이 기능을 위해 우리는 LCT 노드에 다음 정보를 ..

📌 JAX로 Graph Neural Network (GNN) 기반 시계열 예측 모델 만들기 – 관계 + 시계열 데이터를 동시에 학습하는 방법🤔 왜 GNN + 시계열 예측인가?우리는 종종 서로 연결된 시계열 데이터를 다뤄야 합니다.예를 들어:전력망: 각 발전소/변전소 간의 연결센서 네트워크: 제조설비 내 센서들이 상호작용도시 교통: 각 지역의 교통량 + 도로망 연결 구조이럴 때 Graph Neural Network(GNN)는 각 노드(시계열 데이터 단위)가자신과 이웃 노드의 정보까지 활용해서 더 정교한 예측을 가능하게 합니다.🎯 GNN 기반 시계열 예측 모델 개요구성 요소 설명노드시계열 데이터를 가진 단위 (센서, 지역 등)엣지노드 간의 관계 정보 (거리, 영향력, 상관도 등)GNN 레이어이웃 노드 ..

Python으로 Link/Cut Tree 직접 구현하기 (기초 버전)앞서 소개한 **Link/Cut Tree (LCT)**는 동적 트리를 위한 강력한 도구지만,직접 구현해보려면 Splay Tree, Lazy Propagation, 경로 관리 등복잡한 요소를 잘게 나누어 학습하고 구현해야 합니다.이번 글에서는 기본 LCT의 핵심 기능인access, make_root, link, cut, connected, find_root를Python으로 최소한의 형태로 구현합니다.🧱 기본 구조 설명📌 전제: 각 트리 노드는 Splay Tree 노드로 동작class Node: def __init__(self, id): self.id = id self.left = None se..

[고급편] Link/Cut Tree 완전 정복: 동적 트리 쿼리와 간선 연결/삭제 처리 기법이제 우리는 정적인 트리(정해진 구조에서 쿼리만 수행하는 트리)를 넘어서,동적으로 간선을 연결하거나 삭제하면서도 경로 쿼리를 빠르게 처리하는**Link/Cut Tree (LCT)**라는 강력한 자료구조를 다룰 차례입니다.🔍 Link/Cut Tree(LCT)란?간선을 동적으로 삽입/삭제할 수 있는 트리 자료구조로두 노드 사이의 경로 쿼리, 업데이트 등을 O(log N)에 처리할 수 있는 구조입니다.📌 대표적으로 다음 기능을 지원합니다:연산 설명link(u, v)u와 v를 간선으로 연결 (트리가 되도록)cut(u, v)u와 v 사이 간선을 제거find_root(u)u가 속한 트리의 루트 반환lca(u, v)u와 v..

📌 JAX로 Prophet 스타일 + Neural Basis Expansion Hybrid 시계열 예측 모델 구현🌟 왜 Hybrid 모델인가?Prophet은 계절성, 추세, 휴일 효과 등 해석 가능한 예측이 강점**Neural Basis Expansion (N-BEATS)**는 딥러닝 기반의 고정된 블록을 쌓아 높은 예측 정확도를 달성JAX에서는 정형적 계절성 + 비선형 딥러닝 구조를 동시에 반영한 Hybrid 모델을 유연하게 구현할 수 있음🎯 이 글에서 구현하는 Hybrid 구성구성요소 역할Trend Component (Linear/Logistic)Prophet의 추세 모델링Seasonal Component (Fourier basis)주기성 정보 반영Residual Neural Component ..

실전 문제 풀이: 트리 쿼리 알고리즘 완전 적용하기 (ETT & HLD & LCA)이번 글에서는 지금까지 학습한 트리 쿼리 알고리즘들을실전 문제에 적용하는 과정을 단계별 코드 구현과 함께 정리합니다.🎯 문제 1: BOJ 13510 – 트리와 쿼리 1기본 트리 위에서, 간선 가중치 변경 + 경로 가중치 합 쿼리를 처리🔍 요구 기능간선의 가중치를 변경 (change(u, v, w))두 노드 u–v 간의 가중치 합 반환 (query(u, v))🔧 선택 알고리즘: HLD + 세그먼트 트리간선 정보를 노드에 매핑 (보통 자식 노드 기준으로 저장)체인 분할 후 세그먼트 트리 구성update(pos[v]) = w 로 갱신path_query(u, v)는 체인 단위로 합산✅ 핵심 코드 요약def path_query..

트리 알고리즘 마스터 로드맵: LCA부터 HLD, ETT, LCT까지 완전 정복하는 순서 가이드알고리즘 공부에서 트리는 단골 주제입니다.하지만 단순한 DFS/BFS 수준을 넘어서 경로 질의, 노드 업데이트, 동적 연결까지 다루려면체계적인 학습 로드맵이 필요합니다.이번 글에서는 기초부터 고급까지 트리 알고리즘을 마스터하는 로드맵을 제시합니다.각 단계별로 학습 포인트, 추천 자료, 대표 문제도 함께 정리합니다.🧱 1단계: 트리 기초 (DFS, 부모 저장, 깊이, 서브트리 크기)주요 개념트리는 사이클 없는 연결 그래프루트 노드 기준 DFS 탐색각 노드의 깊이(depth), 부모(parent), 자식 관계 등실습 목표서브트리 크기 계산루트로부터 거리 계산트리의 리프 노드, 중심 노드 찾기추천 문제BOJ 117..

📌 JAX로 Transformer 기반 다변량 시계열 예측 모델 구현 - Multi-head Attention을 활용한 고급 Forecasting⚡️ Transformer는 어떻게 시계열 예측에 유리할까?Self-Attention: 시계열 전 구간에서 정보 상호작용 가능병렬 처리: RNN에 비해 학습/추론 속도 빠름멀티채널 지원: 여러 센서 또는 변수(feature) 간 관계 모델링 용이멀티스텝 예측: 미래 10, 20, 30 step까지도 동시에 예측 가능💡 모델 구조 개요구성 요소 설명Positional Encoding시간 정보를 인코딩Encoder Block다중 시점과 피처 간 상호작용Decoder Block (선택적)과거 + 미래 조건 기반 예측Output Head다변량 미래값 출력💾 1. ..

📌 JAX로 Seq2Seq 시계열 예측 모델 구현 - 미래 시점을 예측하는 딥러닝 구조📈 시계열 예측(Time Series Forecasting)이란?시계열 예측은 과거의 데이터를 바탕으로 미래의 값을 추정하는 작업입니다.JAX에서는 고속 수치 연산을 활용하여 Seq2Seq 구조의 시계열 예측 모델을 효율적으로 구현할 수 있습니다.🎯 Seq2Seq 구조란?Sequence-to-Sequence(Seq2Seq) 모델은 다음과 같은 구조를 갖습니다:구성 설명Encoder과거 시점 데이터를 받아 잠재 표현(z) 생성Decoderz를 입력으로 받아 미래 시점의 예측값 출력입력 시계열 예30개의 과거 값출력 시계열 예다음 10개의 미래 값💾 1. 시계열 데이터 준비import pandas as pdimpor..

트리 쿼리 알고리즘 비교: Euler Tour Tree vs Heavy-Light Decomposition지금까지 우리는 트리 쿼리를 처리하는 다양한 알고리즘 중**Euler Tour Tree (ETT)**와 **Heavy-Light Decomposition (HLD)**를 학습해왔습니다.이번 글에서는 두 방법론을 성능, 유연성, 적용 가능 문제 유형 관점에서 비교해보고,실전에서 어떤 상황에 어떤 기법을 선택할지 기준을 제시합니다.✅ 공통 목표: 트리 쿼리를 빠르게 처리트리에서 다음과 같은 쿼리를 빠르게 처리하고자 할 때:경로의 합/최댓값/최솟값경로에 대한 업데이트서브트리 통계 계산노드 색칠 및 통계동적 트리 간선 연결/삭제우리는 보통 ETT, HLD, LCT 중 하나를 선택하게 됩니다.이번 글에서는 그..