RMQ와 LCA를 위한 스파스 테이블(Sparse Table) 최적화: 구간 최소/최대/공통 조상 빠르게 찾기
RMQ와 LCA를 위한 스파스 테이블(Sparse Table) 최적화: 구간 최소/최대/공통 조상 빠르게 찾기스파스 테이블(Sparse Table)은 정적 데이터에서 구간 최소값(RMQ), 최대값, GCD 등을**매우 빠르게 계산(O(1))**할 수 있는 자료구조입니다.특히 LCA(Lowest Common Ancestor) 문제 해결에도 최적화되어 있습니다.이번 글에서는 스파스 테이블의 구조와 구성 원리, RMQ 문제 해결법,그리고 LCA 문제를 스파스 테이블로 최적화하는 방법까지 다룹니다.✅ 스파스 테이블(Sparse Table) 개념정적 배열에서 여러 구간의 최솟값/최댓값/GCD 등을 빠르게 구하는 자료구조전처리 시간: O(N log N)쿼리 시간: O(1)🔑 스파스 테이블 사용 조건업데이트가 없는..
Programming
2025. 5. 8. 11:14
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- gatsbyjs
- 파이썬 알고리즘
- Prisma
- nodejs
- github
- llm
- REACT
- 개발블로그
- PostgreSQL
- Ktor
- 웹개발
- LangChain
- SEO최적화
- CI/CD
- AI챗봇
- Next.js
- 프론트엔드
- fastapi
- rag
- NestJS
- kotlin
- Python
- 백엔드개발
- App Router
- 관리자
- Webpack
- nextJS
- seo 최적화 10개
- 프론트엔드면접
- Docker
| 일 | 월 | 화 | 수 | 목 | 금 | 토 |
|---|---|---|---|---|---|---|
| 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 |
글 보관함
반응형