Algorithms/알고리즘 개념 (11) 썸네일형 리스트형 [알고개념] 2. Lowest Common Ancestor LCA는 스터디 발표 자료로 블로그 글을 대신합니다. [알고개념] 1. Segment Tree 1. 알고리즘 개념 세그먼트 트리: 각 노드가 구간 정보를 가지고 있는 트리를 의미한다. 루트 노드는 전체 구간을 가지고, 리프 노드는 길이가 1인 구간들을 가진다. 리프 노드를 제외한 다른 모든 노드는 항상 2개의 자식을 가진다. -> 완전 이진 트리 꼴 리프 노드가 $N$개인 완전 이진 트리의 전체 노드의 개수는 $2N-1$이고, 높이는 $\lceil log\ N \rceil$ 이다. $N$이 2의 제곱꼴이 아닐 경우에는 남는 구간을 기본값으로 채워서 사용한다. 2. 알고리즘 구현 start == end : 리프 노드는 구간 길이가 1이므로 바로 값을 대입한다. node의 왼쪽 자식은 node*2이고, 오른쪽 자식은 node*2+1이다. node에 저장된 구간이 [start,end]라면, 왼쪽 자식은.. [알고개념] 알고리즘 개념 목차 (이 게시판에는 2022년 3~4월간 알고리즘 초급, 중급 스터디에서 공부한 내용을 업로드할 예정입니다.) 초급 알고리즘 목차 Brute-Force Greedy DP (Dynamic Programming) Math Data Structure Back Tracking DFS & BFS 고급 알고리즘 목차 Segment Tree LCA (Lowest Common Ancester) SCC (Strongly Connected Component) kmp Lazy Propagation 2-SAT Network Flow - Dinic Algorithm Bipartite Matching 이전 1 2 다음
