Microsoft PowerPoint - Chap5 [호환 모드]
|
|
|
- 서천 구
- 6 years ago
- Views:
Transcription
1 5.3 Binary Tree Traversal Tree 의각 node 를한번씩방문하는알고리즘 각 node 와그 node 의 subtree 들을동등하게취급하면 6 개의 traversal 조합이있다. (L: Left 로움직임, V: 노드를 visiting, R: Right 로움직임 ) (1) LVR, (2) LRV, (3) VLR, (4) VRL, (5) RVL, (6) RLV Traverse left before right 를도입하면, 3 개의조합이남는다. (1) LVR (in-order traversal) (2) LRV (post-order traversal) (3) VLR (pre-order traversal) 3 개의 tree traversal 과 expression 의 (1) infix, (2) postfix, (3) prefix form 간에상호관련이있음. 23
2 In-order Traversals: 왼쪽 branch 를모두방문한후, node 를방문하고, 오른쪽 branch 를방문함 주어진식 : 16 + A / B * C * D + E (infix form) 12 * 18 E 번호는아래알고리즘의수행순서이므로방문순서임 8 * D void inorder(tree_ptr ptr) { 4 / if(ptr) { C inorder(ptr->left_child); printf( %d,ptr->data); 2 A 6 B 9 11 inorder(ptr->right_child); inorder() 는총 19번 call되었다. Figure 5.8: Binary tree with arithmetic expression 식의출력 : A/B*C*D+E - 주어진 infix form 과동일 24
3 Pre-order Traversals: node 를방문하고, 왼쪽 branch 를모두방문한후, 오른쪽 branch 를방문함 주어진식 : 1 + A / B * C * D + E (infix form) 2 * 17 E 번호는아래알고리즘의수행순서이므로방문순서임 3 * D void preorder(tree_ptr ptr) { 4 / if(ptr) { C printf( %d,ptr->data); preorder(ptr->left_child); 5 A preorder(ptr->right_child); B preorder() 는총 19번 call되었다. Figure 5.8: Binary tree with arithmetic expression 식의출력 : +**/ABCDE 25
4 Post-order Traversals: 왼쪽 branch 를모두방문한후, 오른쪽 branch 를방문한후, node 를방문함 주어진식 : 19 + A / B * C * D + E (infix form) 15 * 18 E 번호는아래알고리즘의수행순서이므로방문순서임 11 * D void postorder(tree_ptr ptr) { 7 if(ptr) { / 10 C preorder(ptr->left_child); 3 A 6 B preorder(ptr->right_child); 8 9 printf( %d,ptr->data); postorder() 는총 19번 call되었다. Figure 5.8: Binary tree with arithmetic expression 식의출력 : AB/C*D*E+ 26
5 Iterative In-order Traversal Recursive version의 system stack을모방하기위해 stack에대한삽입, 삭제연산을수행 void iter_inorder(tree-pointer node) { int top = -1; // 스택초기화 tree_ptr stack[max_stack_size]; while (1) { while (node) { push(&top, node); // 스택에넣음 node = node->left_child; node = pop(&top); if (!node) break; printf( %d, node->data); node = node->right_child; // 스택에서꺼냄 // 빈스택임 < 분석 > Tree 에있는모든 node 가 stack 에 add 되었다가 delete 된다. delete 될때만처리되므로, tree 의 node 수가 n 이라면 time complexity 는 O(n) 이다. space requirement 는 tree 의 depth 와같으므로평균, O(log n), 최악의경우 O(n) 이다. < 유사응용 > Factorial, Fibonacci 숫자, 트리순회, 이진탐색, 하노이타워, quick sort, 등등 27
6 Level Order Traversal 아래그림의 sequential node number 에근거한항해방법으로서 queue 를이용한다 순회결과 : Figure 5.8 의경우 : +*E*D/CAB 3 7 void level_order(tree_ptr ptr) { int front = rear = 0; tree_ptr queue[max_queue_size]; if (!ptr) return; addq(front,&rear,ptr); while (1) { ptr = deleteq(&front, rear); if (ptr) { printf( %d, ptr->data); if (ptr->left_child) addq(front,&rear,ptr- >left_child); if (ptr->right_child) addq(front,&rear,ptr- >right_child); else break; 28
7 ( 참고 ) 5.4 이진트리의추가연산 (1) Copying Binary Trees (Program 5.6: post-order 항해법을약간변형함 ) tree_ptr copy(tree_ptr original) { tree_ptr temp; if (original) { temp = (tree_ptr)malloc(sizeof(node)); if (IS_FULL(temp)) exit(1); temp->left_child = copy(original->left_child); temp->right_child = copy(original->right_child); temp->data = original->data; return temp; return NULL; 29
8 ( 참고 ) 5.4 이진트리의추가연산 (2) Testing for Equality of Binary Trees 2 개의 binary tree 가 같은구조 와 같은정보 를담고있는지를확인한다. 다음 program 5.7 은 pre-order traversal 에대한약간의변형이다. int equal(tree_ptr first,tree_ptr second) { return ( (!first &&!second) (first && second && (first->data == second->data) && equal (first->left_child, second->left_child) && equal (first->right_child, second->right_child ) ); 30
9 5.5 Threaded Binary Trees Thread : Needless Null link 대신, tree 의다른노드를가리키는용도로사용 A.J. Perlis 와 C. Thorntorn 에의해제안된방법이다. 왜 Thread 를사용하는가? Binary tree 에서 2n 개의 link 들중, leaf 의 n+1 개의 link 가 null link 를이용함 node 당 2 개의 link 가있고, 사용되는 link 의수가, n-1 이므로, null link 는 n+1 개 (1) null link 가너무많다 null link 를다른좋은일에사용할수없을까? 공간이아까우니, 이공간을활용하자. (2) 임의단말노드의바로앞노드 (previous node) 와뒷노드 (successor node) 순서를알기힘들기때문에 thread 를이용하자. Thread 구성규칙 1. 한 node 의 left-child 가 null 이면, 그값이 in-order traversal 에의해현 node 바로전에방문되는 node 를가리킨다. ( 현 node 의 in-order predecessor 를가리킴 ) 2. 한 node 의 right-child 가 null 이면그값이 in-order traversal 에의해현 node 바로뒤에방문되는 node 를가리킨다. ( 현 node 의 in-order successor 를가리킴 ) 31
10 A B C D E F G H I Figure 5.9 Threaded tree corresponding to Figure 5.6 (b) - In-order traversal: H, D, I, B, E, A, F, C, G - E 의 left child 가 null 이므로 E 의 left child 가 predecessor B 를가리킴 - E 의 right child 가 null 이므로 E 의 right child 가 successor A 를가리킴 32
11 실제포인터와스레드를어떻게구분하나? thread 와 normal pointer 를구분하기위해다음두개의 field 를추가함 : (1) left_thread, (2) right_thread (ß 실제로는, 각기한 bit 면된다 ) 예제 : if ( ptr->left_thread = TRUE ) ptr->left_child 는 thread 이다. if ( ptr->left_thread = FALSE ) ptr->left_child 는 left child node 에대한 ptr. right_thread 도동일 dangling reference 방지를위해모든 threaded binary tree 는 head node (dummy root) 를유지한다. 따라서 empty threaded binary tree 도하나의 node 를가진다. Figure 5.10 과같이 root->left_child 는실제 tree 의첫 node 를가리킨다. 33
12 Figure 5.10 (a) empty threaded tree typedef struct threaded_tree * threaded_ptr; typedef struct threaded_tree { short int left_thread; threaded_ptr left_child; char data; threaded_ptr right_child; short int right_thread; ; left_thread left_child data right_child right_thread 34
13 Figure 5.10 (b) Memory representation of the threaded tree root f -- f f A f f B f f C f f D f t E t t F t t G t t H t t I t f: FALSE t: TRUE 35
14 In-order Traversal of a Threaded Binary Tree 일반적으로이미방문했던노드 (already visited node) 이지만, 다음에사용해야하는 node 를 keeping 하는방법으로 stack 을이용한다. 그러나, stack 을사용하지않고도 threaded tree 의 thread 를이용하여 inorder traversal 수행하여다음노드를알수있다. ptr 노드의 in-order 순뒷노드를찾아보자. 만약 ptr->right_thread=true 면, ptr->right_child ( 다음을위해서, 따라간다 ) 그렇지않으면 (ptr->right_thread=false 면 ), 우측노드 (right node) 의좌측노드 (left_thread 에 TRUE 가나타날때까지 ) 를계속따라간다. void tinorder (threaded_ptr tree) { threaded_ptr temp = tree; for (;;) { temp = insucc (temp); if (temp = tree) break; printf( %3c, temp->data); threaded_ptr insucc (threaded_ptr tree) { threaded_ptr temp; temp = tree à right_child; if (!tree à right_thread) /* 오른쪽 FALSE */ while (!temp à left_thread) /* 왼쪽 FALSE */ temp = temp->left_child; return temp; - Insucc () 를계속호출하면됨 임의노드의 inorder - 시간복잡도 : O(n), n은노드수 successor를찾는루틴 36
15 Threaded binary tree 에노드삽입 오른쪽 subtree 가없는 parent 에서오른쪽에 child 를만들어보자. 1) parent->right_thread를 FALSE로만듦 2) child->left_thread, child->right_thread를 TRUE로만듦 3) child->left_child가 parent를가리키게한다. 4) child->right_child가 parent->right_child 값을가짐 5) parent->right_child가 child를가리킴 parent 가 right child 를가지고있으면, 그 child 는 parent 의 inorder successor 노드가된다. 당연히, 역으로 parent 는그 child 의 in-order predecessor 가된다. 37
16 Figure 5.10 부모노드에새로운노드를오른쪽자식으로삽입하는알고리즘 void insert_right(threaded_ptr parent, threaded_ptr child) { threaded_ptr temp; child->right_child=parent->right_child; child->right_thread=parent->right_thread; child->left_child=parent; child->left_thread=true; parent->right_child=child; parent->right_thread=false; if(!child->right_thread) { temp=insucc(child); temp->left_child=child; 38
17 삽입예 : Threaded Binary Trees root root A A parent B parent B C D child C D child 삽입전 삽입후 : 붉은선 Young-Ho Park
18 삽입예 : Threaded Binary Trees root root A parent A parent B B child C D C X E F D child X E F before After: 붉은선 Young-Ho Park
19 The Heap Abstract Data Type 5.6 Heaps Definition: max tree 는 node 에있는 key value 가그 children 의 key value 들보다크거나같다. max heap 은 complete binary tree 이면서동시에 max tree 이다. Max Heap 예제들 :: [1] 14 [1] 9 [1] 30 [2] [3] 12 7 [2] [3] 6 3 [2] 25 [4] [5] [6] [4] 5 41
20 The Heap Abstract Data Type ( 계속 ) Definition: min tree 는 node 에있는 key value 가그 children 의 key value 들보다작거나같다. main heap 은 complete binary tree 이면서동시에 main tree 이다. Min Heap 예제들 :: [1] 2 [1] 10 [1] 11 [2] [3] 7 4 [2] [3] [2] 21 [4] [5] [6] [4] 50 heap 은 array 로표현할수있고, 이경우 Lemma 5.3 에근거한 addressing scheme 을사용할수있다. 42
21 Abstract data type MaxHeap structure MaxHeap is object: 각노드에있는값이그자식들의값보다큰노드들로구성된 0 이상의 element 들을가진 complete binary tree functions: for all heap MaxHeap, item Element, n, max_size integer MaxHeap Create (max_size) ::= 최대크기의 element들의최대값을가지고있는 빈 heap을만든다. Boolean HeapFull (heap,n) ::= if (n==max_size) return TRUE else return FALSE Maxheap Insert (heap, item, n) ::= if (!HeapFull (heap,n)) insert item into heap and return the resulting heap else return error Boolean HeapEmpty (heap,n) ::= if (n>0) return FALSE else return TRUE Maxheap Delete (heap, n) ::= if (!HeapEmpty(heap,n)) 힙에서가장큰것을반환한다. 그리고, 그것을힙에서제거한다. else return error 43
22 5.6.2 Priority Queues heap 은 priority queue 의구현에적합하다. priority queue 에대한연산은? 가장높은 priority 를가진 element 를삭제하고, 임의의 priority 를가진 element 를삽입하는연산이대부분이다. OS 의 job scheduling 시 priority queue 를이용한다. priority queue 를구현하는여러가지방법들 :: 표현방법삽입삭제 순서없는배열 Q (1) Q (n) 순서없는연결리스트 Q (1) Q (n) 정렬된배열 O(n) Q (1) 정렬된연결리스트 O(n) Q (1) 최대힙 O(log 2 n) O(log 2 n) 44
23 priority queue 를구현하는여러가지방법들 ( 보완 ) 1. array 간단함 insertion : array 끝에추가 O(1) deletion : 가장큰값을검색후 element를삭제하고 O(n) array elements를 shift함 O(n) 2. un-ordered linked list insertion : chain 끝에추가 O(1) deletion : 가장큰값을검색후한 element를삭제 O(n) 3. ordered array insertion : 해당위치검색후 O(n) array element shift O(n) deletion : 정해진위치의 element을삭제 O(1) 4. linked list (non-increasing order) insertion : 해당위치검색후삽입 O(n) deletion : link의 header element을삭제 O(1) 5. heap insertion : O(log₂n) deletion : O(log₂n) 45
24 5.6.3 Insertion into a Max Heap 넣는노드위치 (complete tree 구성순서 ) 로부터 parent 로계속올라간다. 링크표현 : 각노드구조에는 parent 를가리키는 field 가있어야한다. 배열표현 : 힙은 complete binary tree 이므로, Lemma 5.3 에서소개한바와같이, 간단한주소방법인 배열 을사용하는것이적합하다. [1] 20 [1] 20 [1] 20 [1] 21 [2] [3] 15 [4] [5] [2] [3] 15 [4] [5] [6] [2] [3] 15 [4] [5] [6] [2] 15 [3] 20 [4] [5] [6] (a) 삽입전힙 (b) 새노드의초기위치 (c) 힙 (a) 에 5 삽입 (d) 힙 (a) 에 21 을삽입 46
25 5.6.3 Insertion into a Max Heap ( 계속, Program 5.11) heap 이 complete binary tree 이므로 array representation 이용 Lemma 5.3 을이용하면노드별배열매핑주소 (location) 를파악할수있다. Lemma 5.3 을이용하기위해 array 의 index 를 0 이아닌 1 부터사용 알고리즘 :: 삽입될노드의위치를지정함 : 가장밑에가장오른쪽단말노드 새로운키값을넣는다. parent 를통해계속루트방향으로올라가면서키값들을조정한다. : i/2 시간복잡도 : O( 트리의깊이 ) O(log 2 n) void insert_max_heap(element item, int *n) { int i; if (HEAP_FULL(*n)) { fprintf(stderr, The heap is full. \n ); exit(1); i = ++(*n); while ((i!=1 )&& (item.key > heap[i/2].key)) { heap[i] = heap[i/2]; i /= 2; heap[i] = item; 47
26 5.6.4 Deletion from a Max Heap 항상, 힙의루트에서자료를제거하면된다. 자료제거후, 완전이진트리가되도록트리를재조정한다. 가장마지막에있는노드를루트에놓고, 루트로부터그자식노드들을비교하면서힙의정의에맞도록노드들을조정하면서트리를아래방향으로 scanning 한다. 시간복잡도 : O( 트리깊이 ) à O(log2n) 48
27 Heaps [1] 20 [1] 20 removed [2] [3] 15 2 [2] [3] 15 2 [4] [5] [4] [5] (a) 힙구조 [1] 10 [1] 15 [2] [3] 15 2 [2] [3] 14 2 [4] 14 [4] 10 (b) 루트에 10 을넣기 (c) 최종힙구조 Young-Ho Park
28 element delete_max_heap (int *n) { element item, temp; if (HEAP_EMPTY(*n)) { fprintf(stderr, 힙 is empty\n ); exit(1); item = heap[1]; temp = heap[(*n)--]; parent = 1; child = 2; while (child <= *n) { /* 왼쪽과오른쪽자식의키값을비교 */ if ((child < *n) && (heap[child].key < heap[child+1].key)) child++; if (temp.key >= heap[child].key) break; /* move to the next lower level */ heap[parent] = heap[child]; parent = child; child *= 2; heap[parent] = temp; return item; Analysis heap 을따라내려가면서 parent 와 child node 를비교하면서 heap 을재정립 heap 의높이가 log 2 (n+1) 이므로 complexity 는 O(log 2 n) 이다. 50
29 5.7 Binary Search Trees Definition: Binary Search Tree 는탐색에목적을둔 binary tree 이다. 본 tree 는 empty 일수있고, empty 가아닌경우다음의성질을만족한다. 1. 모든 element 는서로다른 key 를갖는다. 2. Non-empty left subtree 에있는 key 들은 root 의 key 보다작은값을갖는다. 3. Non-empty right subtree 에있는 key 들은 root 의 key 보다큰값을갖는다. 4. left subtree 와 right subtree 도역시 binary search tree 이다 (a) 이진탐색트리가아님 (b) 이진탐색트리 Figure 5.12: Binary Trees (c) 이진탐색트리 51
30 5.7.2 Binary Search Tree(BST) 의탐색법 BST 의순환적탐색법 ( 재귀호출방법 ) tree_ptr search (tree_ptr root, int key) { /* return a pointer to the node that contains key. If there is no such node, return NULL */ if (!root) return NULL; if (key == root àdata) return root; if (key < root àdata) return search (root àleft_child, key); return search (root àright_child, key); BST의반복적탐색법 tree_ptr iter_search (tree_ptr tree, int key) { while (tree) { if (key == tree à data) return tree; if (key < tree àdata) tree = treeàleft_child; else tree = treeàright_child; return NULL; Analysis ( 이때, h 는 BST 의높이 ) search iter_search 탐색시간측면의비용분석 O(h) O(h) 사용된스택공간측면의비용분석 O(h) None 52
31 5.7.3 Binary Search Tree 에노드삽입하는방법 unique key 를지원하므로 insert 연산시, search 연산이선행되어야함 해당 key 를찾지못한경우, 검색이끝난지점에서새로운 element 를삽입함 (a) 초기상태 (b) 80 삽입 (c) 35 삽입 80 의 insert 과정 : tree 에서 80 을검색하고, 검색이성공적이지못하고검색이끝난곳은 key 40 인 node 이다. 이 node 의오른쪽 child 로서새로운 key 를 insert 한다. 53
32 삽입프로그램 : 5.15: modified_search modified_search 함수 : tree 가비어있거나 (empty) 이거나검색 search key 가이미 tree node 에존재하는경우에는, NULL 을 return 한다. 그렇지않으면 search 중만나는마지막 node 에대한 pointer 를 return 한다 ( 그곳에넣으면된다 ). void insert_node (tree_ptr *node, int num) { tree_ptr ptr, temp = modified_search (*node, num); <BST 에한노드를삽입하기 > if (temp!(*node)) { ptr = (tree_ptr) malloc (sizeof(node)); if (IS_FULL (ptr)) { fprintf (stderr, The momory is full\n ); exit (1); ptràdata = num; ptràleft_child = ptràright_child = NULL; if (*node) { if (num < tempàdata) tempàleft_child = ptr; else tempàright_child = ptr; else *node = ptr; 삽입 key 에대한 search time 이 O(h) 이고, 이외의알고리즘은 O(1) 이다. 따라서, 총시간은 O(h) 이다. 54
33 5.7.4 Binary Search Tree 에서노드를삭제하는방법 leaf node 인경우, 해당 node 를지우고그 parent 의 link 를 NULL 로만든다. 하나의 child 를가진 non-leaf node 를 delete 하는경우, 해당 node 를지우고, child node 가지워진 node 를대체한다. 두개의 children 을가진 non-leaf node 를 delete 하는경우, leaf sub-tree 의가장큰 element 나 right sub-tree 의가장작은 element 를삭제하고자하는 node 와대체한다 삭제 삭제 (a) 노드가삭제될 BST (b) delete 35 ( 단말노드삭제경우 ) (c) delete 40 ( 하나의자식노드를가지는노드제거 ) 55
34 2 개의자식노드 (50, 70) 를가지는노드 (60) 를제거하는방법 (a) 60 을제거하기전트리 (b) 60 을제거한후의트리 (a) 의 tree 에대하여 60 을 55 과 70, 둘중하나와대체할수있다. (b) 는 55 로대체한경우이다. (skewed tree 를피하기위함 ) 56
35 5.7.5 Height of a binary search tree Worst case key 를 1,2,3,., n 의순으로삽입하면, binary search tree 의 height 가 n 이된다. 일반적인경우 binary search tree 의 height 는평균 O(log 2 n) 이다. Balanced search tree worst case height로써 O(log 2 n) 를가지는 search tree 이다. search, insertion, deletion이 O(h) 에수행된다. 종류 : AVL tree, 2-3 tree, red-black tree 등 57
36 5.8 Selection Trees k 개의 ordered sequence 를하나의 ordered sequence 로 merge 하는문제 k 개의 run 으로부터첫번째 record 들을비교하여최소의 key 를찾는다. 용어 run : 각 ordered sequence 를부르는이름이며, 몇개의 record 로구성되고, key field 에따라 non-decreasing order 로정렬되어있다. n : k 개의 run 에속해있는총 record 의수 직접비교방식을사용하면최소값을하나찾기위해 k-1 번의비교를수행한다. Selection tree 를이용하면보다효율적으로최소값을찾을수있다. Definition : selection tree selection tree 는 binary tree 이고각 node 는자신의 children 중작은쪽의값을갖는다. 따라서 root 는최소값을갖는다. 58
37 Run, k = 8 인 selection tree 가있을때, 8 개의 run 들각각에첫번 3 개의 key 를보여주는그림 1 6 가장작은값 6, 출력예정! run 1 run 2 run 3 run 4 run 5 run 6 run 7 run 8 59
38 하나의레코드가출력되고, 트리가재구축된후의 selection tree 그림 (nodes that were changed are ticked) : node that is changed 이출력된이후, 트리변경! run 1 run 2 run 3 run 4 run 5 run 6 run 7 run 8 60
39 Analysis 트리를재구축하는시간은 O(log 2 k) 이다. K: Run 의개수 n 개의 record 들을모두 merge 하는시간은 O(n log 2 k) 이다. 그 selection tree 를초기구성 (set up) 하기위한시간은 the first time is O(k) 총시간 : O(n log 2 k) 61
40 A tree 62
41 ( 참고 ) 5.9 Forests ( 숲, 나무들의집합 ) 63
42 정의 Definition: forest 는 n 개 (n 0) 의 disjoint tree 의집합이다. Binary tree 의 root 를제거하면, 두개의 tree 로이루어진 forest 가생성된다. Transforming a Forest Into Binary Tree Forest 를하나의 binary tree 로변환하기위해서는다음을수행하여야한다. forest 에있는 tree 를위한 binary tree representation 을획득한다. binary tree 들은 root node 의 sibling field 를이용하여연결한다. Definition: T₁,,Tn 의 tree 로구성된 forest 에대한 binary tree 는 B(T₁,,Tn) 이고다음을만족한다. n=0 인경우 B(T₁,,Tn) 는 empty 이다. B(T₁,,Tn) 의 root 는 root(t1) 의 root 와같고 left subtree 는 B(T11,T12,T1m) 로구성되며 right subtree 는 B(T2,,Tn) 로구성된다. 단, B(T11,T12,T1m) 는 root(t1) 의 sub tree 이다. 64
43 ? A E G B C D F H I A E G B C D F H I 3 개의 tree 를가지는 forest 가되었다. 65
44 forest 를이진트리로변환하기 1. forest 내각트리를이진트리 ( 왼쪽자식 - 오른쪽형제형식 ) 로변환한다. 2. 루트노드의 sibling 으로모든이진트리를묶는다. A E G B C D F H I 66
45 정의 ) 만약 T 1,,T n 이트리들의 forest 라면, 이 forest 에해당하는이진트리는 B(T 1,,T n ) 으로표현된다. n = 0 이면, empty root (T 1 ) 을 root 로가진다 왼쪽 B(T 11,T 12,,T 1m ) sub-tree 를가짐 : T 11,T 12,,T 1m 는 root(t 1 ) 의 sub-tree 오른쪽 sub-tree 는 B(T 2,, T n ) 이다. A B E C F G D H I 67
46 Forest 순회 Forest 역시, 전위순회 (pre-order traversal), 중위순회 (in-order traversal), 후위순회 (post-order traversal) 가있다. 전위순회 (pre-order traversal) 와중위순회 (in-order traversal) 는이전에배운트리항해법과동일하다. 다음은전위순회방법만을보인다. 만약 F 가 empty 면, return F 의첫번째 tree 의 root 를방문 첫트리의 sub-tree 들을 tree 전위 (pre-order) 로순회 F 의남은 tree 들을전위 (pre-order) 순서로방문 후위순회 (post-order traversal) 는이전에배운것과다르다. ( 다른점파악할것!) 만약 F 가 empty 면, return F 의첫번째 tree 의 sub-tree 를 tree 후위로순회 나머지 tree 를 tree 후위로순회 F 의첫번째 tree 의 root 를방문 68
47 ( 참고 ) 5.10 Set 표현 트리로집합을표현하자. 가정 - 집합의요소들은 0, 1, 2,, n-1 숫자. - 모든집합들은서로분리 (disjoint) 관계 예 ) 10 개의 0 부터 9 까지의숫자들을세개의집합으로나눠보자. S 1 ={0,6,7,8, S 2 ={1,4,9, S 3 ={2,3,5 - 자식에서부모로링크를두자. Young-Ho Park
48 Set 표현 S S2 S3 집합의포리스트표현 Young-Ho Park
49 Set 표현 분리합집합 (disjoint set union) 만약 S i 와 S j 가두개의분리집합일때, 이들의합집합 S i È S j = { 모든요소 x such that x is in S i or S j find(i): 원소 i 를포함하는집합을찾는다. Young-Ho Park
50 Set 표현 union and find 연산 union 연산 루트들중하나의루트가나머지루트를가리키게만든다. 각집합의이름을다루기위해, 그집합을나타내는루트를가리키는포인터가필요하다. find 연산 각루트는집합이름을가리키는포인터를가진다. 임의의요소가어느집합에있는지알고싶다면, 1) parent 링크를따라가서그트리의루트까지간다. 2) 그곳에있는집합이름포인터를리턴한다. Young-Ho Park
51 Set 표현 S1 È S2 S2 È S1 S 1 È S 2 의가능한표현들 Young-Ho Park
52 Set 표현 0 set name pointer S1 S2 4 S S 1,S 2, S 3 의자료표현 Young-Ho Park
53 Set 표현 i [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] parent S1,S2, S3 의배열표현 int find1(int i) { for(; parent[i] >= 0; i = parent[i]) ; return i; void union1(int i, int j) { parent[i] = j; /* or parent[j] = i; */ union-find 함수의초기구현 Young-Ho Park
54 Set 표현 이전집합표현방식은, 구현이쉽지만, 성능면에서좋지않다. 예 ) S i = {i, 0 i< p - 처음에, p 개의 node 로이루어진 forest 라면, parent[i] = -1, 0 i< p - 다음과같이 operation 이수행되면, union(0,1),find(0) union(1,2),find(0) union(n-2,n-1),find(0) 변질 ( 퇴행 ) (degenerate) 트리생성 : 위연산들의시간복잡도 : O(n) + O(n 2 ) à O(n 2 ) Young-Ho Park
55 Set 표현 n-1 n-2 0 degenerate tree ( 변질트리 ) Young-Ho Park
56 Set 표현 변질트리생성을방지하기위해서는, - union(i,j) 에대한 weighting rule 정의 ) union(i,j) 를위한 weighting rule : 트리 i 에있는노드개수가트리 j 의노드개수보다작으면, j 를 i 의 parent 로만든다. 그렇지않으면, i 를 j 의 parent 로만든다. 각트리에노드개수가몇개인지알아야한다. 루트노드에 count field 가필요하다 : count[i] for root i parent[i] = -count[i] Young-Ho Park
57 Set 표현 0 1 n n n initial 0 4 n-1 union(0,1), 0=find(0) union(0,2), 0 0=find(0) n-1 union(0,3),, union(0,n-1) 0=find(0) weighting rule 을적용하여구한트리 79
chap 5: Trees
5. Threaded Binary Tree 기본개념 n 개의노드를갖는이진트리에는 2n 개의링크가존재 2n 개의링크중에 n + 1 개의링크값은 null Null 링크를다른노드에대한포인터로대체 Threads Thread 의이용 ptr left_child = NULL 일경우, ptr left_child 를 ptr 의 inorder predecessor 를가리키도록변경
슬라이드 제목 없음
Chapter 5: TREES Trees Trees Def) a tree is finite set of one or more nodes such that 1) there is a special node (root) 2) remaining nodes are partitioned into n 0 disjoint trees T 1,T 2,,T n where each
untitled
1. void inorder(tree_ptr ptr) { if(ptr) { inorder(ptr->left_child); printf( %d,ptr->data); inorder(ptr->right_child); 2) => A / B * C * D + E () A / B * C * D + E void preorder(tree_ptr ptr) { if(ptr)
chap 5: Trees
Chapter 5. TREES 목차 1. Introduction 2. 이진트리 (Binary Trees) 3. 이진트리의순회 (Binary Tree Traversals) 4. 이진트리의추가연산 5. 스레드이진트리 (Threaded Binary Trees) 6. 히프 (Heaps) 7. 이진탐색트리 (Binary Search Trees) 8. 선택트리 (Selection
Microsoft PowerPoint - 제9장-트리의응용.pptx
제 9 강의. 트리의탐색 1. 이진트리탐색알고리즘 2. 쓰레드 (Threaded) 이진트리 3. 이진트리를다루는알고리즘 1 1. 이진트리탐색알고리즘 트리의탐색 (traversal) 은트리의각노드를방문하는작업을말한다. ( 왜방문할까요?) 다음과같은방법들을생각해볼수있다. 방법 1) 레벨순 : 레벨이낮은순으로방문 A B C D E F G H 3가지다른방법이나올수있다.
4.1 관계
5 장트리 트리 (tree) 정보의항목들이가지 (branch) 로연결될수있게데이터가조직되는것, 예 ) 그림 5.1 정의 : 트리는 1 개이상의노드로이루어진유한집합으로서 1 root node 2 나머지노드들은 n( 0) 개의분리집합 (disjoint set) T 1, T 2,, T n 으로분리, T i 는각각트리로서 subtree 노드 : 정보항목 + 다른노드로뻗어진가지
7장
CHAP 7: 트리 C 로쉽게풀어쓴자료구조 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모 - 자식관계의노드들로이루어진다. 응용분야 : 계층적인조직표현파일시스템인공지능에서의결정트리 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀생산 1 팀생산 2 팀 * 예제 : 책그림 7-2, 7-3, 7-4 트리의용어 노드 (node): 트리의구성요소 루트
제 1 장 기본 개념
이진트리순회와트리반복자 트리순회 (tree traversal) 트리에있는모든노드를한번씩만방문 순회방법 : LVR, LRV, VLR, VRL, RVL, RLV L : 왼쪽이동, V : 노드방문, R : 오른쪽이동 왼쪽을오른쪽보다먼저방문 (LR) LVR : 중위 (inorder) 순회 VLR : 전위 (preorder) 순회 LRV : 후위 (postorder)
Microsoft PowerPoint - Chap5 [호환 모드]
![Microsoft PowerPoint - Chap5 [호환 모드]](/thumbs/98/135324412.jpg "Microsoft PowerPoint - Chap5 [호환 모드]")
데이터구조 (hapter 5: Trees) 2011 년봄학기 숙명여자대학교정보과학부멀티미디어과학전공박영호 Index hapter 01: asic oncepts hapter 02: rrays and Structures hapter 03: Stacks and Queues hapter 04: Lists hapter 05: Trees hapter 06: Graphs
Chapter 4. LISTS
C 언어에서리스트구현 리스트의생성 struct node { int data; struct node *link; ; struct node *ptr = NULL; ptr = (struct node *) malloc(sizeof(struct node)); Self-referential structure NULL: defined in stdio.h(k&r C) or
슬라이드 1
CHAP 7: 트리 C 로쉽게풀어쓴자료구조 생능출판사 2005 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모 - 자식관계의노드들로이루어진다. 대표이사 응용분야 : 계층적인조직표현 총무부 영업부 생산부 파일시스템 인공지능에서의결정트리 전산팀구매팀경리팀생산 1 팀생산 2 팀 트리의용어 노드 (node): 트리의구성요소 루트 (root): 부모가없는노드
Microsoft PowerPoint - ch10 - 이진트리, AVL 트리, 트리 응용 pm0600
균형이진탐색트리 -VL Tree delson, Velskii, Landis에의해 1962년에제안됨 VL trees are balanced n VL Tree is a binary search tree such that for every internal node v of T, the heights of the children of v can differ by at
슬라이드 1
Data Structure Chapter 8. 우선순위큐 Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr 우선순위큐추상데이터타입 우선순위큐 우선순위큐 (priority queue) 정의 : 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게됨 스택이나 FIFO 큐를우선순위큐로구현할수있음
Microsoft PowerPoint - chap10_tree
Chap. 10 : Tree 2007 학년도 2 학기 1. 개요 재귀 (recursion) 의정의, 순환 ~ 정의하고있는개념자체에대한정의내부에자기자신이포함되어있는경우를의미 ~ 알고리즘이나함수가수행도중에자기자신을다시호출하여문제를해결하는기법 ~ 정의자체가순환적으로되어있는경우에적합한방법 ~ 예제 ) 팩토리얼값구하기 피보나치수열 이항계수 하노이의탑 이진탐색 -2-
A Hierarchical Approach to Interactive Motion Editing for Human-like Figures
단일연결리스트 (Singly Linked List) 신찬수 연결리스트 (linked list)? tail 서울부산수원용인 null item next 구조체복습 struct name_card { char name[20]; int date; } struct name_card a; // 구조체변수 a 선언 a.name 또는 a.date // 구조체 a의멤버접근 struct
Microsoft PowerPoint - ch09 - 연결형리스트, Stack, Queue와 응용 pm0100
2015-1 프로그래밍언어 9. 연결형리스트, Stack, Queue 2015 년 5 월 4 일 교수김영탁 영남대학교공과대학정보통신공학과 (Tel : +82-53-810-2497; Fax : +82-53-810-4742 http://antl.yu.ac.kr/; E-mail : ytkim@yu.ac.kr) 연결리스트 (Linked List) 연결리스트연산 Stack
슬라이드 1
CHAP 8: 우선순위큐 yicho@gachon.ac.kr 1 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다. 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터
Chapter 4. LISTS
6. 동치관계 (Equivalence Relations) 동치관계 reflexive, symmetric, transitive 성질을만족 "equal to"(=) 관계는동치관계임. x = x x = y 이면 y = x x = y 이고 y = z 이면 x = z 동치관계를이용하여집합 S 를 동치클래스 로분할 동일한클래스내의원소 x, y 에대해서는 x y 관계성립
Microsoft PowerPoint - 자료구조2008Chap07
제 7 장트리 7.1 트리의정의 1 Tree 비선형구조, 다차원적구조 원소마다다음에여러개의원소가존재 하나이상의노드로구성된유한집합 정의1 : 루트 (root) 라는특별한노드를가지는사이클이존재치않는그래프 (acyclic graph) 정의 2 : 하나이상의노드로구성된유한집합 루트 (root) 라는특별한노드존재 나머지노드들은다시각각의트리이면서교차하지않는분리집합 (disjoint
Microsoft PowerPoint - lec07_tree [호환 모드]
![Microsoft PowerPoint - lec07_tree [호환 모드]](/thumbs/82/84829941.jpg "Microsoft PowerPoint - lec07_tree [호환 모드]")
Tree 2008학년도 2학기 kkman@sangji.ac.krac kr -1- 트리 (Tree) 1. 개요 ~ 계층적인구조를나타내는비선형 (Non-linear) 자료구조 ~ 트리는부모 - 자식관계의노드로구성 ~ 응용분야 계층적인조직표현 파일시스템 인공지능에서의결정트리 -2- 트리자료구조를사용하는이유? ~ 다른자료구조와달리비선형구조. ~ 정렬된배열 탐색은빠르지만
08장.트리
---------------- T STRUTURES USING ---------------- HPTER 트리 /29 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모-자식관계의노드들로이루어짐 응용분야 : 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀 생산 팀 생산 2 팀 (a) 회사의조직도 내문서 동영상음악사진 영화예능드라마 여행 (b) 컴퓨터의폴더구조
Chap 6: Graphs
그래프표현법 인접행렬 (Adjacency Matrix) 인접리스트 (Adjacency List) 인접다중리스트 (Adjacency Multilist) 6 장. 그래프 (Page ) 인접행렬 (Adjacency Matrix) n 개의 vertex 를갖는그래프 G 의인접행렬의구성 A[n][n] (u, v) E(G) 이면, A[u][v] = Otherwise, A[u][v]
Chapter 4. LISTS
연결리스트의응용 류관희 충북대학교 1 체인연산 체인을역순으로만드는 (inverting) 연산 3 개의포인터를적절히이용하여제자리 (in place) 에서문제를해결 typedef struct listnode *listpointer; typedef struct listnode { char data; listpointer link; ; 2 체인연산 체인을역순으로만드는
Ch.1 Introduction
Tree & Heap SANGJI University Kwangman Ko (kkman@sangji.ac.kr) 트리개요 트리 (Tree) ~ 계층적인구조를나타내는비선형 (Non-linear) 자료구조 ~ 트리는부모-자식관계의노드로구성 ~ 응용분야 계층적인조직표현 파일시스템 인공지능에서의결정트리 kkman@sangji.ac.kr 2 트리자료구조를사용하는이유?
untitled
- -, (insert) (delete) - - (insert) (delete) (top ) - - (insert) (rear) (delete) (front) A A B top A B C top push(a) push(b) push(c) A B top pop() top A B D push(d) top #define MAX_STACK_SIZE 100 int
Microsoft PowerPoint - 제8장-트리.pptx
제 8 강의. 트리 (Tree) 자료구조 1. 트리의개념 2. 이진트리 3. 이진트리의저장 1 트리자료구조필요성연결리스트의삽입삭제시데이터를이동하지않는장점을살리자. 연결리스트의검색시노드의처음부터찾아가야하는단점을보완하자. 데이터를중간부터찾아가는이진검색의장점을이용하자. 연결리스트의포인터를리스트의중간에두는방법? ptr 10 23 34 42 56 검색을중간부터시작하여좌우중하나로분기,
chap01_time_complexity.key
1 : (resource),,, 2 (time complexity),,, (worst-case analysis) (average-case analysis) 3 (Asymptotic) n growth rate Θ-, Ο- ( ) 4 : n data, n/2. int sample( int data[], int n ) { int k = n/2 ; return data[k]
슬라이드 1
CHAP 8: 우선순위큐 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다. 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터 응용분야 : 시뮬레이션시스템 ( 여기서의우선순위는대개사건의시각이다.)
Lab 3. 실습문제 (Single linked list)_해답.hwp
Lab 3. Singly-linked list 의구현 실험실습일시 : 2009. 3. 30. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 5. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Singly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Singly-linked list의각함수를구현한다.
정의 이진탐색트리 이진탐색트리 (BST: binary search tree) 는각각의노드가 BST 특성을만족하는키 - 주소쌍을가지고있는이진트리 BST 특성 트리에있는각각의키에대해, 왼쪽서브트리에있는모든키는이것보다작고, 오른쪽서브트리에있는모든키는이것보다큼 < > 2
13. 탐색트리 AVL 트리, B- 트리, 2-3-4 트리 정의 이진탐색트리 이진탐색트리 (BST: binary search tree) 는각각의노드가 BST 특성을만족하는키 - 주소쌍을가지고있는이진트리 BST 특성 트리에있는각각의키에대해, 왼쪽서브트리에있는모든키는이것보다작고, 오른쪽서브트리에있는모든키는이것보다큼 < > 2 이진탐색트리의예 3 BST 의최선과최악의경우
슬라이드 1
CHAP 7: 트리 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 리스트, 스택, 큐등은선형구조 트리는부모 - 자식관계의노드들로이루어진다. 응용분야 : 계층적인조직표현 컴퓨터디스크의디렉토리구조 인공지능에서의결정트리 (decision tree) 회사의조직 파일디렉토리구조 결정트리 ( 예 ) 골프에대한결정트리 트리의용어 노드 (node): 트리의구성요소
입학사정관제도
자료구조 강의노트 교재 : C 로배우는쉬운자료구조 ( 개정판 ) 출판사 : 한빛미디어 (2011 년 3 월발행 ) 저자 : 이지영 소프트웨어학과원성현교수 1 8 장트리 소프트웨어학과원성현교수 93 1. 트리 트리개요 트리 (tree) 란? 리스트, 스택, 큐등은선형자료구조 (linear data structure) 인것에반해서트리는계층 (hierarchy)
o 경로 (path) 트리에서사용하는용어 ~ 어떤한노드에서다른노드까지링크를통해이동했을때, 거쳐온노드들의집합. o 루트 (root) ~ 트리의가장상위에있는노드로루트는항상하나만존재 o 부모, 자식 (parent, children) ~ 링크로연결된노드중위에있는노드를부모노드,
Tree & Heap SANGJI University Kwangman Ko kkman@sangji.ac.kr - 1 - o 트리 (Tree) 1. 개요 ~ 계층적인구조를나타내는비선형 (Non-linear) 자료구조 ~ 트리는부모 - 자식관계의노드로구성 ~ 응용분야 계층적인조직표현 파일시스템 인공지능에서의결정트리 - 2 - o 트리자료구조를사용하는이유? ~ 다른자료구조와달리비선형구조.
슬라이드 1
CHAP 8: 우선순위큐 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다. 우선순위큐 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터 응용분야 : 시뮬레이션시스템
슬라이드 1
6-1 리스트 (list) 란순서를가진항목들을표현하는자료구조 리스트를구현하는두가지방법 배열 (array) 을이용하는방법 구현간단 삽입, 삭제시오버헤드 항목의개수제한 연결리스트 (linked list) 를이용하는방법 구현복잡 삽입, 삭제가효율적 크기가제한되지않음 6-2 객체 : n 개의 element 형으로구성된순서있는모임 연산 : add_last(list,
Lab 4. 실습문제 (Circular singly linked list)_해답.hwp
Lab 4. Circular singly-linked list 의구현 실험실습일시 : 2009. 4. 6. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 12. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Circular Singly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Circular
5.스택(강의자료).key
CHP 5: https://www.youtube.com/watch?v=ns-r91557ds ? (stack): (LIFO:Last-In First-Out):. D C B C B C B C B (element) C (top) B (bottom) (DT) : n element : create() ::=. is_empty(s) ::=. is_full(s) ::=.
슬라이드 1
Data Structure Chapter 7. 트리 Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr 트리의개념 트리 (Tree) 트리 : 계층적인구조를나타내는자료구조 리스트, 스택, 큐등은선형구조 정의 (1) 하나의루트 (root) 노드 (2) 다수의서브트리 (subtree) 트리는부모-자식관계의노드들로이루어짐
C 언어 강의노트
C언어 (CSE2035) (15-1 Lists) Linear list 의구성, Insertion, deletion 윤용운, Ph.D. Dept. of Computer Science and Engineering Sogang University Seoul, Korea Tel: 010-3204-6811 Email : yuyoon0@sogang.ac.kr 2018-01-11
11강-힙정렬.ppt
11 (Heap ort) leejaku@shinbiro.com Topics? Heap Heap Opeations UpHeap/Insert, DownHeap/Extract Binary Tree / Index Heap ort Heap ort 11.1 (Priority Queue) Operations ? Priority Queue? Priority Queue tack
05_tree
Tree Data Structures and Algorithms 목차 트리의개요 이진트리의구현 이진트리의순회 (Traversal) 수식트리 (Expression Tree) 의구현 Data Structures and Algorithms 2 트리의개요 Data Structures and Algorithms 3 트리의접근과이해 트리는계층적관계 (Hierarchical
<4D F736F F F696E74202D20C1A637C0E52DB0EDB1DEBFACB0E1B8AEBDBAC6AE2E >
제 7 강의. 고급연결리스트 1. 원형연결리스트 2. 이중연결리스트 3. 연결리스트알고리즘 1 1. 원형연결리스트 (Circularly Linked Lists) 원형연결리스트란? 연결리스트의맨끝노드를첫번째노드와연결시켜서원형으로만든리스트 단순연결리스트 (Singly Linked List) 불편한점 - 연결리스트의노드포인터를알고있을때첫번째노드는바로찾아갈수있지만마지막노드는리스트전체를따라가면서끝을찾아가야한다
5 장 트 리
5 장 트리 Copyright 2007 DBLAB, Seoul National University 트리구조 Copyright 2007 DBLAB, Seoul National University 2 트리 트리 : 하나이상의노드 (node) 로이루어진유한집합 1 하나의루트 (root) 노드 2 나머지노드들은 n( 0) 개의분리집합 T 1, T 2,, T n 으로분할
2002년 2학기 자료구조
자료구조 (Data Structures) Chapter 1 Basic Concepts Overview : Data (1) Data vs Information (2) Data Linear list( 선형리스트 ) - Sequential list : - Linked list : Nonlinear list( 비선형리스트 ) - Tree : - Graph : (3)
슬라이드 1
CHAP 7: 트리 yicho@gachon.ac.kr 1 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 리스트, 스택, 큐등은선형구조 트리는부모 - 자식관계의노드들로이루어진다. 응용분야 : 계층적인조직표현 컴퓨터디스크의디렉토리구조 인공지능에서의결정트리 (decision tree) 2 2 회사의조직 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀생산
PowerPoint 프레젠테이션
3. 트리 3.1 트리의개요 3.2 이진트리 3.3 트리의운행 3.1 트리의개요 트리 : 그래프의일종 데이터 : 노드 순환적정의 T = {R, T 1,T 2, T n } R : 루트 T i : 서브-트리 ( 트리 ) 3.1 트리의개요 1. 노드 2. 근노드 3. 서브트리 4. 차수 5. 단노드 6. 간노드 (nonterminal node) 7. 부-노드,
리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L = n ( item0, item1,..., item -1) l 리스트의예 l 요일 : ( 일요일, 월요일,, 토요일 ) l 한글자음의모임 : ( ㄱ, ㄴ
00. 리스트 자료구조 01. 링크드 리스트 02. 더블 링크드 리스트 03. 환형 링크드 리스트 리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L = n ( item0, item1,..., item -1) l 리스트의예 l 요일 : ( 일요일, 월요일,, 토요일 ) l 한글자음의모임 : (
1장. 리스트
01. 링크드리스트 02. 더블링크드리스트 03. 환형링크드리스트 배열과는달리유연하게크기를바꿀수있는자료구조 각노드는다음노드를가리키는포인터를가짐. 각노드를다음노드를가리키는포인터로연결하여만든리스트. Single Linked List 라고도함. 링크드리스트의첫번째노드를헤드 (Head), 마지막노드를테일 (Tail) 이라고한다. C 언어로표현하는링크드리스트의노드 typedef
06장.리스트
---------------- DATA STRUCTURES USING C ---------------- CHAPTER 리스트 1/28 리스트란? 리스트 (list), 선형리스트 (linear list) 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 카드 :
11장 포인터
Dynamic Memory and Linked List 1 동적할당메모리의개념 프로그램이메모리를할당받는방법 정적 (static) 동적 (dynamic) 정적메모리할당 프로그램이시작되기전에미리정해진크기의메모리를할당받는것 메모리의크기는프로그램이시작하기전에결정 int i, j; int buffer[80]; char name[] = data structure"; 처음에결정된크기보다더큰입력이들어온다면처리하지못함
e-비즈니스 전략 수립
트리 IT CookBook, C 로배우는쉬운자료구조 ( 개정판 ) Contents 학습목표 트리의개념을이해한다. 이진트리의자료구조를알아본다. 이진트리에서의순회를이해한다. 이진탐색트리의개념을이해하고연산방법을이해한다. 히프의자료구조를이해한다. 내용 트리 이진트리 이진트리의구현 이진트리의순회 이진탐색트리 히프 2/104 1. 트리 트리 (tree) 원소들간에 1:
03_queue
Queue Data Structures and Algorithms 목차 큐의이해와 ADT 정의 큐의배열기반구현 큐의연결리스트기반구현 큐의활용 덱 (Deque) 의이해와구현 Data Structures and Algorithms 2 큐의이해와 ADT 정의 Data Structures and Algorithms 3 큐 (Stack) 의이해와 ADT 정의 큐는 LIFO(Last-in,
Chap 6: Graphs
AOV Network 의표현 임의의 vertex 가 predecessor 를갖는지조사 각 vertex 에대해 immediate predecessor 의수를나타내는 count field 저장 Vertex 와그에부속된모든 edge 들을삭제 AOV network 을인접리스트로표현 count link struct node { int vertex; struct node
03장.스택.key
---------------- DATA STRUCTURES USING C ---------------- 03CHAPTER 1 ? (stack): (LIFO:Last-In First-Out) 2 : top : ( index -1 ),,, 3 : ( ) ( ) -> ->. ->.... 4 Stack ADT : (LIFO) : init():. is_empty():
Microsoft PowerPoint - 07-chap05-Stack.ppt
/ 스택이란? 스택 stack): 쌓아놓은더미 hapter 5 스택 Dongwon Jeong djeong@kunsan.ac.kr Department of Informatics & Statistics 학습목표 스택의개념이해 스택의동작원리이해 배열과연결리스트를이용한스택구현 스택응용프로그램 스택의특징 후입선출 LIFO:Last-In First-Out) 가장최근에들어온데이터가가장먼저나감.
Chap 6: Graphs
5. 작업네트워크 (Activity Networks) 작업 (Activity) 부분프로젝트 (divide and conquer) 각각의작업들이완료되어야전체프로젝트가성공적으로완료 두가지종류의네트워크 Activity on Vertex (AOV) Networks Activity on Edge (AOE) Networks 6 장. 그래프 (Page 1) 5.1 AOV
Microsoft PowerPoint - 6장 탐색.pptx
01. 순차탐색 02. 이진탐색 03. 이진탐색트리 04. 레드블랙트리 탐색 (search) 기본적으로여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요. 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열, 연결리스트, 트리, 그래프등 탐색키데이터 순차탐색 (sequential
슬라이드 1
CHAP 5 : 스택 yicho@gachon.ac.kr 1 5.1 스택추상데이터타입 스택 (stack) 이란?: 쌓아놓은더미 2 스택의특징 후입선출 (LIFO:Last-In First-Out): 가장최근에들어온데이터가가장먼저나감. D C B C B C B C B A A A A 3 스택의구조 요소 (element) 스택에저장되는것 C 스택상단 (top) : 스택에서입출력이이루어지는부분
쉽게 배우는 알고리즘 강의노트
쉽게배우는알고리즘 장. 정렬 Sorting http://www.hanbit.co.kr 장. 정렬 Sorting 은유, 그것은정신적상호연관성의피륙을짜는방법이다. 은유는살아있다는것의바탕이다. - 그레고리베이트슨 - 2 - 학습목표 기본정렬알고리즘을이해한다. 정렬을귀납적관점에서볼수있도록한다. 1 장과 2 장에서배운기법을사용해각정렬의수행시간을분석할수있도록한다. 비교정렬의한계를이해하고,
Microsoft Word - FunctionCall
Function all Mechanism /* Simple Program */ #define get_int() IN KEYOARD #define put_int(val) LD A val \ OUT MONITOR int add_two(int a, int b) { int tmp; tmp = a+b; return tmp; } local auto variable stack
원형연결리스트에대한설명중틀린것은 모든노드들이연결되어있다 마지막에삽입하기가간단한다 헤더노드를가질수있다 최종노드포인터가 NULL이다 리스트의 번째요소를가장빠르게찾을수있는구현방법은무엇인가 배열 단순연결리스트 원형연결리스트 이중연결리스트 단순연결리스트의노드포인터 가마지막노드를
리스트에대한설명중틀린것은 구조체도리스트의요소가될수있다 리스트의요소간에는순서가있다 리스트는여러가지방법으로구현될수있다 리스트는집합과동일하다 다음은순차적표현과연결된표현을비교한것이다 설명이틀린것은 연결된표현은포인터를가지고있어상대적으로크기가작아진다 연결된표현은삽입이용이하다 순차적표현은연결된표현보다액세스시간이많이걸린다 연결된표현으로작성된리스트를 개로분리하기가쉽다 다음은연결리스트에서있을수있는여러가지경우를설명했는데잘못된항목은
중간고사 (자료 구조)
Data Structures 215 중간고사 문제에서명시적으로기술하지않은부분은교재의내용에근거함. 215. 1. 27. 1 다음용어에대하여간단하게설명하시오 ( 각 3 점 *1=3 점 ) 1 abstract data type 6 Circular linked list 2 recursion 3 time complexity 4 space complexity 5 Single
61 62 63 64 234 235 p r i n t f ( % 5 d :, i+1); g e t s ( s t u d e n t _ n a m e [ i ] ) ; if (student_name[i][0] == \ 0 ) i = MAX; p r i n t f (\ n :\ n ); 6 1 for (i = 0; student_name[i][0]!= \ 0&&
Microsoft PowerPoint - 알고리즘_5주차_1차시.pptx
Basic Idea of External Sorting run 1 run 2 run 3 run 4 run 5 run 6 750 records 750 records 750 records 750 records 750 records 750 records run 1 run 2 run 3 1500 records 1500 records 1500 records run 1
ABC 10장
10 장구조체와리스트처리 0 자기참조구조체 자기참조구조체는자기자신의형을참조하는포인터멤버를가짐 이러한자료구조를동적자료구조라고함 배열이나단순변수는일반적으로블록을진입할때메모리할당을받지만, 동적자료구조는기억장소관리루틴을사용하여명시적으로메모리할당을요구함 10-1 자기참조구조체 10-2 자기참조구조체 예제 struct list { int struct list a; data;
09J1_ _R.hwp
상수삽입전이시간을가지는양단우선순위큐 217 DOI: 10.3745/KIPSTA.2009.16-A.3.217 상수삽입전이시간을가지는양단우선순위큐 정해재 요 약 우선순위큐는스케줄링, 정렬, 유전자검색과같은우선순위에따른검색, 최단거리계산과같은응용에사용될수있다. 본논문에서제안하는배열을이용한양단우선순위큐자료구조는삽입과삭제연산에각각 O(1) 전이시간과 O(logn) 시간이걸린다.
슬라이드 1
C programming and Data Structures Overview T. H. Cormen, C. E. Leiserson and R. L. Rivest Introduction to, 3rd Edition, MIT Press, 2009 Sungkyunkwan University Hyunseung Choo choo@skku.edu Copyright 2000-2018
Chapter 08. 트리(Tree)
윤성우의열혈자료구조 : C 언어를이용한자료구조학습서 Chapter 08. 트리 (Tree) Introduction To Data Structures Using C Chapter 08. 트리 (Tree) Chapter 08-1: 트리의개요 트리의접근과이해 트리는계층적관계 (Hierarchical Relationship) 를표현하는자료구조이다. 트리의예 트리의예
이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다. 2
제 17 장동적메모리와연결리스트 유준범 (JUNBEOM YOO) Ver. 2.0 jbyoo@konkuk.ac.kr http://dslab.konkuk.ac.kr 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다. 이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다.
슬라이드 1
CHAP 6: 큐 yicho@gachon.ac.kr 1 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 () 후단 () 2 큐 ADT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element
Lab 5. 실습문제 (Double linked list)-1_해답.hwp
Lab 5. Doubly-linked list 의구현 실험실습일시 : 2009. 4. 13. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 19. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Doubly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Doubly-linked list의각함수를구현한다.
chap x: G입력
원형큐 (Circular Queue) [2] [3] [2] [3] [1] [4] [1] [4] [0] [5] front = 0, rear = 0 [2] [3] [0] [5] front = 0, rear = 3 [1] [4] [0] [5] front = 0, rear = 0 최대큐이용률 = MAX_Q_SIZE 1 3 장. 스택과큐 (Page 13) 원형큐의구현
chap x: G입력
재귀알고리즘 (Recursive Algorithms) 재귀알고리즘의특징 문제자체가재귀적일경우적합 ( 예 : 피보나치수열 ) 이해하기가용이하나, 비효율적일수있음 재귀알고리즘을작성하는방법 재귀호출을종료하는경계조건을설정 각단계마다경계조건에접근하도록알고리즘의재귀호출 재귀알고리즘의두가지예 이진검색 순열 (Permutations) 1 장. 기본개념 (Page 19) 이진검색의재귀알고리즘
o 스택 (stack) ~ 쌓아놓은더미 1. 스택의개요 - 2 -
스택 (stack) SANGJI University Kwangman Ko o 스택 (stack) ~ 쌓아놓은더미 1. 스택의개요 - 2 - o 스택의특징 ~ 모든원소의삽입과삭제가 top 이라는자료구조의한쪽끝에서만수행되는제한된리스트구조 ~ 후입선출 (Last-In-First-Out, LIFO) 방식 가장마지막에입력된자료가가장먼저출력 o 스택의동작 ~ top 에서만삽입
Data structure: Assignment 1 Seung-Hoon Na October 1, Assignment 1 Binary search 주어진 정렬된 입력 파일이 있다고 가정하자. 단, 파일내의 숫자는 공백으로 구 분, file내에 숫자들은
Data structure: Assignment 1 Seung-Hoon Na October 1, 018 1 1.1 Assignment 1 Binary search 주어진 정렬된 입력 파일이 있다고 가정하자. 단, 파일내의 숫자는 공백으로 구 분, file내에 숫자들은 multiline으로 구성될 수 있으며, 한 라인에는 임의의 갯수의 숫자가 순서대로 나열될
고급자료구조
배상원 Binary Search Tree (BST) Balanced BSTs Red-Black Tree Splay Tree Geometric Search Trees Range Tree Interval Tree Segment Tree Binary Indexed Tree Definition (recursive) An empty tree is a binary tree
데이터구조 (Chapter 3: Stacks and Queues) 2011 년봄학기 숙명여자대학교이과대학멀티미디어과학과박영호
데이터구조 (Chapter 3: Stacks and Queues) 2011 년봄학기 숙명여자대학교이과대학멀티미디어과학과박영호 Index Chapter 01: Basic Concepts Chapter 02: Arrays and Structures Chapter 03: Stacks and Queues Chapter 04: Lists Chapter 05: Trees
리스트연산, 검색 + 삽입 + 삭제 새로운항목을리스트의처음, 중간, 끝에추가. 기존의항목을리스트의임의의위치에서삭제. 모든항목을삭제. 기존항목을대치 (replace). 리스트가특정항목을가지고있는지를검색 (search). 리스트의특정위치의항목을반환. 리스트안의항목의개수를센
Linked List 2014 2 학기 SANGJI University 리스트 (list) 1. 리스트개념 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 핸드폰의문자메시지리스트
슬라이드 1
Linked List 2015 2 학기 SANGJI University 1. 리스트개념 리스트 (list) 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 핸드폰의문자메시지리스트
untitled
年 識 料 ˍˍˍˍˍˍ 不 80 1.25 2 1~80 不 1 列 array A n n matrix 零 lower triangular matrix 列 來 n n(n+1)/2 n(n 1)/2 n n 2 例 行 Y[1][3] 列 INT Y[4][4]; FOR(I=0; I
4장
CHAP 5: 스택 스택이란? 스택 (stack): 쌓아놓은더미 스택의특징 후입선출 (LIFO:Last-In First-Out): 가장최근에들어온데이터가가장먼저나감. D C B C B C B C B A A A A 스택의구조 요소 (element) C 스택상단 (top) B A 스택하단 (bottom) 스택추상데이터타입 (ADT) 객체 : n개의 element형의요소들의선형리스트
Let G = (V, E) be a connected, undirected graph with a real-valued weight function w defined on E. Let A be a set of E, possibly empty, that is includ
알고리즘설계와분석 (CSE3081(2 반 )) 기말고사 (2016년 12월15일 ( 목 ) 오전 9시40분 ~) 담당교수 : 서강대학교컴퓨터공학과임인성 < 주의 > 답안지에답을쓴후제출할것. 만약공간이부족하면답안지의뒷면을이용하고, 반드시답을쓰는칸에어느쪽의뒷면에답을기술하였는지명시할것. 연습지는수거하지않음. function MakeSet(x) { x.parent
Algorithms
자료구조 & 알고리즘 리스트 (List) Seo, Doo-okok clickseo@gmail.com http://www.clickseo.com 목 차 선형리스트 연결리스트 2 선형리스트 선형리스트 선형리스트의개념 선형리스트의구현 연결리스트 3 선형리스트개념 리스트 (List) 목록, 대부분의목록은도표 (Table) 형태로표시 추상자료형리스트는이러한목록또는도표를추상화한것
슬라이드 1
컬렉션프레임워크 (Collection Framework) 의정의 - 다수의데이터를쉽게처리할수있는표준화된방법을제공하는클래스들 - 데이터의집합을다루고표현하기위한단일화된구조 (architecture) - JDK 1.2 이전까지는 Vector, Hashtable, Properties와같은컬렉션클래스로서로다른각자의방식으로처리 - 컬렉션프레임워크는다수의데이터를다루는데필요한다양하고풍부한클래스들을제공하므로프로그래머의부담을상당부분덜어준다.
6장정렬알고리즘.key
6 : :. (Internal sort) (External sort) (main memory). :,,.. 6.1 (Bubbble Sort).,,. 1 (pass). 1 pass, 1. (, ), 90 (, ). 2 40-50 50-90, 50 10. 50 90. 40 50 10 비교 40 50 10 비교 40 50 10 40 10 50 40 10 50 90
1. 리스트개념 리스트 (list) 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : (ᄀ,ᄂ,,ᄒ
Linked List 2010 2 학기 SANGJI University 1. 리스트개념 리스트 (list) 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : (ᄀ,ᄂ,,ᄒ) 핸드폰의문자메시지리스트
A Dynamic Grid Services Deployment Mechanism for On-Demand Resource Provisioning
Basic Data Structures, Make, GDB Contents Data Structures Linked List Tree Hash Make 사용법 디버거 (gdb) 사용법 2/17 Reference The C Programming language, Brian W. Kernighan, Dennis M. Ritchie, Prentice-Hall Teach
리스트구현방법 배열 (array) 을이용하는방법 구현이간단 삽입, 삭제동작에따른원소이동. 항목의개수제한, 정적기억공간할당. 메모리낭비, 오버플로우 연결리스트 (linked list) 를이용하는방법 구현이복잡 삽입, 삭제가효율적 크기가제한되지않음 Lecture 03_Li
Linked List 2011 2 학기 SANGJI University 리스트 (list) 1. 리스트개념 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : (ᄀ,ᄂ,,ᄒ) 핸드폰의문자메시지리스트
chap8.PDF
8 Hello!! C 2 3 4 struct - {...... }; struct jum{ int x_axis; int y_axis; }; struct - {...... } - ; struct jum{ int x_axis; int y_axis; }point1, *point2; 5 struct {....... } - ; struct{ int x_axis; int
PowerPoint 프레젠테이션
C 언어포인터정복하기 16 강. 포인터로자료구조화하기 TAE-HYONG KIM COMPUTER ENG, KIT 2 학습내용 구조체멤버와구조체포인터멤버 다른구조체 ( 변수 ) 를가리키는구조체 ( 변수 ) 연결된리스트 의구성및관리 포인터로 연결된리스트 탐색하기 3 중첩구조체에자료저장하기 중첩된구조체변수에값저장하기 struct person { char PRID[15];
Microsoft PowerPoint - 자료구조2008Chap06
제 6 장연결리스트 연결리스트개요 2 일정한순서를가지는데이터요소들을표현하는방법중의하나이다. 배열과다르게데이터요소들의논리적인순서만유지되고기억장소내에서는각데이터요소들은논리적인순서와는상관없는임의의위치를가지도록하는자료구조이다. 연결리스트에서는각데이터요소들이기억장소내의어떤위치에어떤항목이있는지를표시해주어야한다. 이를위해데이터요소에는데이터값 (value) 뿐만아니라위치정보
<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CBED0C3E0C7C1B7CEB1D7B7A55C D616E2E637070>
#include "stdafx.h" #include "Huffman.h" 1 /* 비트의부분을뽑아내는함수 */ unsigned HF::bits(unsigned x, int k, int j) return (x >> k) & ~(~0
6주차.key
6, Process concept A program in execution Program code PCB (process control block) Program counter, registers, etc. Stack Heap Data section => global variable Process in memory Process state New Running
PowerPoint 프레젠테이션
10 장. 트리 트리 리스트나스택, 큐가데이터집합을한줄로늘어세운선형자료구조라면트리는두갈래로나누어세운비선형구조이다. 비선형구조를고안한동기는바로이구조가지닌효율성때문이다. 즉, 삽입, 삭제, 검색이라는주작업에대해서선형구조보다나은시간적효율을보일수있다. 학습목표 트리와관련된용어를정확히이해한다. 이진트리의세가지순회방법의차이점을이해한다. 포인터로구현한이진탐색트리의탐색,
0. 표지에이름과학번을적으시오. (6) 1. 변수 x, y 가 integer type 이라가정하고다음빈칸에 x 와 y 의계산결과값을적으시오. (5) x = (3 + 7) * 6; x = 60 x = (12 + 6) / 2 * 3; x = 27 x = 3 * (8 / 4
Introduction to software design 2012-1 Final 2012.06.13 16:00-18:00 Student ID: Name: - 1 - 0. 표지에이름과학번을적으시오. (6) 1. 변수 x, y 가 integer type 이라가정하고다음빈칸에 x 와 y 의계산결과값을적으시오. (5) x = (3 + 7) * 6; x = 60 x
Microsoft PowerPoint - chap4_list
Chap. 4 : 리스트 (list) 2007 학년도 2 학기 리스트 1. 리스트개념 ~ 고정된길이의자료 ( 원소 ) 들을순차적으로나열해놓은집합을가르키는자료구조의추상적인개념 ~ 순서를가진항목들의모임 집합 (set) : 항목간의순서의개념이없음 리스트의예 ~ 요일 : ( 일요일, 월요일,, 토요일 ) ~ 한글자음의모임 : (ᆨ,ᆫ,,ᄒ) ~ 핸드폰의문자메시지리스트
비트와바이트 비트와바이트 비트 (Bit) : 2진수값하나 (0 또는 1) 를저장할수있는최소메모리공간 1비트 2비트 3비트... n비트 2^1 = 2개 2^2 = 4개 2^3 = 8개... 2^n 개 1 바이트는 8 비트 2 2
비트연산자 1 1 비트와바이트 비트와바이트 비트 (Bit) : 2진수값하나 (0 또는 1) 를저장할수있는최소메모리공간 1비트 2비트 3비트... n비트 2^1 = 2개 2^2 = 4개 2^3 = 8개... 2^n 개 1 바이트는 8 비트 2 2 진수법! 2, 10, 16, 8! 2 : 0~1 ( )! 10 : 0~9 ( )! 16 : 0~9, 9 a, b,
<4D F736F F F696E74202D20C1A63132B0AD20B5BFC0FB20B8DEB8F0B8AEC7D2B4E7>
제14장 동적 메모리 할당 Dynamic Allocation void * malloc(sizeof(char)*256) void * calloc(sizeof(char), 256) void * realloc(void *, size_t); Self-Referece NODE struct selfref { int n; struct selfref *next; }; Linked
Frama-C/JESSIS 사용법 소개
Frama-C 프로그램검증시스템소개 박종현 @ POSTECH PL Frama-C? C 프로그램대상정적분석도구 플러그인구조 JESSIE Wp Aorai Frama-C 커널 2 ROSAEC 2011 동계워크샵 @ 통영 JESSIE? Frama-C 연역검증플러그인 프로그램분석 검증조건추출 증명 Hoare 논리에기초한프로그램검증도구 사용법 $ frama-c jessie
-09- 학습목표 기본정렬알고리즘을이해한다. 정렬을귀납적관점에서볼수있도록한다. 1 장과 2 장에서배운기법을사용해각정렬의수행시간을분석할수있도록한다. 비교정렬의한계를이해하고, 선형시간정렬이가능한조건과선형시간정렬알고리즘을이해한다. - - 한빛미디어 Sortng Algorth
-09- 쉽게배우는알고리즘 장. 정렬 Sortng http://academy.hanb.co.kr 장. 정렬 Sortng 은유, 그것은정신적상호연관성의피륙을짜는방법이다. 은유는살아있다는것의바탕이다. - 그레고리베이트슨 - 2 - 한빛미디어 1 -09- 학습목표 기본정렬알고리즘을이해한다. 정렬을귀납적관점에서볼수있도록한다. 1 장과 2 장에서배운기법을사용해각정렬의수행시간을분석할수있도록한다.