C++ 세그먼트 트리 구현 및 지연 전파(Lazy Propagation) 완벽 가이드
세그먼트 트리(Segment Tree)는 펜윅 트리(Fenwick Tree)와 유사하게 구간 합을 구하는 데 주로 사용되지만, 이 외에도 구간 최소/최대값 탐색, 구간 색칠 등 다양한 구간 연산을 효율적으로 처리할 수 있는 강력한 자료구조입니다. 본 가이드에서는 C++를 사용하여 세그먼트 트리의 기본 구현부터 지연 전파(Lazy Propagation)를 활용한 고급 기법까지 단계별로 다룹니다. ...
7월 23일 20:44에 게시됨
정수론과 기하학적 최적화를 활용한 알고리즘 문제 해결
약수 관계를 가진 정수 삼원조의 개수 구하기
양의 정수 \(n\)이 주어졌을 때, 다음의 조건을 모두 만족하는 정수 삼원조 \((a, b, c)\)의 개수를 구하는 문제입니다.
\(a + b + c = n\)
\(1 \le a < b < c \le n\)
\(a\)는 \(b\)의 약수이고, \(b\)는 \(c\)의 약수이다.
이 문제의 핵심은 약수 관계를 매개변수로 치환하여 식을 단순화하는 것입니다. ...
6월 27일 04:21에 게시됨
세그먼트 트리 심화: 다중 지연 전파와 세그먼트 트리 비트 구현
세그먼트 트리(Segment Tree)는 배열의 구간 연산을 효율적으로 처리하기 위한 강력한 자료구조입니다. 기본적인 구간 합 구하기를 넘어, 여러 종류의 업데이트를 동시에 처리하거나 구간 내 최솟값/최댓값을 갱신하는 고급 기법들이 존재합니다. 본 글에서는 지연 전파(Lazy Propagation)를 활용한 다중 연산 처리와 세그먼트 트리 비트(Segment Tree Beats)를 포함한 고 ...
5월 26일 20:46에 게시됨