모노이드(Monoid)란? 세그먼트 트리를 다양한 쿼리로 일반화하는 방법

모노이드(Monoid)란? 세그먼트 트리를 다양한 쿼리로 일반화하는 방법세그먼트 트리는 원래 구간 합 구하기를 위해 설계된 자료구조지만,구간 합뿐만 아니라 최댓값, 최솟값, 최대공약수(GCD), XOR, 곱 등 다양한 쿼리로 확장할 수 있습니다.이 확장의 핵심 이론이 바로 **모노이드(Monoid)**입니다.이번 글에서는 모노이드 개념, 세그먼트 트리 일반화,그리고 최대값, GCD, XOR 쿼리로 확장하는 실제 예제까지 쉽고 명확하게 정리합니다.✅ 모노이드(Monoid)란 무엇인가?어떤 집합 S와 **이항 연산 ∘**가 있을 때,아래 두 조건을 모두 만족하면 (S, ∘)는 모노이드입니다:결합 법칙(Associative Law)(a ∘ b) ∘ c = a ∘ (b ∘ c)예시: 덧셈, 최댓값, 최솟값, G..
Programming 2025. 4. 29. 11:12
1
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG more
«   2025/05   »
일 월 화 수 목 금 토
1 2 3
4 5 6 7 8 9 10
11 12 13 14 15 16 17
18 19 20 21 22 23 24
25 26 27 28 29 30 31
글 보관함
반응형