welcome!

참고문서: CLRS hash 해시의 작업은 INSERT, SEARCH, DELETE 로 나눌 수 있다. direct-address tables 직접 주소 테이블은, 어떤 값의 키 값을 직접적으로 테이블 키 값으로 활용하는 방법이다. T[x.key] = x # INSERT return T[x.key] # SEARCH T[x.key] = None # DELETE직접 주소 테이블은 주로 실제 값의 키를 활용하는데, 주요 작업에 대해 O(1) 시간복잡도에 동작할 수 있다. 이 경우, 값의 키를 직접 테이블 키로 저장하므로 연결될 값에는 키가 빠져도 된다. 직접 주소의 경우 같은 값을 여러 번 저장 하려면, 같은 인덱스에 대해 doubly linked list로 값을 저장하면, 삭제시에도 상수 시간으로 제거할 수..

하노이의 탑 하노이의 탑 이라는 문제는 일렬로 서있는 세 막대기 중 왼쪽 끝 막대기에 모든 원반들이 크기 순으로 꽂혀있고, 일정한 룰에 따라 그것을 전부 오른 쪽 끝 막대기로 이동하는 것을 묻는 문제이다. 아래는 하노이의 탑 사진 (wikipedia) 큰 원반이 항상 아래에 있어야 한다는 규칙을 준수하면서, 첫 번째 막대기에서 세 번째 막대기로 가는데에 가장 최단 수행 횟수가 존재할 거라 생각하는가? 만약 최단 수행이 존재한다면, 몇 번의 수행 만에 작업을 완료 할 수 있는가? 이에 대해 생각을 해볼 것이다. 하노이의 탑은 브라마의 탑이라고도 불리며 원래는 64개의 원반을 가지고 이동시키는 놀이로 부터 기원한다. 생각 step 1 처음부터 많은 수의 원반을 생각하지 말고 원반의 수를 줄여보자. 원반이 한..

FIsher-Yates Shuffle 순서를 정하는 문제에 직면하였을 때, 원소들을 어떻게 무작위적으로 배치하는가 생각이 들었다. 산업공학과 학부 시절에 가장 흥미가 있었던 분야가 통계/실험계획법이었기에, 랜덤/샘플링 이라는 단어만 들어도 그냥 재밌을것 같다. 현실 문제 만약 n 명의 사람이 있다. n 명의 사람을 일렬로 세우는데 순서를 무작위적으로 바꾸기 위한 알고리즘을 제시하라. 편향된 알고리즘 제시 이 이야기를 시작하기 전에 우선 편향된 알고리즘을 보여주려고 한다. n 개의 원소를 무작위로 셔플하는 naive approach #include #include #include #include #include using namespace std; vector ans; set s; int main() { ..

세그먼트 트리 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..

최단경로 문제와 벨만포드 알고리즘Shortest path Problem && Bellman-ford Algorithm (Label Correcting Algorithm)벨만의 1958년 연구 논문의 서론 부분이다. (RAND corp.) 두 번째 문단에서, " dynamic programming의 (함수 방정식 기법) 사용과 N-1번의 반복후에 수렴하는 반복적 알고리즘이 " 를 보자. 이게 바로 벨만-포드 알고리즘의 큰 핵심이다. Introduction 최단경로를 찾는 문제는 크게 두 종류로 나뉜다. 1 한 점에서 임의의 한 점(다른 모든 점) 까지의 최단경로를 찾는 문제2 모든 점 간의 최단경로를 찾는 문제 이 포스팅은 1번인 한 점에서 임의의 한 점 까지의 최단경로를 찾는 방법(알고리즘)에 대해서 포..

이 자료는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 글자에 대해 트라이 자료구조로 만들어 본것이다. 위키피디아에서 퍼왔다. 이렇게 트라이 자료구조를 만드는 것은 내가 저런 단어들을 가지고 있어요~ 라는 뜻과 같다. 우리가 구현할 트라이 자료구조는 위 그림과는 좀 다르다.차차 더 읽어가면 트라이 자료구조에..