인프런에서 권오흠 교수님의 알고리즘 강좌를 듣고 필기한 내용이다.수강한 파트는 Red-black Tree이다.강의 분량이 많아서 Delete 부분은 다음에 수강할 예정이다. BST의 일종Balanced BST -> 높이가 O(logn)Search, Insert, Delete 연산을 최악의 경우에도 O(logn) 시간에 지원-----------------------------------------------------------------------------각 노드 -> key, left, right, parent 의 주소를 저장자식노드가 존재하지 않을 경우, NIL 노드라고 부르는 특수한 노드가 있다고 가정따라서 모든 리프노드는 NIL 노드루트의 부모도 NIL노드라고 가정노드들은 내부노드와 NIL 노드..
인프런에서 권오흠 교수님의 알고리즘 강좌를 듣고 필기한 내용이다.수강한 파트는 Recursion이다. Recursion이 무한 루프에 빠지지 않으려면..1. Base case : 적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다.2. Recursvie case : recursion을 반복하다보면 결국 base case로 수렴해야 한다. ex)public class Code02{ public static void main(String[] args){ int n = 4; func(n); }} public static void func(int k){ if (k
오늘은 자료구조에 대한 인강 중 recursion에 대한 강의를 듣고, 배운 내용을 필기해 보려고 한다.
인프런에서 권오흠 교수님의 알고리즘 강좌를 듣고 필기한 내용이다.수강한 파트는 Hashing이다. 해쉬 테이블은 dynamic set을 구현하는 효과적인 방법의 하나- 적절한 가정하에서 평균 탐색, 삽입, 삭제 시간 O(1)- 보통 최악의 경우 theta(n) 해쉬 테이블이란- 해쉬 함수(hash function) h를 사용하여 키 k를 T[h(k)]에 저장 - h : U -> {0, 1, ..., m-1} 여기서 m은 테이블의 크기, U는 모든 가능한 키들의 집합 (U의 예 -> 모든 자연수의 집합) - 키 k가 h(k)로 해슁되었다고 한다. - 해쉬 테이블은 일반적으로 하나의 배열 - index = h(k) : 즉, 각 키에 대한 해쉬함수 값을 그 키를 저장할 배열 인덱스로 사용함 해쉬 함수의 예- ..
오늘은 자료구조에 대한 인강 중 hasing에 대한 강의를 듣고, 배운 내용을 필기해 보려고 한다.
오늘은 파이썬을 이용한 그룹 채팅 프로그램을 구현해볼 예정이다.
Red Black Tree를 c++, java로 구현하였다.빡세게 이해하다가 제때 포스팅 하는 것을 까먹어버렸다. 자바 -> https://github.com/khe0613/AlgorithmStudy/blob/master/src/main/java/data_structure/RBTree.javac++ -> https://github.com/khe0613/AlgorithmStudy/blob/master/src/cpp/data_structure/rbt.cpp코드는 위의 링크에 올려두었다. 수업때 레드 블랙 트리를 배운적이 없어, 구글링을 통해 이해하려니 쉽지 않았다.현재는 외국 알고리즘 사이트에서 코드를 이해하며 따라친 수준인데,인프런에서 레드 블랙 트리를 설명하는 강의를 찾게 되었다. 강의를 듣고 이해한 뒤..
self-balancing Binary Search Tree(BST) 에는 대표적으로 AVL Tree와 Red Black Tree 가 있다. AVL Tree -> | left 서브트리의 height - right 서브트리의 height |가 1이하인 트리 AVL Tree의 예 AVL Tree가 아닌 예 AVL Tree를 구현하는 이유대부분의 BST operations (e.g., search, max, min, insert, delete.. etc)는 O(h)의 시간이 소요된다. (h는 BST의 높이로 logn 정도)그러나, BST가 skewed Binary tree가 될 경우, O(n)의 시간이 소요될 수가 있다.따라서 left, right 서브트리의 height에 balance를 맞춰 O(logn)의..