Computer Science/자료구조 (11) 썸네일형 리스트형 Graphs 1. Definition and terms Graph (V, E)는 set of vertices V와 set of edges E로 이루어져 있다. vertex는 하나의 node 점을 의미하고, edge는 vertex끼리 이어진 선을 의미한다. # of Vertices는 |V| # of Edges는 |E| 이다. Path : Vertices의 sequence와 n-1개의 edge로 이뤄진 집합을 의미한다. simple path : Path를 이루는 모든 vertices가 distinct한 것을 뜻한다. Cycle : $v_1$에서 시작하여 자기 자신으로 돌아오는 길이가 3 이상인 path를 뜻한다. Simple Cycle : 처음과 끝을 제외하고 모든 vertices가 distinct한 것을 뜻한다. Co.. Searching 1. Searching Ordered Arrays 만약 element가 정렬되어 있지 않다면, linear search($\Theta(n)$)가 가장 최선의 선택지이다. 정렬이 되어 있다면 Binary Search($\Theta(log n)$)이 linear search보다 낫다. 하지만 우리가 사전에 데이터의 분포와 사용 패턴을 알고 있다면 Binary Search보다도 더 좋은 Search Algorithm을 찾을 수 있다. 1-1. Jump Search k의 범위를 두고, L[0], L[k-1], L[2k-1]...을 순차적으로 방문하며 해당 값이 찾고자 하는 값 K보다 큰지 작은지를 검사한다. 해당 값이 K보다 크다면 계속해서 jump search를 진행하고 아니라면 이전의 값으로 돌아가 Line.. Internal Sorting 각각의 sorting algorithm을 비교하기 위해 # of comparison, # of swap을 기준으로 삼는다. 1. $\Theta(n^2)$ Sorting Algorithms 1-1. Insertion Sort (1) 초기에 output은 비어있다. (2) 각각의 item을 알맞은 장소에 삽입한다. static Non-Binary Tree(General Tree) 1. General Tree 1-1. Definition & Terms 노드가 child를 0 또는 1개 이상으로 가질 수 있는 tree를 뜻한다. 기본적인 term(root, parent, subtree..)들은 binary tree와 동일하다. 1-2 Preorder Traversal general tree에서도 똑같이 동작한다. Root - 1st left subtree - 2nd subtree - ... - nth subtree로 방문 static void preorder(GTNode rt){ PrintNode(rt); if(!rt.isLeaf()){ GTNode temp = rt.leftmostChild(); while(temp != null){ preorder(temp); temp = temp.. List, Stacks, and Queues 1. List 1-1. 정의 유한하고, 순서가 정해져있는 자료구조 List의 element는 위치가 정해져있다. 1-2. Implementation concept current position의 컨셉을 가지고 있다. Operation은 curr_pos에 근거해서 일어나게 된다. 1-3. Array-based List : array를 이용하여 만든 list 장점 : 설치하기/이해하기 쉽다. 빠르게 특정 위치의 element에 접근하기 쉽다. access만 하고 insert나 remove가 안되는 application의 경우 Linked list에 비해 빠르다. linked list에 비해 메모리를 적게 쓸 수도 있다.(pointer를 저장할 필요가 없기 때문에) 약점: insert와 remove에 Θ(n).. Huffman tree 1. Huffman Coding Trees 1-1. 문제 상황 ASCII codes : 문자 하나당 8bit가 사용되는 크기가 고정된 코딩방법 자주 사용하는 문자를 더 적은 수의 비트로 코딩하면 공간을 줄일 수 있다. variable-length coding : 문자별로 길이를 다르게 하는 코딩 목표 : external path weight이 최소가 되는 binary tree를 구하는 것 weighted path length of a leaf : weight $\times$ (depth of the leaf) external path weight = weighted path length의 합 1-2. Huffman tree 생성 과정 1) frequency 중에서 가장 작은 것 두개를 찾는다. 2) 그 .. Priority Queue & Heap 1. Priority Queue 1.1 문제 상황 삽입은 자유롭게 이루어지지만, element를 꺼낼 때 항상 가장 큰 element(removemax)를 꺼내고자 한다면 가장 좋은 자료구조는 무엇인가? ex) multi-tasking operating system에서 scheduling job하는 문제! 1.2 Unsorted array or linked list insert : O(1)의 시간 소요 removemax : max인 element를 찾기 위해 O(n)의 시간 소요 1.3 Sorted array of linked list insert : O(n)의 시간 소요, sorting을 위해 removemax : 맨끝 값을 return하면 되니까 O(1) 하지만 이때 heap 자료구조를 사용하게 되면.. Binary Tree(이진 트리), Binary Search Tree(이진탐색트리) 1. Binary Tree 1-1. 정의 유한개의 노드로 이루어진 트리이다. 이진 트리는 root(노드)와 그와 이어진 두개의 이진트리들로 구성된다.(이를 각각 left, right subtree로 칭한다.) 1-2. 용어 (1) node : 이진 트리를 구성하는 단위 value를 저장하는 공간과 왼쪽과 오른쪽을 노드를 가르치는 포인터로 구성된다. (2) children : root 노드의 왼쪽과 오른쪽이 가리키는 node를 child라 한다. (3) edge : root들을 잇는 선분 (4) ancestor : children의 반대 (5) descendant : 밑의 노드들 (6) path : 이웃하는 두 노드가 앞이 부모, 뒤가 자식인 노드의 열 (7) level(=depth) : 루트 노드에서 자.. 이전 1 2 다음
