Eunbi

펜윅 트리 누적합을 구한다. → 누적합을 이용하면 구간합도 구할 수 있음. 세그먼트 트리와 다르게 추가적인 공간(tree)이 필요없다. 만약 1~13번째 데이터의 구간합을 구하고 싶다면... 8, 12, 13번 값을 알면됨. 8 : 1~8까지의 값 12 : 9~12까지의 값 13 : 13의 값 LSB(Least Significant Bit) Index 정의하기 i 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 binary 0001 0010 0011 0100 - - - - - - - - - - - - LSB index 1 2 1 4 - - - - - - - - - - - - 저 칸수만큼 나를 기준으로 왼쪽을 커버. LSB 구하기 : v&-v 기존 이진수와 2의 보수를 and 연산하면..

합동식의 성질 백준 1837 유클리드 호제법 확장 유클리드 호제법 에라토스테네스의 체 수의 범위 N이 있을 때, 한 수를 두 가지 수로 곱하는 쌍의 개수는 $\sqrt{n}$ 이다. 즉, 시간복잡도는 $O(\sqrt{N}/\ln{\sqrt{N}})$ 백준 6588

트리 Tree 트리의 조건 : 1개 이상의 노드를 갖는 집합(그래프) + cycle이 없다. 노드 N, 간선 M cycle : 간선이 $N-1$ 일 때, 사이클이 없다. cycle이 존재하지 않는다 = 우회도로가 없다 = 경로가 하나뿐이다. 이진 트리 Binary Tree 트리의 분지 수가 2 이하인 트리. 트리의 분지 수 : 트리 내의 모든 노드의 차식 차수 중 가장 큰값을 나타냄. => 즉, 자식을 최대 2개 가질 수 있다. 높이가 $H$일 때, 노드의 최대 개수는 $2^H-1$이다. 힙 Heap 완전 이진트리 형태 힙 조건 (Heap condition) 만족 max heap : 모든 노드들은 자식 노드보다 큰 값을 가진다. (루트노드가 가장 큰 값) min heap : 모든 노드들은 자식 노드보다 ..

https://cplusplus.com/reference/algorithm/sort/ sort Sorts the elements in the range [first,last) into ascending order. first를 포함하여 last 전까지 범위의 요소에 대해 ascending, 오름차순을 따르도록 정렬한다. The elements are compared using operator< for the first version, and comp for the second. template1에서는 연산자 &#39;