09J1_ _R.hwp

Size: px
Start display at page:

Download "09J1_ _R.hwp"

Transcription

1 상수삽입전이시간을가지는양단우선순위큐 217 DOI: /KIPSTA A 상수삽입전이시간을가지는양단우선순위큐 정해재 요 약 우선순위큐는스케줄링, 정렬, 유전자검색과같은우선순위에따른검색, 최단거리계산과같은응용에사용될수있다. 본논문에서제안하는배열을이용한양단우선순위큐자료구조는삽입과삭제연산에각각 O(1) 전이시간과 O(logn) 시간이걸린다. 본저자가알고있는한, 지금까지의배열을이용한양단우선순위큐알고리즘은삽입과삭제에모두 O(logn) 시간이걸린다. 키워드 : 자료구조, 양단우선순위큐, 힙, 전이시간복잡도 A Double-Ended Priority Queue with O(1) Insertion Amortized Time Haejae Jung ABSTRACT Priority queues can be used in applications such as scheduling, sorting, retrival based on a priority like gene searching, shortest paths computation. This paper proposes a data structure using array representation for double-ended priority queue in which insertion and deletion takes O(1) amortized time and O(logn) time, respectively. To the author's knowledge, all the published array-based data structures for double ended priority queue support O(logn) time insertion and deletion operations. Keywords : Data Structure, Double-Ended Priority Queue, Heap, Amortized Time Complexity 1. 서론 1) 양단우선순위큐 (double-ended priority queue) 는어떤데이터집합 S에서특정우선순위에따른최소값과최대값을빨리찾고자고안된동적자료구조로서, 다음의세가지연산을기본으로지원하며, 이자료구조는운영체제스케줄링, 사건시뮬레이션, 유전자검색과같은우선순위에따른검색, 또는정렬과같은응용에이용될수있다. insert(e, S): 집합 S에새로운임의의데이터 e를추가. delmax(s): 집합 S로부터우선순위가가장높은데이터를삭제. delmin(s): 집합 S로부터우선순위가가장낮은데이터를삭제. 우선순위큐는부모-자식관계를나타내기위해포인터를사용하거나일차원배열인덱스를사용하여구현할수있다. 포인터를사용하는경우부모노드와자식노드를포 이논문은 2006 년도안동대학교특성화추진지원사업에의하여연구되었음. 종신회원 : 안동대학교정보통신공학과교수논문접수 : 2009 년 1 월 22 일수정일 :1 차 2009 년 4 월 21 일심사완료 : 2009 년 4 월 30 일 인터로연결하여부모-자식관계를나타내고, 배열을사용하는경우인덱스값에관한간단한수식을사용하여부모- 자식관계를묵시적으로나타낸다. 배열을이용한단일우선순위큐 (single-ended priority queue) 로는 O(logn) 삽입및삭제시간을가진전통적인힙, 상수삽입전이시간 (amortized time) 과 O(logn) 삭제시간복잡도를가지는묵시이항 (binomial) 큐, 및 M-힙의배열버전인 MA-힙등이있다 [1-4]. MA-힙은최대 O(logn) 개의내부힙으로구성되며, 삽입은 O(1) 전이시간복잡도 (amortized time complexity) 를가지고, 삭제는 O(logn) 시간복잡도를가진다 [1]. MA-힙은묵시이항큐보다자료구조가훨씬단순하여구현하기가상당히용이하다. 본논문에서관심이있는배열을이용한양단우선순위큐에는최대-최소힙 (min-max heap), 딥 (deap), d-딥 (d-deap), 대칭최대-최소힙 (symmetric min-max heap), 구간힙 (interval heap) 등이있으며, 이들은모두 O(logn) 삽입및삭제시간복잡도를가진다 [5-8]. 이중구간힙의구조는전통적인힙과같은완전이진트리 (complete binary tree) 형태를가지지만, 제일마지막노드를제외한각노드에는구간의좌단값과우단값을나타내는두개의값 <lval, rval> 을유지

2 218 정보처리학회논문지 A 제 16-A 권제 3 호 (2009.6) 하고, lval <= rval의관계를가진다. 삽입, 삭제연산을통하여부모노드의구간은자식노드의구간을항상포함하도록유지한다 [5, 6]. 본논문에서는상수삽입전이시간과 O(logn) 최대값 / 최소값삭제시간을가지는배열을이용한양단우선순위큐 MI-힙을제안하며, 제안된자료구조는 MA-힙의자료구조의특성과구간힙의특성을기반으로하여고안된구조이다. 본저자가알고있는한, 지금까지의배열을이용한모든양단우선순위큐에대한모든자료구조는 O(logn) 삽입과 O(logn) 최대값 / 최소값삭제시간복잡도를가진다. 2. MI-힙자료구조 MI-힙은최대 n 개의데이터를저장하기위해 개의노드를가지는포화이진트리 (full binary tree) 로표현되며, 최대 O(logn) 개의내부힙으로구성된다 [3]. 데이터를가지고있는내부힙의각루트노드는연결리스트를통하여연결된다. ( 그림 1) 은노드 2와노드 6에루트를가진두개의내부힙으로구성된 MI-힙의예를나타내며, 각내부힙의루트노드는연결리스트의노드에의해참조되고연결리스트의각노드는 lastp로부터접근될수있다. MI- 힙에서는삽입과삭제연산을하기위해서두개의변수 lastleaf와 lastp를유지한다. lastleaf는데이터를가진노드중가장오른쪽리프노드를나타내고, lastp는가장오른쪽연결리스트노드를참조하여마지막내부힙즉가장오른쪽내부힙의루트노드를접근할수있도록하고있다. MI-힙에서의는각노드에좌단값 (lval) 과우단값 (rval) 의두값 <lval, rval> 을저장하여구간을나타내는데, 그두값의관계는 lval <= rval 이다. MI-힙에서의부모노드의구간은항상자식노드의구간을포함하는관계를가진다. 예를들면, ( 그림 1) 에서노드 4와 5의구간은노드 2의구간에포함된다. ( 그림 3) MI-힙에서의연산 lastp를통하여연결된연결리스트의각노드는 ( 그림 3) 과같은구조를가진다. nextp는연결리스트의다음노드를가리키고, rootnode는내부힙의루트노드인덱스값을저장하며, height는 rootnode에의해참조되는내부힘의높이를나타낸다. ( 그림 1) 에서의연결리스트노드에있는값은 height 값이다. MI-힙에서의실질적인데이터삽입과삭제는 MI-힙에서의가장오른쪽에있는마지막내부힙의루트노드에서이루어지며, 그노드의 rval은실제저장되는어떠한값보다도크게정의된값 (( 그림 1) 에서 로표시 ) 이저장될수있다. ( 그림 3) 은연결리스트를생략한 MI-힙의구조를나타내고있다. 삽입연산시마지막내부힙루트노드의 rval이 인경우, 새데이터로 값을대체한다. 그렇지않은경우마지막두내부힙의높이를비교한다. 높이가같은경우, ( 그림 3) 의 (a) 와같이마지막두내부힙의루트노드의부모노드 h에새로운데이터와 값를삽입하고, 노드 h를새로운마지막내부힙의루트로만든다. 높이가같지않을경우, ( 그림 3) 의 (b) 와같이하나의노드로된새로운내부힙 h에새데이터와 값을삽입하고, 노드 h를마지막내부힙의루트노드로만든다. 삭제의경우실제데이터의삭제는마지막내부힙의루트노드에서일어난다. 즉, 먼저각내부힙의루트노드를조사하여최대또는최소값을찾고, 그값을마지막내부힙의 rval (rval이 이면 lval) 로대체한다. 물론기술한삽입또는대체후힙조정 (heapify) 이적절히이루어진다. 3. MI- 힙연산 3.1 초기화 MA- 힙에서는 n 개의데이터저장을위해크기가 인배열 A[M] 를할당하여, 포화이진트리가되도록한다. 참조변 ( 그림 1) MI-힙의예 nextp height rootnode ( 그림 2) 연결리스트노드구조 void initialize( nummax ) // nummax : max. number of elements MinLeaf = 2 log2(nummax) ; // leftmost leaf node MaxLeaf = 2* MinLeaf - 1; // rightmost leaf node // allocate array A[] and // initialize lastleaf and lastp. A = new Node [MaxLeaf + 1]; // array of nodes lastleaf = MinLeaf - 1; ListNode lastp = null; // reference of right most linked list node ( 그림 4) MI- 힙초기화

3 상수삽입전이시간을가지는양단우선순위큐 219 수 lastp 는 NULL 로초기화되고, 변수 lastleaf 는 MI-힙의제일왼쪽리프노드인덱스보다 1 적은값으로초기화한다. 3.2 힙조정 MI-힙에새로운데이터가삽입되면더이상 MI-힙의성질을만족하지못하게되므로힙조정을통하여 MI-힙성질을만족하도록만든다. MI-힙에서는새로운데이터가어떤내부힙의루트노드의좌단값또는우단값으로삽입될수있으며, 힙조정은하향식으로이루어진다. 새로운데이터가우단값으로상입될경우, 우단값으로만형성되는최대힙를따라하향식으로조정이이루어지는데, 그알고리즘은 ( 그림 5) 에나타나있다. 좌단값으로만구성되는최소힙을따라하향식으로힙조정을하는 heapify_lheap( ) 도이와유사하게작성할수있다. 함수 heapify_rheap() 의인수 k는새로운우단값을가지고있는노드인덱스를나타낸다. 함수 cmp_swap() 는특정 노드의좌단값과우단값을비교하여좌단값이우단값보다크면서로교환해주는함수이다. heapify_rheap() 함수에서노드 k의두자식노드의우단값중큰값을가지는노드를 max로두고, 노드 max가부모노드 k의우단값보다크면두우단값을서로교환한다. 이러한과정은부모노드의우단값이자식노드의우단값중큰값보다크면 while 반복문을빠져나와힙조정을종료한다. // k : root node to start to heapify void heapify_rheap( k ) cmp_swap( A[k].lval, A[k].rval ); left = 2*k; // left child of k while( left < MaxLeaf ) // 자식이있는동안 max = left; if( A[max].rval < A[left+1].rval ) max = left + 1; // right child of k. if( A[k].rval > A[max].rval ) break; swap( A[k].rval, A[max].rval ); cmp_swap( A[max].lval, A[max].rval ); k = max; left = 2*k; ( 그림 5) 우단힙조정알고리즘 3.3 삽입 ( 그림 6) 은 MI-힙삽입알고리즘을보여주고있다. 인수로전달된 thedata 를삽입하기위해마지막내부힙의루트노드가한개의데이터만가지고있는지알아본다. 이경우인수로전달된데이터로 rval인 INF( ) 값을대체하고 heapify_rheap() 함수를호출하여힙조정을한다. 마지막두내부힙의높이가같은경우에는마지막내부힙 루트노드의부모노드에인수 thedata와 INF 값을각각 lval 과 rval로저장하고, heapify_lheap() 을호출하여힙조정을한다. 마지막리스트노드의왼쪽노드는삭제하고, 마지막리스트노드의 rootnode와 height 필드를수정한다. 마지막두내부힙의높이가다른경우, lastleaf를 1 증가하여새로운내부힙을생성하고, 이노드의 lval과 rval 필드에 thedata와 INF 값을각각삽입한다. 이경우새로운리스트노드를하나생성하여마지막리스트노드로만들고, 이노드의 rootnode와 height 값은 lastleaf와 1이된다. ( 그림 7) 과 ( 그림 8) 은 ( 그림 1) 에데이터 45와 35를연속으로삽입한후의 MI-힙을보여주고있다. ( 그림 7) 은 45로 INF값을대체한후힙조정한결과이고, ( 그림 8) 은 35를새로운내부힙루트노드 14에삽입한결과이다. bool insert( Element thedata ) // check if the rval of the last root is infinite value. if( lastp!= NULL && A[lastp.rootnode].rval == INF ) lastroot = lastp.rootnode; A[lastroot].rval = thedata; heapify_rheap( lastroot ); return TRUE; // Now, heap is empty, or the last root node has two values. h1 = -1; h2 = -2; if( lastp ) if( lastp.rootnode == 1 ) return FALSE; // MI-힙 is full. h1 = lastp.height; // 마지막내부힙높이 sp = lastp.nextp; // 두번째리스트노드 if( sp ) h2 = sp.height; // 마지막왼쪽내부힙높이 if( h1 == h2 ) parnode = lastp.rootnode / 2; A[parnode].lval = thedata; A[parnode].rval = INF; heapify_lheap( parnode ); lastp.rootnode = parnode; lastp.height++; lastp.nextp = sp.nextp; delete sp; // 두번째리스트노드삭제 else lastleaf++; A[lastLeaf].lval = thedata; A[lastLeaf].rval = INF; np = new ListNode; np.rootnode = lastleaf; np.height = 1; np.nextp = lastp; lastp = np; return TRUE; ( 그림 6) 삽입알고리즘 ( 그림 7) ( 그림 1) 에 45 를삽입한후

4 220 정보처리학회논문지 A 제 16-A 권제 3 호 (2009.6) ( 그림 8) ( 그림 7) 에 35 를삽입한후 [ 정리 1] n 개의데이터를가지고있는 MI-힙에서, 삽입연산은 O(1) 전이시간복잡도를가진다. ( 증명 ) 리스트노드의삽입및삭제와변수 lastleaf의증가는상수시간걸리고, m개의노드를가진내부힙의힙조정은트리높이인 O(logm) 시간이걸린다. 삽입전이시간복잡도를구하기위해, 일련의삽입연산이이루어진다고하자. 일련의삽입중, 두개의내부힙으로구성된 MI-힙에새로운데이터를삽입할경우하나의내부힙만으로구성된 MI-힙이되는데, 이때최대비용이소요된다. 삽입시의힙조정은항상이웃하는두내부힙의부모노드에서시작하여리프노드쪽으로이루어지므로, 그부모노드의높이만큼의시간이걸린다. 따라서, 하나의내부힙으로구성된 MI-힙의높이가 h라할때, 일련의삽입총 비용을계산하면 가된다. 즉, 트리레벨 i 에는 개의노드가있고, 각노드에대한 2개의데이터삽입비용은 가된다. 따라서총비용을계산하면, 이되므로, 각데이터삽입에대한전이시간복잡도는 이된다. int find_maxnode( void ) maxnode = lastp.rootnode; leftchild = 2 * maxnode; if( maxnode.rval == INF && leftchild <= MaxLeaf ) rightchild = leftchild +1; maxnode = leftchild; if( A[leftchild].rval < A[rightchild].rval ) maxnode = rightchild; maxval = A[maxnode].rval; if( A[maxnode].rval == INF ) maxval = A[maxnode].lval; tmp = lastp.nextp; while( tmp ) if( A[tmp.rootnode].rval > maxval ) maxnode = tmp.rootnode; maxval = A[maxnode].rval; tmp = tmp.nextp; return maxnode; // node index with maxval ( 그림 9) 최대값을가진노드찾기함수 Element delmax( ) if( lastp == NULL ) return -1; // MI-힙 is empty. maxnode = find_maxnode( ); // find the node with max. element retdata = A[maxnode].rval; if( A[maxnode].rval == INF ) // maxnode == lastroot : leaf node retdata = A[maxnode].lval; lastleaf--; tmp = lastp; lastp = lastp.nextp; delete tmp; lastroot = lastp.rootnode; if( A[lastroot].rval == INF ) // lastroot has children, maxnode!= lastroot A[maxnode].rval = A[lastroot].lval; heapify_rheap( maxnode ); if( 2*lastroot < MaxLeaf ) split_heap( ); else lastleaf--; tmp = lastp; lastp = lastp.nextp; delete tmp; 3.4 최대값삭제최대값은내부힙들중어떤한내부힙의루트노드또는마지막내부힙의루트노드의자식노드에있을수있다. ( 그림 9) 에서보는바와같이마지막내부힙의 rval이 INF 값을가지고있는경우그자식노드의값도조사하여최대값을가진노드및값을각각 maxnode 및 maxval로둔다. 마지막내부힙을제외한내부힙에대해서는루트노드의 rval만비교하면되며, while 문을통하여최대값을가진 maxnode를찾게된다. MI-힙에서의최대값삭제는최대값을가지고있는내부힙을찾은후, 그최대값을마지막내부힙의루트노드값으로대체하고, 대체된내부힙에대해힙조정을함으로써이루어진다. ( 그림 10) 의최대값삭제알고리즘은우선 find_maxnode() 함수를호출하여최대값을가진노드 maxnode를찾는다. // Now, there is no INF value in MI-heap. if( lastroot!= maxnode ) A[maxnode].rval = A[lastroot].rval; heapify_rheap( maxnode ); A[lastroot].rval = INF; ( 그림 10) 최대값삭제알고리즘 maxnode의 rval이 INF이면 maxnode는단하나의리프노드만을가진마지막내부힙이므로마지막내부힙을삭제하고최대값을리턴한다. 그렇지않고마지막내부힙루트노드의 rval이 INF이면, 그노드의 lval을 maxnode의 rval로대체한후힙조정을한다. 힙조정후, 마지막내부힙루트노드가

5 상수삽입전이시간을가지는양단우선순위큐 221 자식을가지고있으면 split_heap( ) 함수를호출하여마지 4. 결론 막내부힙의루트노드의오른쪽자식을마지막내부힙루 트노드로만들고, 자식이없으면마지막내부힙을제거한 본고에서제안한 MI-힙은배열을이용하여묵시적으로 다. 위의경우가아니면, 마지막내부힙의 rval을 maxnode 부모-자식관계를표현하는양단우선순위큐자료구조이다. 의 rval로복사한후 maxnode 로부터하향식으로힙조정을 배열을이용한기존의양단우선순위큐알고리즘은삽입 한다. 마지막내부힙루트노드인 lastroot의 rval에는 INF 과삭제를하는데모두 O(logn) 시간이걸렸지만, 본논문에 값을삽인한후, 최대값을리턴한다. 서제안한 MI-힙에서는삽입과최대값 / 최소값삭제연산에 ( 그림 11) 의 split_heap( ) 함수는마지막내부힙의루트 각각상수전이시간과 O(logn) 시간복잡도를가진다. 노드에더이상데이터가없을경우그자식들을루트로하 는두개의내부힙으로분리하는함수이다. 이때, 마지막 참고문헌 두내부힙의높이는 1 감소한다. ( 그림 12) 는기술한알고리즘에따라 ( 그림 8) 로부터최 [1] 정해재, 배열표현을이용한 M-힙에서의삽입 / 삭제알고리 대값 90을삭제한결과를보여주고있다. 즘, 정보처리학회논문지, 13-A(3), pp , Jun., [2] D. Mehta, and S. Sahni(ed.), Handbook of Data Structures [ 정리 2] n 개의데이터를가지고있는 MI-힙에서, 최대 and Applications, Chapman & Hall/CRC, New York, 값삭제연산은 O(logn) 시간복잡도를가진다. [3] S. Bansal, S. Sreekanth, and P. Gupta, M-heap: A Modified heap data structures, International Journal of Foundations ( 증명 ) 힙조정알고리즘 heapify_rheap( ) 은힙의높이만 of Computer Science, 14(3), pp , 큼의시간이걸리므로 O(logn) 시간이걸리고, MI-힙에최대 [4] S. Carlsson, J. Munro, and P. Poblete, An implicit binomial O(logn) 개의내부힙이존재할수있으므로최대값을가진 queue with constant insertion time, Proceedings of the 1st 노드를찾는함수 find_maxnode( ) 또한 O(logn) 시간이걸 Scandinavian Workshop on Algorithm Theory, Lecture 린다. 그외의삭제알고리즘에서사용하는함수 split_heap( ) Notes in Computer Science, 318, pp.1-13, July, 과문장은상수시간이걸린다. 따라서최대값삭제알고리 [5] J. van Leeuwen and D. Wood, Interval heaps, The Computer 즘은 O(logn) 시간복잡도를가진다. Journal, 36(3), , O(logn) 시간복잡도를가지는최소값삭제알고리즘도 [6] Y. Ding and M. Weiss, On the Complexity of Building an 최대값삭제알고리즘과유사하며, 구체적인알고리즘은 [ 부 Interval Heap, Information Processing Letters, 50, , 록 ] 의 ( 그림 13) 와 ( 그림 14) 에나타나있다 [7] H. Jung, The d-deap*: A fast and simple cache-aligned d-ary deap, Information Processing Letters, 93(2), pp.63-67, void split_heap( void ) // 마지막내부힙루트가자식을가지고있음. Jan., [8] E. Horowitz, S. Sahni, and D. Mehta, Fundamentals of Data sp = new ListNode; sp.nextp = lastp.nextp; lastp.nextp = sp; Structures in C++, W. H. Freeman, San Francisco, leftchild = 2 * lastp.rootnode; lastp.rootnode = leftchild+1; lastp.height--; sp.rootnode = leftchild; sp.height = lastp.height; ( 부록 ) 최소값삭제알고리즘 ( 그림 11) 마지막내부힙의분할 int find_minnode( void ) minroot = lastp.rootnode; tmp = lastp.nextp; while( tmp ) if( A[tmp.rootnode].lval < A[minroot].lval ) minroot = tmp.rootroot; tmp = tmp.nextp; return minroot; // node index with minval ( 그림 12) ( 그림 8) 로부터최대값삭제후 MI- 힙 ( 그림 13) 최소값을가진노드찾기함수

6 222 정보처리학회논문지 A 제 16-A 권제 3 호 (2009.6) Element delmin( ) if( lastp == NULL ) return -1; // MI-힙 is empty. minroot = find_minnode( ); // find the node with min. element retdata = A[minroot].lval; lastroot = lastp.rootnode; A[minroot].lval = A[lastroot].lval; heapify_lheap( minroot ); if( A[lastroot].rval!= INF ) A[lastroot].lval = A[lastroot].rval; heapify_lheap( lastroot ); A[lastroot].rval = INF; // A[lastroot].rval is INF. leftchild = 2 * lastroot; if( leftchild > MaxLeaf ) // lastroot is a leaf node. lastleaf--; tmp = lastp; lastp = lastp.nextp; delete tmp; else // lastroot has children split_heap( ); 정해재 hjjung@andong.ac.kr 1984년경북대학교전자계산학과 ( 학사 ) 1987년서울대학교컴퓨터공학과 ( 공학석사 ) 2000년플로리다대학교 (UF) 컴퓨터정보학과 ( 공학박사 ) 1988년~1995년한국전자통신연구원선임연구원 2001년~2002년 Numerical Technologies Inc. Staff Engineer 2003년~2005년성신여자대학교컴퓨터정보학부교수 2005년~현재안동대학교정보통신공학과교수관심분야 : 알고리즘, 계산기하, 웹데이터베이스, 웹보안 ( 그림 14) 최소값삭제알고리즘

chap 5: Trees

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 를가리키도록변경

More information

chap 5: Trees

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

More information

7장

7장 CHAP 7: 트리 C 로쉽게풀어쓴자료구조 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모 - 자식관계의노드들로이루어진다. 응용분야 : 계층적인조직표현파일시스템인공지능에서의결정트리 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀생산 1 팀생산 2 팀 * 예제 : 책그림 7-2, 7-3, 7-4 트리의용어 노드 (node): 트리의구성요소 루트

More information

Microsoft PowerPoint - ch09 - 연결형리스트, Stack, Queue와 응용 pm0100

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

More information

슬라이드 1

슬라이드 1 CHAP 7: 트리 C 로쉽게풀어쓴자료구조 생능출판사 2005 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모 - 자식관계의노드들로이루어진다. 대표이사 응용분야 : 계층적인조직표현 총무부 영업부 생산부 파일시스템 인공지능에서의결정트리 전산팀구매팀경리팀생산 1 팀생산 2 팀 트리의용어 노드 (node): 트리의구성요소 루트 (root): 부모가없는노드

More information

Chapter 4. LISTS

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

More information

Chapter 4. LISTS

Chapter 4. LISTS 연결리스트의응용 류관희 충북대학교 1 체인연산 체인을역순으로만드는 (inverting) 연산 3 개의포인터를적절히이용하여제자리 (in place) 에서문제를해결 typedef struct listnode *listpointer; typedef struct listnode { char data; listpointer link; ; 2 체인연산 체인을역순으로만드는

More information

03_queue

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,

More information

슬라이드 1

슬라이드 1 CHAP 6: 큐 yicho@gachon.ac.kr 1 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 () 후단 () 2 큐 ADT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element

More information

Microsoft PowerPoint - Chap5 [호환 모드]

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

More information

슬라이드 1

슬라이드 1 Data Structure Chapter 8. 우선순위큐 Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr 우선순위큐추상데이터타입 우선순위큐 우선순위큐 (priority queue) 정의 : 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게됨 스택이나 FIFO 큐를우선순위큐로구현할수있음

More information

11강-힙정렬.ppt

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

More information

Ch.1 Introduction

Ch.1 Introduction Tree & Heap SANGJI University Kwangman Ko (kkman@sangji.ac.kr) 트리개요 트리 (Tree) ~ 계층적인구조를나타내는비선형 (Non-linear) 자료구조 ~ 트리는부모-자식관계의노드로구성 ~ 응용분야 계층적인조직표현 파일시스템 인공지능에서의결정트리 kkman@sangji.ac.kr 2 트리자료구조를사용하는이유?

More information

슬라이드 1

슬라이드 1 CHAP 8: 우선순위큐 yicho@gachon.ac.kr 1 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다. 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터

More information

06장.리스트

06장.리스트 ---------------- DATA STRUCTURES USING C ---------------- CHAPTER 리스트 1/28 리스트란? 리스트 (list), 선형리스트 (linear list) 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 카드 :

More information

Microsoft PowerPoint - ch10 - 이진트리, AVL 트리, 트리 응용 pm0600

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

More information

o 경로 (path) 트리에서사용하는용어 ~ 어떤한노드에서다른노드까지링크를통해이동했을때, 거쳐온노드들의집합. o 루트 (root) ~ 트리의가장상위에있는노드로루트는항상하나만존재 o 부모, 자식 (parent, children) ~ 링크로연결된노드중위에있는노드를부모노드,

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 트리자료구조를사용하는이유? ~ 다른자료구조와달리비선형구조.

More information

쉽게 배우는 알고리즘 강의노트

쉽게 배우는 알고리즘 강의노트 쉽게배우는알고리즘 장. 정렬 Sorting http://www.hanbit.co.kr 장. 정렬 Sorting 은유, 그것은정신적상호연관성의피륙을짜는방법이다. 은유는살아있다는것의바탕이다. - 그레고리베이트슨 - 2 - 학습목표 기본정렬알고리즘을이해한다. 정렬을귀납적관점에서볼수있도록한다. 1 장과 2 장에서배운기법을사용해각정렬의수행시간을분석할수있도록한다. 비교정렬의한계를이해하고,

More information

정의 이진탐색트리 이진탐색트리 (BST: binary search tree) 는각각의노드가 BST 특성을만족하는키 - 주소쌍을가지고있는이진트리 BST 특성 트리에있는각각의키에대해, 왼쪽서브트리에있는모든키는이것보다작고, 오른쪽서브트리에있는모든키는이것보다큼 < > 2

정의 이진탐색트리 이진탐색트리 (BST: binary search tree) 는각각의노드가 BST 특성을만족하는키 - 주소쌍을가지고있는이진트리 BST 특성 트리에있는각각의키에대해, 왼쪽서브트리에있는모든키는이것보다작고, 오른쪽서브트리에있는모든키는이것보다큼 < > 2 13. 탐색트리 AVL 트리, B- 트리, 2-3-4 트리 정의 이진탐색트리 이진탐색트리 (BST: binary search tree) 는각각의노드가 BST 특성을만족하는키 - 주소쌍을가지고있는이진트리 BST 특성 트리에있는각각의키에대해, 왼쪽서브트리에있는모든키는이것보다작고, 오른쪽서브트리에있는모든키는이것보다큼 < > 2 이진탐색트리의예 3 BST 의최선과최악의경우

More information

Chapter 4. LISTS

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 관계성립

More information

C 언어 강의노트

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

More information

원형연결리스트에대한설명중틀린것은 모든노드들이연결되어있다 마지막에삽입하기가간단한다 헤더노드를가질수있다 최종노드포인터가 NULL이다 리스트의 번째요소를가장빠르게찾을수있는구현방법은무엇인가 배열 단순연결리스트 원형연결리스트 이중연결리스트 단순연결리스트의노드포인터 가마지막노드를

원형연결리스트에대한설명중틀린것은 모든노드들이연결되어있다 마지막에삽입하기가간단한다 헤더노드를가질수있다 최종노드포인터가 NULL이다 리스트의 번째요소를가장빠르게찾을수있는구현방법은무엇인가 배열 단순연결리스트 원형연결리스트 이중연결리스트 단순연결리스트의노드포인터 가마지막노드를 리스트에대한설명중틀린것은 구조체도리스트의요소가될수있다 리스트의요소간에는순서가있다 리스트는여러가지방법으로구현될수있다 리스트는집합과동일하다 다음은순차적표현과연결된표현을비교한것이다 설명이틀린것은 연결된표현은포인터를가지고있어상대적으로크기가작아진다 연결된표현은삽입이용이하다 순차적표현은연결된표현보다액세스시간이많이걸린다 연결된표현으로작성된리스트를 개로분리하기가쉽다 다음은연결리스트에서있을수있는여러가지경우를설명했는데잘못된항목은

More information

제 1 장 기본 개념

제 1 장 기본 개념 이진트리순회와트리반복자 트리순회 (tree traversal) 트리에있는모든노드를한번씩만방문 순회방법 : LVR, LRV, VLR, VRL, RVL, RLV L : 왼쪽이동, V : 노드방문, R : 오른쪽이동 왼쪽을오른쪽보다먼저방문 (LR) LVR : 중위 (inorder) 순회 VLR : 전위 (preorder) 순회 LRV : 후위 (postorder)

More information

08장.트리

08장.트리 ---------------- T STRUTURES USING ---------------- HPTER 트리 /29 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모-자식관계의노드들로이루어짐 응용분야 : 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀 생산 팀 생산 2 팀 (a) 회사의조직도 내문서 동영상음악사진 영화예능드라마 여행 (b) 컴퓨터의폴더구조

More information

슬라이드 1

슬라이드 1 CHP 6: 큐 C 로쉽게풀어쓴자료구조 생능출판사 2005 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 () 후단 () 큐 DT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element

More information

Microsoft PowerPoint - 08-Queue.ppt

Microsoft PowerPoint - 08-Queue.ppt Chapter Queue ( 큐 ) Dongwon Jeong djeong@kunsan.ac.kr Department of Informatics & Statistics 학습목표 큐의개념및추상데이터타입에대한이해 큐의구현방법 배열 링크드리스트 덱 / 데크의개념과구현방법 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In

More information

Microsoft PowerPoint - 08-chap06-Queue.ppt

Microsoft PowerPoint - 08-chap06-Queue.ppt / 큐 (QUEUE) Chapter 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 큐 Ticket ox Dongwon Jeong djeong@kunsan.ac.kr Department of Kunsan National University 전단 () 후단 () 학습목표 큐 DT 큐의개념및추상데이터타입에대한이해

More information

Microsoft PowerPoint - chap10_tree

Microsoft PowerPoint - chap10_tree Chap. 10 : Tree 2007 학년도 2 학기 1. 개요 재귀 (recursion) 의정의, 순환 ~ 정의하고있는개념자체에대한정의내부에자기자신이포함되어있는경우를의미 ~ 알고리즘이나함수가수행도중에자기자신을다시호출하여문제를해결하는기법 ~ 정의자체가순환적으로되어있는경우에적합한방법 ~ 예제 ) 팩토리얼값구하기 피보나치수열 이항계수 하노이의탑 이진탐색 -2-

More information

슬라이드 1

슬라이드 1 6-1 리스트 (list) 란순서를가진항목들을표현하는자료구조 리스트를구현하는두가지방법 배열 (array) 을이용하는방법 구현간단 삽입, 삭제시오버헤드 항목의개수제한 연결리스트 (linked list) 를이용하는방법 구현복잡 삽입, 삭제가효율적 크기가제한되지않음 6-2 객체 : n 개의 element 형으로구성된순서있는모임 연산 : add_last(list,

More information

Microsoft PowerPoint - lec07_tree [호환 모드]

Microsoft PowerPoint - lec07_tree [호환 모드] Tree 2008학년도 2학기 kkman@sangji.ac.krac kr -1- 트리 (Tree) 1. 개요 ~ 계층적인구조를나타내는비선형 (Non-linear) 자료구조 ~ 트리는부모 - 자식관계의노드로구성 ~ 응용분야 계층적인조직표현 파일시스템 인공지능에서의결정트리 -2- 트리자료구조를사용하는이유? ~ 다른자료구조와달리비선형구조. ~ 정렬된배열 탐색은빠르지만

More information

입학사정관제도

입학사정관제도 자료구조 강의노트 교재 : C 로배우는쉬운자료구조 ( 개정판 ) 출판사 : 한빛미디어 (2011 년 3 월발행 ) 저자 : 이지영 소프트웨어학과원성현교수 1 8 장트리 소프트웨어학과원성현교수 93 1. 트리 트리개요 트리 (tree) 란? 리스트, 스택, 큐등은선형자료구조 (linear data structure) 인것에반해서트리는계층 (hierarchy)

More information

Lab 3. 실습문제 (Single linked list)_해답.hwp

Lab 3. 실습문제 (Single linked list)_해답.hwp Lab 3. Singly-linked list 의구현 실험실습일시 : 2009. 3. 30. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 5. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Singly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Singly-linked list의각함수를구현한다.

More information

11장 포인터

11장 포인터 Dynamic Memory and Linked List 1 동적할당메모리의개념 프로그램이메모리를할당받는방법 정적 (static) 동적 (dynamic) 정적메모리할당 프로그램이시작되기전에미리정해진크기의메모리를할당받는것 메모리의크기는프로그램이시작하기전에결정 int i, j; int buffer[80]; char name[] = data structure"; 처음에결정된크기보다더큰입력이들어온다면처리하지못함

More information

Lab 4. 실습문제 (Circular singly linked list)_해답.hwp

Lab 4. 실습문제 (Circular singly linked list)_해답.hwp Lab 4. Circular singly-linked list 의구현 실험실습일시 : 2009. 4. 6. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 12. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Circular Singly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Circular

More information

Contents v 학습목표 자료구조큐에대한개념을스택과비교하여이해한다. 큐의특징과연산방법에대해알아본다. 순차표현방법을이용한큐와연결표현방법을이용한큐를구현해본다. 큐의응용방법을알아본다. v 내용 큐 큐의구현 큐의응용 2/74

Contents v 학습목표 자료구조큐에대한개념을스택과비교하여이해한다. 큐의특징과연산방법에대해알아본다. 순차표현방법을이용한큐와연결표현방법을이용한큐를구현해본다. 큐의응용방법을알아본다. v 내용 큐 큐의구현 큐의응용 2/74 큐 IT CookBook, C 로배우는쉬운자료구조 ( 개정판 ) Contents v 학습목표 자료구조큐에대한개념을스택과비교하여이해한다. 큐의특징과연산방법에대해알아본다. 순차표현방법을이용한큐와연결표현방법을이용한큐를구현해본다. 큐의응용방법을알아본다. v 내용 큐 큐의구현 큐의응용 2/74 1. 큐 v 큐 (Queue) 데이터의삽입과삭제가양쪽끝에서일어나는자료구조

More information

Microsoft PowerPoint - 6장 탐색.pptx

Microsoft PowerPoint - 6장 탐색.pptx 01. 순차탐색 02. 이진탐색 03. 이진탐색트리 04. 레드블랙트리 탐색 (search) 기본적으로여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요. 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열, 연결리스트, 트리, 그래프등 탐색키데이터 순차탐색 (sequential

More information

A Hierarchical Approach to Interactive Motion Editing for Human-like Figures

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

More information

<4D F736F F F696E74202D20C1A637C0E52DB0EDB1DEBFACB0E1B8AEBDBAC6AE2E >

<4D F736F F F696E74202D20C1A637C0E52DB0EDB1DEBFACB0E1B8AEBDBAC6AE2E > 제 7 강의. 고급연결리스트 1. 원형연결리스트 2. 이중연결리스트 3. 연결리스트알고리즘 1 1. 원형연결리스트 (Circularly Linked Lists) 원형연결리스트란? 연결리스트의맨끝노드를첫번째노드와연결시켜서원형으로만든리스트 단순연결리스트 (Singly Linked List) 불편한점 - 연결리스트의노드포인터를알고있을때첫번째노드는바로찾아갈수있지만마지막노드는리스트전체를따라가면서끝을찾아가야한다

More information

chap01_time_complexity.key

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]

More information

슬라이드 1

슬라이드 1 CHAP 8: 우선순위큐 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다. 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터 응용분야 : 시뮬레이션시스템 ( 여기서의우선순위는대개사건의시각이다.)

More information

Microsoft PowerPoint - 제8장-트리.pptx

Microsoft PowerPoint - 제8장-트리.pptx 제 8 강의. 트리 (Tree) 자료구조 1. 트리의개념 2. 이진트리 3. 이진트리의저장 1 트리자료구조필요성연결리스트의삽입삭제시데이터를이동하지않는장점을살리자. 연결리스트의검색시노드의처음부터찾아가야하는단점을보완하자. 데이터를중간부터찾아가는이진검색의장점을이용하자. 연결리스트의포인터를리스트의중간에두는방법? ptr 10 23 34 42 56 검색을중간부터시작하여좌우중하나로분기,

More information

중간고사 (자료 구조)

중간고사 (자료 구조) 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

More information

설계란 무엇인가?

설계란 무엇인가? 금오공과대학교 C++ 프로그래밍 jhhwang@kumoh.ac.kr 컴퓨터공학과 황준하 6 강. 함수와배열, 포인터, 참조목차 함수와포인터 주소값의매개변수전달 주소의반환 함수와배열 배열의매개변수전달 함수와참조 참조에의한매개변수전달 참조의반환 프로그래밍연습 1 /15 6 강. 함수와배열, 포인터, 참조함수와포인터 C++ 매개변수전달방법 값에의한전달 : 변수값,

More information

리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L = n ( item0, item1,..., item -1) l 리스트의예 l 요일 : ( 일요일, 월요일,, 토요일 ) l 한글자음의모임 : ( ㄱ, ㄴ

리스트 (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 한글자음의모임 : (

More information

05_tree

05_tree Tree Data Structures and Algorithms 목차 트리의개요 이진트리의구현 이진트리의순회 (Traversal) 수식트리 (Expression Tree) 의구현 Data Structures and Algorithms 2 트리의개요 Data Structures and Algorithms 3 트리의접근과이해 트리는계층적관계 (Hierarchical

More information

1장. 리스트

1장. 리스트 01. 링크드리스트 02. 더블링크드리스트 03. 환형링크드리스트 배열과는달리유연하게크기를바꿀수있는자료구조 각노드는다음노드를가리키는포인터를가짐. 각노드를다음노드를가리키는포인터로연결하여만든리스트. Single Linked List 라고도함. 링크드리스트의첫번째노드를헤드 (Head), 마지막노드를테일 (Tail) 이라고한다. C 언어로표현하는링크드리스트의노드 typedef

More information

슬라이드 1

슬라이드 1 CHAP 8: 우선순위큐 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다. 우선순위큐 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터 응용분야 : 시뮬레이션시스템

More information

제 11 장 다원 탐색 트리

제 11 장 다원 탐색 트리 제 11 장 다원탐색트리 Copyright 07 DBLB, Seoul National University m- 원탐색트리의정의와성질 (1) 탐색성능을향상시키려면메모리접근횟수를줄여야함 탐색트리의높이를줄여야함 차수 (degree) 가 2보다큰탐색트리가필요 m- 원탐색트리 (m-way search tree) 공백이거나다음성질을만족 (1) 루트는최대 m 개의서브트리를가진다.

More information

슬라이드 1

슬라이드 1 CHAP 7: 트리 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 리스트, 스택, 큐등은선형구조 트리는부모 - 자식관계의노드들로이루어진다. 응용분야 : 계층적인조직표현 컴퓨터디스크의디렉토리구조 인공지능에서의결정트리 (decision tree) 회사의조직 파일디렉토리구조 결정트리 ( 예 ) 골프에대한결정트리 트리의용어 노드 (node): 트리의구성요소

More information

2. QUEUE OPERATIONS Initialize the queue Insert to the rear of the queue (also called as Enqueue) Remove (Delete) from the front of the queue (also ca

2. QUEUE OPERATIONS Initialize the queue Insert to the rear of the queue (also called as Enqueue) Remove (Delete) from the front of the queue (also ca Queues The name "queue" likely comes from the everyday use of the term. Consider: queue of people waiting at a bus stop, as pictured in fig. below. Each new person who comes and takes his or her place

More information

Chap 6: Graphs

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]

More information

Lab 5. 실습문제 (Double linked list)-1_해답.hwp

Lab 5. 실습문제 (Double linked list)-1_해답.hwp Lab 5. Doubly-linked list 의구현 실험실습일시 : 2009. 4. 13. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 19. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Doubly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Doubly-linked list의각함수를구현한다.

More information

제 11 장포인터 유준범 (JUNBEOM YOO) Ver 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다.

제 11 장포인터 유준범 (JUNBEOM YOO) Ver 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다. 제 11 장포인터 유준범 (JUNBEOM YOO) Ver. 2.0 jbyoo@konkuk.ac.kr http://dslab.konkuk.ac.kr 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다. 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습합니다.

More information

Microsoft PowerPoint - Chap5 [호환 모드]

Microsoft PowerPoint - Chap5 [호환 모드] 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,

More information

Microsoft PowerPoint - ch07 - 포인터 pm0415

Microsoft PowerPoint - ch07 - 포인터 pm0415 2015-1 프로그래밍언어 7. 포인터 (Pointer), 동적메모리할당 2015 년 4 월 4 일 교수김영탁 영남대학교공과대학정보통신공학과 (Tel : +82-53-810-2497; Fax : +82-53-810-4742 http://antl.yu.ac.kr/; E-mail : ytkim@yu.ac.kr) Outline 포인터 (pointer) 란? 간접참조연산자

More information

Microsoft PowerPoint - chap-11.pptx

Microsoft PowerPoint - chap-11.pptx 쉽게풀어쓴 C 언어 Express 제 11 장포인터 컴퓨터프로그래밍기초 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습한다. 컴퓨터프로그래밍기초 2 포인터란? 포인터 (pointer): 주소를가지고있는변수 컴퓨터프로그래밍기초 3 메모리의구조 변수는메모리에저장된다. 메모리는바이트단위로액세스된다.

More information

-09- 학습목표 기본정렬알고리즘을이해한다. 정렬을귀납적관점에서볼수있도록한다. 1 장과 2 장에서배운기법을사용해각정렬의수행시간을분석할수있도록한다. 비교정렬의한계를이해하고, 선형시간정렬이가능한조건과선형시간정렬알고리즘을이해한다. - - 한빛미디어 Sortng Algorth

-09- 학습목표 기본정렬알고리즘을이해한다. 정렬을귀납적관점에서볼수있도록한다. 1 장과 2 장에서배운기법을사용해각정렬의수행시간을분석할수있도록한다. 비교정렬의한계를이해하고, 선형시간정렬이가능한조건과선형시간정렬알고리즘을이해한다. - - 한빛미디어 Sortng Algorth -09- 쉽게배우는알고리즘 장. 정렬 Sortng http://academy.hanb.co.kr 장. 정렬 Sortng 은유, 그것은정신적상호연관성의피륙을짜는방법이다. 은유는살아있다는것의바탕이다. - 그레고리베이트슨 - 2 - 한빛미디어 1 -09- 학습목표 기본정렬알고리즘을이해한다. 정렬을귀납적관점에서볼수있도록한다. 1 장과 2 장에서배운기법을사용해각정렬의수행시간을분석할수있도록한다.

More information

슬라이드 1

슬라이드 1 Data Structure Chapter 7. 트리 Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr 트리의개념 트리 (Tree) 트리 : 계층적인구조를나타내는자료구조 리스트, 스택, 큐등은선형구조 정의 (1) 하나의루트 (root) 노드 (2) 다수의서브트리 (subtree) 트리는부모-자식관계의노드들로이루어짐

More information

Microsoft PowerPoint - chap06-2pointer.ppt

Microsoft PowerPoint - chap06-2pointer.ppt 2010-1 학기프로그래밍입문 (1) chapter 06-2 참고자료 포인터 박종혁 Tel: 970-6702 Email: jhpark1@snut.ac.kr 한빛미디어 출처 : 뇌를자극하는 C프로그래밍, 한빛미디어 -1- 포인터의정의와사용 변수를선언하는것은메모리에기억공간을할당하는것이며할당된이후에는변수명으로그기억공간을사용한다. 할당된기억공간을사용하는방법에는변수명외에메모리의실제주소값을사용하는것이다.

More information

2002년 2학기 자료구조

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)

More information

목차 포인터의개요 배열과포인터 포인터의구조 실무응용예제 C 2

목차 포인터의개요 배열과포인터 포인터의구조 실무응용예제 C 2 제 8 장. 포인터 목차 포인터의개요 배열과포인터 포인터의구조 실무응용예제 C 2 포인터의개요 포인터란? 주소를변수로다루기위한주소변수 메모리의기억공간을변수로써사용하는것 포인터변수란데이터변수가저장되는주소의값을 변수로취급하기위한변수 C 3 포인터의개요 포인터변수및초기화 * 변수데이터의데이터형과같은데이터형을포인터 변수의데이터형으로선언 일반변수와포인터변수를구별하기위해

More information

untitled

untitled int i = 10; char c = 69; float f = 12.3; int i = 10; char c = 69; float f = 12.3; printf("i : %u\n", &i); // i printf("c : %u\n", &c); // c printf("f : %u\n", &f); // f return 0; i : 1245024 c : 1245015

More information

슬라이드 1

슬라이드 1 CHAP 6: 큐 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 (front) 후단 (rear) 큐 ADT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element 형으로구성된요소들의순서있는모임

More information

이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다. 2

이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다. 2 제 17 장동적메모리와연결리스트 유준범 (JUNBEOM YOO) Ver. 2.0 jbyoo@konkuk.ac.kr http://dslab.konkuk.ac.kr 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다. 이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다.

More information

Microsoft PowerPoint - 알고리즘_5주차_1차시.pptx

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

More information

EA0015: 컴파일러

EA0015: 컴파일러 5 Context-Free Grammar 무엇을공부하나? 앞에서배운 " 정규식 " 은언어의 " 어휘 (lexeme)" 를표현하는도구로사용되었다. 언어의 " 구문 (syntax)" 은 " 정규언어 " 의범위를벗어나기때문에 " 정규식 " 으로표현이불가능하다. 본장에서배우는 " 문맥자유문법 " 은언어의 " 구문 (syntax)" 을표현할수있는도구이다. 어떤 " 문맥자유문법

More information

Microsoft PowerPoint - 제4장-스택과큐.pptx

Microsoft PowerPoint - 제4장-스택과큐.pptx 제 4 강의. 스택과큐자료구조 1 제 4 강. 스택과큐자료구조 학습목차 1. 스택과큐자료구조 2. 스택자료구조 3. 큐자료구조 4. 원형큐의구현 2 1. 스택 (Stack) 과큐자료구조 리스트, 스택과큐 (Stack and Queue) 스택과큐는리스트자료구조의특별한경우이다. 리스트 - 순서가있다 - 읽기, 삽입 (insert) 과삭제 (delete) 를리스트의어느곳에서나행함

More information

슬라이드 1

슬라이드 1 CHAP 7: 트리 yicho@gachon.ac.kr 1 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 리스트, 스택, 큐등은선형구조 트리는부모 - 자식관계의노드들로이루어진다. 응용분야 : 계층적인조직표현 컴퓨터디스크의디렉토리구조 인공지능에서의결정트리 (decision tree) 2 2 회사의조직 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀생산

More information

슬라이드 제목 없음

슬라이드 제목 없음 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

More information

자연언어처리

자연언어처리 제 7 장파싱 파싱의개요 파싱 (Parsing) 입력문장의구조를분석하는과정 문법 (grammar) 언어에서허용되는문장의구조를정의하는체계 파싱기법 (parsing techniques) 문장의구조를문법에따라분석하는과정 차트파싱 (Chart Parsing) 2 문장의구조와트리 문장 : John ate the apple. Tree Representation List

More information

adfasdfasfdasfasfadf

adfasdfasfdasfasfadf C 4.5 Source code Pt.3 ISL / 강한솔 2019-04-10 Index Tree structure Build.h Tree.h St-thresh.h 2 Tree structure *Concpets : Node, Branch, Leaf, Subtree, Attribute, Attribute Value, Class Play, Don't Play.

More information

PowerPoint Presentation

PowerPoint Presentation 자바프로그래밍 1 배열 손시운 ssw5176@kangwon.ac.kr 배열이필요한이유 예를들어서학생이 10 명이있고성적의평균을계산한다고가정하자. 학생 이 10 명이므로 10 개의변수가필요하다. int s0, s1, s2, s3, s4, s5, s6, s7, s8, s9; 하지만만약학생이 100 명이라면어떻게해야하는가? int s0, s1, s2, s3, s4,

More information

Algorithms

Algorithms 자료구조 & 알고리즘 리스트 (List) Seo, Doo-okok clickseo@gmail.com http://www.clickseo.com 목 차 선형리스트 연결리스트 2 선형리스트 선형리스트 선형리스트의개념 선형리스트의구현 연결리스트 3 선형리스트개념 리스트 (List) 목록, 대부분의목록은도표 (Table) 형태로표시 추상자료형리스트는이러한목록또는도표를추상화한것

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 System Software Experiment 1 Lecture 5 - Array Spring 2019 Hwansoo Han (hhan@skku.edu) Advanced Research on Compilers and Systems, ARCS LAB Sungkyunkwan University http://arcs.skku.edu/ 1 배열 (Array) 동일한타입의데이터가여러개저장되어있는저장장소

More information

<4D F736F F F696E74202D FBFACB0E120C0DAB7E1B1B8C1B6205BC8A3C8AF20B8F0B5E55D>

<4D F736F F F696E74202D FBFACB0E120C0DAB7E1B1B8C1B6205BC8A3C8AF20B8F0B5E55D> 연결자료구조 IT CookBook, C 로배우는쉬운자료구조 ( 개정판 ) Contents 학습목표 연결자료구조를이해한다. 순차자료구조와연결자료구조의차이와장단점을알아본다. 연결리스트의종류와특징을알아본다. 연결자료구조를이용한다항식의덧셈연산방법을알아본다. 내용 배열연결자료구조를이해한다. 순차자료구조와연결자료구조의차이와장단점을알아본다. 연결리스트의종류와특징을알아본다.

More information

Chapter 08. 트리(Tree)

Chapter 08. 트리(Tree) 윤성우의열혈자료구조 : C 언어를이용한자료구조학습서 Chapter 08. 트리 (Tree) Introduction To Data Structures Using C Chapter 08. 트리 (Tree) Chapter 08-1: 트리의개요 트리의접근과이해 트리는계층적관계 (Hierarchical Relationship) 를표현하는자료구조이다. 트리의예 트리의예

More information

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

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

More information

PowerPoint 프레젠테이션

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. 부-노드,

More information

e-비즈니스 전략 수립

e-비즈니스 전략 수립 트리 IT CookBook, C 로배우는쉬운자료구조 ( 개정판 ) Contents 학습목표 트리의개념을이해한다. 이진트리의자료구조를알아본다. 이진트리에서의순회를이해한다. 이진탐색트리의개념을이해하고연산방법을이해한다. 히프의자료구조를이해한다. 내용 트리 이진트리 이진트리의구현 이진트리의순회 이진탐색트리 히프 2/104 1. 트리 트리 (tree) 원소들간에 1:

More information

gnu-lee-oop-kor-lec11-1-chap15

gnu-lee-oop-kor-lec11-1-chap15 어서와 Java 는처음이지! 제 15 장컬렉션 컬렉션 (collection) 은자바에서자료구조를구현한클래스 자료구조로는리스트 (list), 스택 (stack), 큐 (queue), 집합 (set), 해쉬테이블 (hash table) 등이있다. 자바는컬렉션인터페이스와컬렉션클래스로나누어서제공한다. 자바에서는컬렉션인터페이스를구현한클래스도함께제공하므로이것을간단하게사용할수도있고아니면각자필요에맞추어인터페이스를자신의클래스로구현할수도있다.

More information

02장.배열과 클래스

02장.배열과 클래스 ---------------- DATA STRUCTURES USING C ---------------- CHAPTER 배열과구조체 1/20 많은자료의처리? 배열 (array), 구조체 (struct) 성적처리프로그램에서 45 명의성적을저장하는방법 주소록프로그램에서친구들의다양한정보 ( 이름, 전화번호, 주소, 이메일등 ) 를통합하여저장하는방법 홍길동 이름 :

More information

11장 포인터

11장 포인터 누구나즐기는 C 언어콘서트 제 9 장포인터 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습한다. 포인터란? 포인터 (pointer): 주소를가지고있는변수 메모리의구조 변수는메모리에저장된다. 메모리는바이트단위로액세스된다. 첫번째바이트의주소는 0, 두번째바이트는 1, 변수와메모리

More information

Microsoft PowerPoint - 자료구조2008Chap07

Microsoft PowerPoint - 자료구조2008Chap07 제 7 장트리 7.1 트리의정의 1 Tree 비선형구조, 다차원적구조 원소마다다음에여러개의원소가존재 하나이상의노드로구성된유한집합 정의1 : 루트 (root) 라는특별한노드를가지는사이클이존재치않는그래프 (acyclic graph) 정의 2 : 하나이상의노드로구성된유한집합 루트 (root) 라는특별한노드존재 나머지노드들은다시각각의트리이면서교차하지않는분리집합 (disjoint

More information

1장. 리스트

1장. 리스트 01. 순차탐색 02. 이진탐색 03. 이진탐색트리 04. 레드블랙트리 탐색 (search) 기본적으로여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요. 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열, 연결리스트, 트리, 그래프등 탐색키데이터 순차탐색 (sequential

More information

q 이장에서다룰내용 1 연결자료구조방식 2 단순연결리스트 3 원형연결리스트 4 이중연결리스트 3 다항식의연결자료구조표현 2

q 이장에서다룰내용 1 연결자료구조방식 2 단순연결리스트 3 원형연결리스트 4 이중연결리스트 3 다항식의연결자료구조표현 2 연결자료구조표현방식 IT CookBook, 자바로배우는쉬운자료구조 q 이장에서다룰내용 1 연결자료구조방식 2 단순연결리스트 3 원형연결리스트 4 이중연결리스트 3 다항식의연결자료구조표현 2 q 연결자료구조 v 순차자료구조의문제점 삽입연산이나삭제연산후에연속적인물리주소를유지하기위해서원소들을이동시키는추가적인작업과시간소요 Ø 원소들의이동작업으로인한오버헤드는원소의개수가많고삽입

More information

OCW_C언어 기초

OCW_C언어 기초 초보프로그래머를위한 C 언어기초 4 장 : 연산자 2012 년 이은주 학습목표 수식의개념과연산자및피연산자에대한학습 C 의알아보기 연산자의우선순위와결합방향에대하여알아보기 2 목차 연산자의기본개념 수식 연산자와피연산자 산술연산자 / 증감연산자 관계연산자 / 논리연산자 비트연산자 / 대입연산자연산자의우선순위와결합방향 조건연산자 / 형변환연산자 연산자의우선순위 연산자의결합방향

More information

비트와바이트 비트와바이트 비트 (Bit) : 2진수값하나 (0 또는 1) 를저장할수있는최소메모리공간 1비트 2비트 3비트... n비트 2^1 = 2개 2^2 = 4개 2^3 = 8개... 2^n 개 1 바이트는 8 비트 2 2

비트와바이트 비트와바이트 비트 (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,

More information

금오공대 컴퓨터공학전공 강의자료

금오공대 컴퓨터공학전공 강의자료 C 프로그래밍프로젝트 Chap 14. 포인터와함수에대한이해 2013.10.09. 오병우 컴퓨터공학과 14-1 함수의인자로배열전달 기본적인인자의전달방식 값의복사에의한전달 val 10 a 10 11 Department of Computer Engineering 2 14-1 함수의인자로배열전달 배열의함수인자전달방식 배열이름 ( 배열주소, 포인터 ) 에의한전달 #include

More information

<322EBCF8C8AF28BFACBDC0B9AEC1A6292E687770>

<322EBCF8C8AF28BFACBDC0B9AEC1A6292E687770> 연습문제해답 5 4 3 2 1 0 함수의반환값 =15 5 4 3 2 1 0 함수의반환값 =95 10 7 4 1-2 함수의반환값 =3 1 2 3 4 5 연습문제해답 1. C 언어에서의배열에대하여다음중맞는것은? (1) 3차원이상의배열은불가능하다. (2) 배열의이름은포인터와같은역할을한다. (3) 배열의인덱스는 1에서부터시작한다. (4) 선언한다음, 실행도중에배열의크기를변경하는것이가능하다.

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 제 2 장연결리스트 리스트 일반적인리스트 (List) 는일련의동일한타입의항목 (item) 들 실생활의예 : 학생명단, 시험성적, 서점의신간서적, 상점의판매품목, 실시간급상승검색어, 버킷리스트등 일반적인리스트의구현 : - 1 차원파이썬리스트 (list) - 단순연결리스트 - 이중연결리스트 - 원형연결리스트 2.1 단순연결리스트 단순연결리스트 (Singly Linked

More information

슬라이드 1

슬라이드 1 Data Structure & Algorithms SANGJI University KO Kwangman () 자료 (data) 1. 자료와정보 현실세계로부터의단순한관찰이나측정을통하여수집한사실이나개념의값들또는값들의집합. 정보 (information) 의사결정에도움을주기위해유용한형태로다시작성된 (= 가공 ) 자료. Data Structure & Algorithms

More information

슬라이드 1

슬라이드 1 Data Structure Chapter 1. 자료구조와알고리즘 Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr 자료구조와알고리즘 일상생활에서의사물의조직화 해야할일리스트 조직도 일상생활에서의사물의조직화 사전 Ticket Box 3 일상생활과자료구조의비교 일상생활 vs 자료구조 자료구조 스택 큐 리스트 사전, 탐색구조

More information

Data Structure

Data Structure Function & Pointer C- 언어의활용을위한주요기법 (3) Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr 함수의인자전달 함수의인자전달 함수의인자전달방식 인자전달의기본방식은복사다. 함수호출시전달되는값을매개변수를통해서전달받는데, 이때에값의복사가일어난다. int main(void) int val = 10;

More information

o 스택 (stack) ~ 쌓아놓은더미 1. 스택의개요 - 2 -

o 스택 (stack) ~ 쌓아놓은더미 1. 스택의개요 - 2 - 스택 (stack) SANGJI University Kwangman Ko o 스택 (stack) ~ 쌓아놓은더미 1. 스택의개요 - 2 - o 스택의특징 ~ 모든원소의삽입과삭제가 top 이라는자료구조의한쪽끝에서만수행되는제한된리스트구조 ~ 후입선출 (Last-In-First-Out, LIFO) 방식 가장마지막에입력된자료가가장먼저출력 o 스택의동작 ~ top 에서만삽입

More information

Microsoft PowerPoint - ch08_큐 [호환 모드]

Microsoft PowerPoint - ch08_큐 [호환 모드] 큐 (Queue) 자바로배우는쉬운자료구조 이장에서다룰내용 1 큐 2 큐의구현 3 큐의응용 2 큐 (1) 큐 (Queue) 스택과마찬가지로삽입과삭제의위치가제한된유한순서리스트 큐의뒤에서는삽입만하고, 앞에서는삭제만할수있는구조 삽입한순서대로원소가나열되어가장먼저삽입 (First-In) 한원소는맨앞에있다가가장먼저삭제 (First-Out) 된다. 선입선출구조 (FIFO,

More information

JAVA 프로그래밍실습 실습 1) 실습목표 - 메소드개념이해하기 - 매개변수이해하기 - 새메소드만들기 - Math 클래스의기존메소드이용하기 ( ) 문제 - 직사각형모양의땅이있다. 이땅의둘레, 면적과대각

JAVA 프로그래밍실습 실습 1) 실습목표 - 메소드개념이해하기 - 매개변수이해하기 - 새메소드만들기 - Math 클래스의기존메소드이용하기 (   ) 문제 - 직사각형모양의땅이있다. 이땅의둘레, 면적과대각 JAVA 프로그래밍실습 실습 1) 실습목표 - 메소드개념이해하기 - 매개변수이해하기 - 새메소드만들기 - Math 클래스의기존메소드이용하기 ( http://java.sun.com/javase/6/docs/api ) 문제 - 직사각형모양의땅이있다. 이땅의둘레, 면적과대각선의길이를계산하는메소드들을작성하라. 직사각형의가로와세로의길이는주어진다. 대각선의길이는 Math클래스의적절한메소드를이용하여구하라.

More information

ABC 10장

ABC 10장 10 장구조체와리스트처리 0 자기참조구조체 자기참조구조체는자기자신의형을참조하는포인터멤버를가짐 이러한자료구조를동적자료구조라고함 배열이나단순변수는일반적으로블록을진입할때메모리할당을받지만, 동적자료구조는기억장소관리루틴을사용하여명시적으로메모리할당을요구함 10-1 자기참조구조체 10-2 자기참조구조체 예제 struct list { int struct list a; data;

More information

슬라이드 1

슬라이드 1 컬렉션프레임워크 (Collection Framework) 의정의 - 다수의데이터를쉽게처리할수있는표준화된방법을제공하는클래스들 - 데이터의집합을다루고표현하기위한단일화된구조 (architecture) - JDK 1.2 이전까지는 Vector, Hashtable, Properties와같은컬렉션클래스로서로다른각자의방식으로처리 - 컬렉션프레임워크는다수의데이터를다루는데필요한다양하고풍부한클래스들을제공하므로프로그래머의부담을상당부분덜어준다.

More information

chap x: G입력

chap x: G입력 재귀알고리즘 (Recursive Algorithms) 재귀알고리즘의특징 문제자체가재귀적일경우적합 ( 예 : 피보나치수열 ) 이해하기가용이하나, 비효율적일수있음 재귀알고리즘을작성하는방법 재귀호출을종료하는경계조건을설정 각단계마다경계조건에접근하도록알고리즘의재귀호출 재귀알고리즘의두가지예 이진검색 순열 (Permutations) 1 장. 기본개념 (Page 19) 이진검색의재귀알고리즘

More information

학습목차 2.1 다차원배열이란 차원배열의주소와값의참조

학습목차 2.1 다차원배열이란 차원배열의주소와값의참조 - Part2- 제 2 장다차원배열이란무엇인가 학습목차 2.1 다차원배열이란 2. 2 2 차원배열의주소와값의참조 2.1 다차원배열이란 2.1 다차원배열이란 (1/14) 다차원배열 : 2 차원이상의배열을의미 1 차원배열과다차원배열의비교 1 차원배열 int array [12] 행 2 차원배열 int array [4][3] 행 열 3 차원배열 int array [2][2][3]

More information