공대생 정리노트

Binary Search Trees(BST) Property: 노드의 left subtree에 있는 원소들의 value는 노드의 value보다 작다. 노드의 right subtree에 있는 원소들의 value는 노드의 value보다 크다. BST의 Operation 1. Check BST 어떠한 노드에 대해서 left subtree의 모든 원소들의 value들은 노드의 value보다 작아야 하고, right subtree의 모든 원소들의 value들은 노드의 value보다 커야한다. 이를 확인하기 위해서 upper bound와 lower bound를 설정한다. left subtree의 upper bound는 노드의 value보다 1 작은 값이고, right subtree의 lower bound는 노드의 ..

Dictionary Concepts : 우리가 원하는 내용을 찾기 위하여 key를 검색한다. Key comparison : key값을 비교하여 같은 key 값을 가진 value를 가져온다. Records and Keys : key를 record와 별도로 저장을 한다. (key, record) pair 형태로 가지고 잇으며 이를 (key, value) pair라고도 부른다. Sorted vs Unsorted Array List Dictionaries list가 key 값으로 sorted가 되어 있을 때 : binary search를 이용하여 key 값을 검색할 때 빠르게 검색할 수 있다. O(logn) 그러나 새로운 (key, value)값을 insert할 때 순서에 맞춰서 insert를 해야하기에 느리다..

Queues FIFO : First in, First out Stack은 LIFO였다면 반대로 Queues는 먼저 들어온 element가 먼저 나간다. 기본 Notation은 다음과 같다. Enqueue : element를 Queue의 끝부분에 추가한다. Dequeue : Queue에 있는 element들 중 가장 오래전에 추가된(가장 앞에 있는) element를 제거한다. Front : 가장 앞에 있는 element를 반환한다. Rear : 가장 뒤에 있는 element를 반환한다. Array based Queue Array를 base로하면 circular queue를 base로 한다. 그냥 단순히 Array로 Queue를 만들게 되면 element들을 추가했다 제거했다 하면서 Array의 앞부분이 비..

Full binary tree 각각의 node가 leaf(자식이 없는 노드)이거나 두 개의 자식을 가지고 있는 internal node인 tree. Complete binary tree 마지막 level을 제외한 모든 level이 완전히 차있어야(full) 한다. 가장 마지막 level은 모든 노드들이 왼쪽부터 채워져 있어야 한다. Full Binary Tree Theorem (1) non empty full binary tree의 leaves 수는 internal node의 개수보다 1개 더 많다. Mathematical Induction을 이용하면 쉽게 증명이 가능하다. 위 theorem을 이용하면 non-empty tree에 대해서 null pointer의 개수가 tree의 node 개수보다 1개 ..

Doubly Linked Lists Linked List의 한계점 : prev()를 하면 O(n) 시간이 걸린다. -> pointer를 두 개 만들자! 기존의 Linked List에서는 head만 null을 가지고 있었지만, Doubly Linked Lists는 tail도 null이다. tail이 있으면 boundary condition을 check하는데 편하다(코딩하기 편하다). 단점으로는 additional storage를 사용하게 된다. Stacks LIFO : Last In, First Out -> 최근에 추가된 element가 제거될때 먼저 제거된다. 기본적인 Notation은 PUSH, POP, TOP이 있다. PUSH : element 하나를 추가한다. POP : stack에 있는 eleme..

Array-Based List Insert : inefficient in Array. O(n) Array-Based List에서 insert 함수와 Remove 함수는 for문을 사용하므로 O(n)이 걸린다. Array Based List 장점 : 1. element의 위치를 안다면 O(1) 시간에 acccess 할 수 있다. 2. 프로그래밍하기 쉽다(배열 사용) 단점 : 1. input size가 Array size(max size) 넘어가면 extra work가 필요하다. 2. insert가 worst case의 경우 O(n)이 걸리고 best case의 경우 O(1)이 걸리는데 gap이 너무 크다. remove도 마찬가지. Space : list size가 max size(Array size)와 비..