TwentyTwentyOne

Lazy Propagation + 모노이드 세그먼트 트리: 다양한 쿼리와 구간 업데이트를 동시에 처리하는 고급 기법지금까지 우리는세그먼트 트리를 통해 빠른 구간 쿼리를Lazy Propagation을 통해 효율적인 구간 업데이트를**모노이드(Monoid)**를 통해 다양한 연산으로의 확장을각각 배웠습니다.이번 글에서는 이 세 가지를 하나의 프레임워크로 통합하여**“다양한 연산을 지원하는 구간 갱신 + 쿼리용 세그먼트 트리”**를 구현하고 실전 문제에 바로 활용할 수 있도록 정리합니다.✅ 목표: 어떤 연산도 지원하는 세그먼트 트리 만들기기능 지원 여부구간 쿼리✅구간 갱신 (덧셈, 대입 등)✅연산 유형 (합, 최대, 최소, GCD 등)✅✅ 설계 전략: 모노이드 + 지연 전파 (Lazy Propagation)기..

모노이드(Monoid)란? 세그먼트 트리를 다양한 쿼리로 일반화하는 방법세그먼트 트리는 원래 구간 합 구하기를 위해 설계된 자료구조지만,구간 합뿐만 아니라 최댓값, 최솟값, 최대공약수(GCD), XOR, 곱 등 다양한 쿼리로 확장할 수 있습니다.이 확장의 핵심 이론이 바로 **모노이드(Monoid)**입니다.이번 글에서는 모노이드 개념, 세그먼트 트리 일반화,그리고 최대값, GCD, XOR 쿼리로 확장하는 실제 예제까지 쉽고 명확하게 정리합니다.✅ 모노이드(Monoid)란 무엇인가?어떤 집합 S와 **이항 연산 ∘**가 있을 때,아래 두 조건을 모두 만족하면 (S, ∘)는 모노이드입니다:결합 법칙(Associative Law)(a ∘ b) ∘ c = a ∘ (b ∘ c)예시: 덧셈, 최댓값, 최솟값, G..

2차원 펜윅 트리(2D Fenwick Tree) 완전 정리: 2D 누적합 쿼리 최적화 방법과 구현 예제1차원 배열 누적합을 빠르게 처리할 수 있는 **펜윅 트리(Fenwick Tree)**를,2차원 배열(행렬)로 확장한 것이 바로 **2차원 펜윅 트리(2D BIT)**입니다.이번 글에서는 2D 펜윅 트리의 개념, 구조, 쿼리 및 업데이트 구현법,그리고 실제 이미지 누적합 문제나 2D 구간 쿼리 문제 적용법까지 다룹니다.✅ 2D 펜윅 트리란?2차원 배열(Matrix)의 직사각형 구간 합을 빠르게 구하고 갱신할 수 있도록 설계된 자료구조입니다.1D BIT에서 누적합을 O(log N)으로 처리했던 것처럼,2D BIT는 O(log N × log M) 시간에 쿼리와 업데이트를 처리합니다.🔍 2D BIT 동작 개..

펜윅 트리(Fenwick Tree) aka BIT 완전 정리: 개념, 구현, 세그먼트 트리와 차이점 비교**펜윅 트리(Fenwick Tree)**는 **Binary Indexed Tree (BIT)**라고도 불리며,배열에서 구간 합을 빠르게 처리하기 위한 자료구조입니다.구간 합 구하기, 누적합 업데이트가 핵심이며,세그먼트 트리보다 간단하고 메모리 효율적이어서 실전에서 많이 쓰입니다.이번 글에서는 Fenwick Tree의 원리, 구현법, 주요 연산,그리고 세그먼트 트리와의 차이점과 문제 적용까지 상세히 알아봅니다.✅ 펜윅 트리란?정수 배열에서 누적합을 빠르게 구하거나 갱신할 수 있도록 설계된 자료구조**시간 복잡도 O(log N)**로 쿼리 및 업데이트가 가능🔍 구조 개념 (Binary Indexed T..

Lazy Propagation 완벽 이해: 세그먼트 트리에서 구간 업데이트를 효율적으로 처리하는 방법세그먼트 트리에서 구간 단위로 값을 업데이트해야 할 경우, 단순하게 처리하면 **시간복잡도가 O(N)**이 되어버려 효율이 급격히 떨어집니다.이를 해결하는 고급 기법이 바로 **Lazy Propagation(지연 전파)**입니다.이번 글에서는 Lazy Propagation의 개념, 필요성, 작동 방식, Python 코드 구현, 실전 문제 적용까지 단계별로 정리합니다.✅ Lazy Propagation이란?세그먼트 트리에서 여러 구간을 한 번에 갱신할 때, 갱신 정보를 지연시켜 저장해 두었다가**필요할 때만 적용(전파)**하는 최적화 기법입니다.📉 왜 필요한가?기존 세그먼트 트리로 아래와 같은 연산을 수행한..

세그먼트 트리(Segment Tree) 완벽 정리: 기본 개념부터 구간 합, 최솟값, Lazy Propagation까지**세그먼트 트리(Segment Tree)**는 배열의 구간 정보를 효율적으로 저장하고, 빠르게 질의/갱신할 수 있는 자료구조입니다.특히 구간 합, 최댓값, 최솟값, 특정 조건 카운트 등에서 **O(log N)**의 시간복잡도를 제공하여,코딩 테스트, 실전 알고리즘 문제에서 매우 중요한 역할을 합니다.이번 글에서는 세그먼트 트리의 구조, 구축(Build), 쿼리(Query), 업데이트(Update) 방법과**Lazy Propagation(지연 업데이트)**까지 단계별로 정리합니다.✅ 세그먼트 트리란?원래 배열을 트리 형태로 분할하여 저장하는 구조각 노드는 특정 구간을 대표하고, 구간 전체..

최소 공통 조상(LCA: Lowest Common Ancestor) 알고리즘 정복하기 – 개념, 세 가지 구현 방법, 실전 문제 응용 **LCA(Lowest Common Ancestor)**는 트리에서 두 노드의 가장 가까운 공통 조상을 찾는 알고리즘입니다.이는 트리 기반의 그래프 문제, 유전자 정보 분석, 네비게이션 경로, 파일 시스템 경로 찾기 등 실전에서 다양하게 활용됩니다.이번 글에서는 **LCA의 개념, 3가지 구현 방법(DFS + Parent 배열, Binary Lifting, 세그먼트 트리)**과 함께백준 실전 문제 적용법까지 완벽하게 정리합니다.✅ LCA란 무엇인가?트리에서 두 노드 A와 B의 조상 중에서 가장 깊은(가장 가까운) 공통 조상 노드를 말합니다.예를 들어, 다음과 같은 트리에서..

유니온 파인드(Union-Find) 알고리즘 완전 이해: 사이클 판별, 네트워크 그룹화, MST 응용까지**유니온 파인드(Disjoint Set, Union-Find)**는 그래프 이론에서 자주 쓰이는 대표적인 자료구조 중 하나로,서로소 집합을 관리하면서 **집합 간의 합치기(Union)**와 같은 집합인지 확인(Find) 작업을 빠르게 처리할 수 있게 해줍니다.이번 글에서는 유니온 파인드의 개념, 구현법, 경로 압축 최적화,그리고 **사이클 판별, 네트워크 연결 확인, 크루스칼 알고리즘(MST)**에의 응용까지 완전히 정리합니다.✅ 유니온 파인드란?여러 노드가 속한 **집합(components)**을 트리 구조로 표현하여두 노드가 같은 집합에 속해 있는지를 빠르게 확인하는 알고리즘🔹 핵심 연산연산명 ..

위상 정렬(Topological Sort) 완벽 이해: 개념, 구현, 사이클 판별까지 한 번에 정리**위상 정렬(Topological Sort)**은 방향 그래프(DAG: Directed Acyclic Graph)의 정점들을 선후 관계에 맞춰 순서대로 나열하는 알고리즘입니다.선수 과목 → 후수 과목, 작업 순서 지정, 빌드 순서 등 순차적 의존성을 가지는 문제에서 자주 활용됩니다.이번 글에서는 위상 정렬의 개념, 구현 방식(Kahn 알고리즘 / DFS 기반), 사이클 판별, 실전 예제까지 완벽하게 정리합니다.✅ 위상 정렬(Topological Sort)이란?방향성이 있는 그래프(DAG)에서,"A → B"라면 A를 B보다 먼저 나열하는 방식으로 모든 정점을 정렬🔹 위상 정렬의 전제 조건사이클이 없어야 한..

최소 신장 트리(MST) 완전 이해: 크루스칼(Kruskal) vs 프림(Prim) 알고리즘 비교와 구현**최소 신장 트리(Minimum Spanning Tree, MST)**는 그래프 알고리즘의 꽃이라 불립니다.특히 네트워크 비용 최소화, 전선 연결, 도로망 구성 등 비용 최소화 문제에서 많이 등장하며,**크루스칼(Kruskal)**과 프림(Prim) 알고리즘이 대표적인 해결책입니다.이번 글에서는 MST의 개념과 이 두 알고리즘의 차이, 작동 방식, Python 구현, 시간복잡도 비교까지 완전 정리합니다.🌲 MST(최소 신장 트리)란?그래프 내 모든 정점을 포함하면서사이클이 없고,간선의 가중치 합이 최소인 트리✅ 주요 특징그래프가 연결되어 있어야 함간선 수 = 정점 수 - 1MST는 여러 개가 존재할..