코드 낙서장

세그먼트 트리 : latter2005.tistory.com/28?category=946518 [자료구조] 세그먼트 트리 자료구조 설명 : www.acmicpc.net/blog/view/9 세그먼트 트리 (Segment Tree) 문제 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제를 생각해봅시다. 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A.. latter2005.tistory.com 세그먼트 트리에서 자주 업데이트가 발생할 때 이를 더욱 효율적으로 처리하기 위한 알고리즘입니다. 간단하게 설명하자면 구간 a~b의 값을 변경할 때 모든 트리구조, 배열을 변경하지 않고 접근 시 차근차근 변경해 나가겠다는 의미입니다. 예시를 들어 설명하도록 하겠습니다. ary = {0, 1,..

자료구조 설명 : www.acmicpc.net/blog/view/9 세그먼트 트리 (Segment Tree) 문제 배열 A가 있고, 여기서 다음과 같은 두 연산을 수행해야하는 문제를 생각해봅시다. 구간 l, r (l ≤ r)이 주어졌을 때, A[l] + A[l+1] + ... + A[r-1] + A[r]을 구해서 출력하기 i번째 수를 v로 바꾸기. A[i www.acmicpc.net 백준 사이트에서 설명을 잘해 두었습니다. 배열에서 부분합, 부분 최대/최소 등 범위 참조 연산이 자주 일어날 때 자주 사용하는 자료구조입니다. 미리 배열에 대하여 세그먼트 트리를 생성해 둔 후 미리 계산해둔 값을 참고하여 O(n)의 시간을 O(log n) 만큼으로 줄여줍니다. 일반적으로 세그먼트 트리에서 노드들은 다음과 같은..

위키피디아 : ko.wikipedia.org/wiki/%EC%9D%B4%ED%95%AD_%ED%9E%99 이항 힙 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 둘러보기로 가기 검색하러 가기 이항 힙에 대해 설명한다. 컴퓨터 과학 분야에서는 이항힙(binomial heap)은 이진힙(binary heap)과 유사하지만, 이항힙(binomial heap)이 ko.wikipedia.org 이항 트리 시각화 사이트 : www.cs.usfca.edu/~galles/visualization/BinomialQueue.html Binomial Queue Visualization www.cs.usfca.edu 이항 힙은 이항 트리가 결합된 구조로 이루어져 있으며 n차수의 이항 트리는 2개의 n-..