welcome!

세그먼트 트리 with Lazy PropagationIntroduction만약 문제를 풀 때 구간 질의와 관련된 문제에서 naive한 방법 또는 잘 알려진 prefix 계열의 접근으로도 풀 수 없는 것이 있다면, 한 번쯤 생각해볼 방법은 세그먼트 트리이다.세그먼트 트리는 구간에 대해 분할 해놓은 정보들을 담고 있는 트리이다. 루트노드는 [0 ... n-1] 구간에 대한 특정 연산 결과가 담겨있고. 그 자식 노드는 [0 ... (n-1)/2], [(n-1)/2+1 ... n-1] 구간에 대한 특정 연산 결과가 담겨있다. 이는 초기화 단계 init 에서 수행된다.이러한 트리는 분할정복을 따르며, 재귀적으로 파고 들어가 자식노드의 결과값을 부모노드가 받고 또 그 결과를 재사용하기 때문에 납득할 만한 초기화 수..

/*The source of this article is from1 Geeks For Geeks (https://www.geeksforgeeks.org/avl-tree-set-1-insertion/) 2 Wikipedia (https://en.wikipedia.org/wiki/AVL_tree)*/AVL tree의 생성과 삽입, 순회에 대해 이번 시간에는 AVL Tree에 대한 개론과 생성과 삽입, 순회에 대한 구현을 말하려고 한다. 개요AVL Tree는 BST의 일종이다. BST는 Binary Search Tree이며 원어 뜻 그대로 Search 하는데에 특화된 Tree이며, 거기에 더해 삽입, 삭제 등을 하는데에 효율적으로 설계 되어있다. naive 한 이진검색트리에 대해서 이전 포스트에서 이미 다루었..

/*This article is from 1 youtube ( https://www.youtube.com/watch?v=aZjYr87r1b8 )2 wikipedia3 geeks for geeks4 introduction to algorihtm5 bunch of website, blog6 Rosetta code*/ B+ trees B+ trees 는 balanced n - ary search Tree 의 일종이다. n - ary Tree는 말 그대로 한 노드가 자신의 자식노드를 최대 n 개 까지 가질 수 있는 트리이다. 이 때, Search Tree 이므로 각 노드들의 자식 - 부모 관계는 그 노드의 키에 의해 결정된다. Binary Search Tree 가 최대 2개의 자식을 가지는 Bin - ary 이..

/* The source of this article is from 1 Wikipedia (https://en.wikipedia.org/wiki/Binary_search_tree) 2 Geeks for Geeks (https://www.geeksforgeeks.org/binary-search-tree-set-1-search-and-insertion/) 3 Introduction to algorithm 3rd edition 4 Handbook of discrete and combinatorial mathematics. I just write down this post for my learning in CS. I don't have any authority for comercial uses with this..

이 자료는Thomas H. Cormen, Charles E. Leiserson의 introduction to algorithms과 Kenneth H. Rosen 의 Handbook of discrete and combinatorial mathematics의 자료 일부를 번역하고 그 외 여러 wikipedia 자료들을 통합해서 작성된 것입니다.개인의 이윤을 위해서 작성한 것이 아니며 스스로의 학습용 및 정보 공유 용으로 작성했습니다. Introduction of Heap sort이번 포스트에서는, heap sort를 소개하고자 한다. heap sort의 수행복잡도는 O(nlog n)이다.머지 소트나 퀵소트는 sorts in place가 아니지만,힙 정렬은 삽입정렬과 마찬가지로 sorts in place이다..

Trie Introduction트라이는 자료를 찾는데 특화된 자료 구조이다. 트라이(Trie)의 어원은 retrieval (찾는다)의 중간글자 trie에서 유래되었다.트라이 자료구조는 종종 radix tree, prefix tree라고도 불린다. 앞 문자를 기준으로 차차 트리의 자식 vertex로 한글자씩 진행해 나가기 때문이다. 잘 이해하지 못 해도 다음 그림을 보면 이해할 수 있다.아래의 그림은 to, tea, ted, ten, a, in, inn 7 글자에 대해 트라이 자료구조로 만들어 본것이다. 위키피디아에서 퍼왔다. 이렇게 트라이 자료구조를 만드는 것은 내가 저런 단어들을 가지고 있어요~ 라는 뜻과 같다. 우리가 구현할 트라이 자료구조는 위 그림과는 좀 다르다.차차 더 읽어가면 트라이 자료구조에..