제 7 장 정렬
|
|
- 우석 추
- 5 years ago
- Views:
Transcription
1 제 7 장 정렬 Copyright 2007 DBLAB, Seoul National University
2 탐색 (1) 용어정리 리스트 : 하나이상의필드로된레코드의집합 키 (Key) : 레코드를구분하기위해서사용되는필드 순차탐색 (Sequential Search) 레코드리스트를왼편에서오른편또는오른편에서왼편으로레코드를검사하는것 Copyright 2007 DBLAB, Seoul National University 2
3 탐색 (2) template <class E, class K> int SeqSearch(E *a, const int n, const K& k) {// a[1:n] 을왼쪽에서오른쪽으로탐색한다. // a[i] 의키값이 k 와같은가장작은 i 를반환한다. // 그런 i 가없으면, 0 을반환한다. int i; for(i = 1; i <= n && a[i]!= k; i++); if(i>n) return 0; return i; } 순차탐색 n 개의레코드를가진리스트를탐색하기위해 O(n) 의시간이걸린다. 성공적인탐색을위한평균키비교횟수 (1 i n) ( n i 1) / n ( n 1) / 2 Copyright 2007 DBLAB, Seoul National University 3
4 탐색 (3) 이원탐색 (Binary Search) n 개의레코드를가진리스트를탐색하기위해 O(log n) 시간이걸림. ( 순차탐색보다빠르다 ) SeqSearch 코드를이원탐색에맞게수정 for 조건부분을 i<=n && a[i] < k 로변경 조건 i>n 을 i>n a[i]!= k 로함께변경 순차나이원탐색방법은실제로사람이사용하는탐색방법과대응되지않는다. Copyright 2007 DBLAB, Seoul National University 4
5 탐색 (4) 보간법 (interpolation) 에의한탐색 리스트가정렬되었을때만사용가능 탐색의성질은리스트에있는키의분포에달려있음 리스트를반복해서탐색할때리스트를정렬된상태로유지하는것이이롭다. Copyright 2007 DBLAB, Seoul National University 5
6 두개의레코드리스트의비교 미국국세청 (IRS) 에서고용주와피고용자에게개별적으로받은신고서들을비교하여모순점이있는지를검증하려함 IRS 에서받는신고서들 고용주는피고용자에게얼마를지급하였다고신고 피고용자는고용주로부터얼마를지급받았다고신고 고용주와피고용자에관련된두개의레코드리스트가생겨남 IRS 에도착되는신고서는임의순서대로접수 리스트의레코드역시임의순서대로배열되어있다고가정 키는피고용자의사회보장번호 ( 가정 ) (1) 고용주리스트에있는키와대응디는레코드가피고용자리스트에없으면메시지를피고용자에게보냄 (2) (1) 과반대인경우메시지를고용주에게보냄 (3) 같은키를가진두레코드사이에모순점이없으면이결과에대한메시지를출력 Copyright 2007 DBLAB, Seoul National University 6
7 순차탐색으로두리스트검증 함수 Verify1 두개의비정렬리스트를직접비교해서검증문제해결 복잡도 : O(mn) (n, m 은각각고용자, 피고용자리스트의레코드수 ) void Verify1(Element *l1, Element *l2, const int n, const int m) {// 길이가 n 과 m 인비정렬리스트 l1 과 l2 를비교한다. bool *marked = new bool[m+1]; fill(marked+1, marked+m+1, false); } for(i=1; i<=n; i++) { int j = SeqSearch(l2, m, l1[i]); if(j==0) cout << l1[i] << not in l2 << endl; // (1) 을만족 else { if(!compare(l1[i],l2[j]) // (3) 을만족 cout << Discrepancy in << l1[i] << endl; marked[j] = true; // l2[j] 를검사한것으로표시 } } for(i=1; i<=m; i++) if(!marked[i]) cout << i2[i] << not in l1. << endl; // (2) 를만족 delete [] marked; Copyright 2007 DBLAB, Seoul National University 7
8 두리스트의빠른검증 함수 Verify2 두리스트를먼저정렬시킨다음비교 복잡도 : O(t sort (n) + t sort (m) + n + m) t sort (n): n 개의레코드를가진리스트를정렬하는데걸리는시간 연산시간 : O(max(nlogn, mlogm)) n 개의레코드를 O(nlogn) 시간에정렬할수있으므로 void Verify2(Element *l1, Element *;2, const int n, const int m) {// Verify1과같은작업을수행한다. 여기서는 l1과 l2를먼저정렬한다. Sort(l1, n); Sort(l2, m); // 키를오름차순으로정렬 int i = 1, j=1; while((i<=n) && (j<=m)) if(l[i] < l[j]) { cout << l1[i] << not in l2 << endl; i++; } else if(l[i]>l[j]) { cout << l2[j] << not in l1 << endl; j++; } else { // 같은키들 if(!compare(l1[i],l2[j])) cout << Discrepancy in << l1[i] << endl; i++; j++; } if(i<=n) OutputRest(l1, i, n, 1); // l1의레코드 i부터 n까지출력 else if(j<=m) OutputRest(l2,j,m,2); // l2의레코드 j부터 m까지출력 } Copyright 2007 DBLAB, Seoul National University 8
9 정렬의필요성 정렬의두가지중요한사용법 (1) 탐색에서보조로사용 (2) 리스트의엔트리를비교하는방법으로사용 정렬방법 (1) 내부방법 (internal methods) 정렬할리스트가작아서전체적인정렬이메인메모리상에서실행될수있을때사용 (2) 외부방법 (external methods) 큰리스트에사용 Copyright 2007 DBLAB, Seoul National University 9
10 삽입정렬 (1) 새로운레코드를 i 개의정렬된레코드리스트에끼워넣어크기가 i+1 인정렬된결과레코드리스트를만든다. template <class T> void Insert(const T& e, T *a, int i) {// e 를정렬된리스트 a[1:i] 에삽입하여결과 // 리스트 a[1:i+1] 도정렬되게한다. // 배열 a 는적어도 i+2 원소를포함할공간을가지고있어야한다. a[0] = e; while(e <a[i]) { a[i+1] = a[i]; i--; } a[i+1] = e; } 정렬된리스트로삽입 Copyright 2007 DBLAB, Seoul National University 10
11 삽입정렬 (2) template <class T> void InsertionSort(T* a, const int n) {// a[1:n] 을비감소순으로정렬 for(int j = 2; j <= n; j++) { T temp = a[j]; Insert(temp, a, j-1); } } Insert(e, a, i) 는최악의경우삽입전 i+1 번비교해야함 Insert 의복잡도 : O(i) InsertionSort 의복잡도 삽입정렬 i = j-1 = 1,2,...,n-1 일때 Insert 를호출 n 1 i 1 복잡도 : O( ( i 1) ) = O(n 2 ) Copyright 2007 DBLAB, Seoul National University 11
12 삽입정렬 (3) 삽입정렬의최악의예 입력리스트가역순이므로새로운레코드가정렬된부분에삽입될때마다전체정렬된부분이오른쪽으로이동 j [1] [2] [3] [4] [5] _ Copyright 2007 DBLAB, Seoul National University 12
13 삽입정렬 (4) n = 5, 입력키순서가 2, 3, 4, 5, 1 일경우 j = 2, 3, 4에대한시간 : O(1) j = 5에대한시간 : O(n) j [1] [2] [3] [4] [5] _ Copyright 2007 DBLAB, Seoul National University 13
14 삽입정렬 (5) 삽입정렬의변형 이원삽입정렬 Insert( 프로그램 7.4) 에서사용된순차탐색기법대신이원탐색을사용 삽입정렬에서수행하는비교횟수를줄인다 레코드이동횟수는변하지않음 연결삽입정렬 리스트의원소들을배열대신연결리스트로표현 링크필드만조정하면되므로레코드이동횟수가 0 Copyright 2007 DBLAB, Seoul National University 14
15 퀵정렬 (1) 평균성능이가장좋은정렬방법 퀵정렬 (Quick Sort) 단계 (1) 정렬할레코드중피벗 (pivot: 중추 ) 레코드를선택 (2) 정렬할레코드들을다시정돈 피벗의왼쪽 : 피벗의키보다작거나같은레코드들을위치시킴 피벗의오른쪽 : 피벗의키보다크거나같은레코드들을위치시킴 (3) 퀵정렬을순환적으로사용 피벗의왼쪽과오른쪽의레코드들은서로독립적으로정렬된다 Copyright 2007 DBLAB, Seoul National University 15
16 퀵정렬 (2) 키 (26, 5, 37, 1, 61, 11, 59, 15, 48, 19) 를가진 10 개의레코드로된리스트를퀵정렬을사용하여정렬 R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 9 R 10 left right [ ] 1 10 [ ] 26 [ ] 1 5 [ 1 5] 11 [19 15] 26 [ [19 15] 26 [ ] [ ] [48 37] 59 [61] [61] QuickSort 를호출할때마다의리스트상태대괄호는계속해서정렬할서브리스트를나타냄 Copyright 2007 DBLAB, Seoul National University 16
17 퀵정렬 (3) QuickSort 의분석 최악의경우복잡도 : O(n 2 ) 한레코드의위치가정확히정해질때마다그레코드의왼쪽과오른쪽의서브리스트크기가같을경우 크기가 n/2인두개의서브리스트를정렬하는작업과같다 크기가 n인리스트에서한레코드를위치시키는데필요한시간 : O(n) T(n) cn + 2T(n/2) 어떤상수 c에대해서 cn + 2(cn/2 + 2T(n/4)) 2cn + 4T(n/4)... cnlog 2 n + nt(1) = O(nlog 2 n) 평균연산시간 : O(nlogn) Copyright 2007 DBLAB, Seoul National University 17
18 퀵정렬 (4) 보조정리 7.1 T avg (n) 을함수 QuickSort 가 n 개의레코드를가진리스트를정렬하는데필요한예상시간이라하자그러면 n 2 에대해 T avg (n) knlog e n 을만족시키는상수 k 가존재한다. ( 증명 ) QuickSort(list, 1, n) 호출시, 피벗이 j 위치에놓이게됨 크기가각각 j-1, n-j인두개의서브리스트를정렬하는문제가됨 예상시간 : T avg (j-1) + T avg (n-j) j는 1에서부터 n까지의범위에서똑같은확률로임의의값을취하므로다음과같은식을얻을수있다. Copyright 2007 DBLAB, Seoul National University 18
19 퀵정렬 (5) ( 증명 ) 계속 어떤상수 b에대하여 T avg (0) b와 T avg (1) b 라고가정이제, n 2이고 k=2(b+c) 인경우, T avg (n) knlog e n임을증명 귀납기초 : n=2인경우 (7.1) 식에의해 Tavg(2) 2c+2b knloge2 귀납가정 : 1 n < m에대해 Tavg(n) knlogen라고가정 귀납단계 : 식 (7.1) 과귀납가정에의해 jlog e j 가 j 에대한증가함수이므로식 (7.2) 는다음과같이된다. Copyright 2007 DBLAB, Seoul National University 19
20 퀵정렬 (6) 퀵정렬과스택공간 퀵정렬은순환 (recursion) 을구현하기위해스택공간필요 리스트가균등하게나뉘는경우 최대순환깊이는 log n 이되어스택공간으로 O(log n) 필요 최악의경우 순환의각단계에서, 크기가 n-1 인왼쪽서브리스트와크기가 0 인오른쪽서브리스트로리스트가나뉘는경우 순환깊이는 n 이되어스택공간으로 O(n) 필요 보다작은크기의서브리스트를먼저정렬하여스택공간을점근적으로감소시킬수있다. Copyright 2007 DBLAB, Seoul National University 20
21 퀵정렬 (7) 세 - 값의 - 메디안을사용한퀵정렬 (Quick Sort using a median-of-three) 피벗으로현재서브리스트에있는첫번째, 중앙, 마지막키중에서메디안을사용 pivot = median{k left, K (left+right)/2, K right } Copyright 2007 DBLAB, Seoul National University 21
22 얼마나빠르게정렬할수있는가? (1) 키에대한비교와교환연산만이허용된다는제약하에가장좋은정렬시간은 O(nlogn) 이라는정리를증명 Yes K 1 K 2 [1,2,3] No [1,2,3] K 2 K 3 K 1 K 3 [2,1,3] Yes No Yes No [1,2,3] stop K 1 K 3 [1,3,2] [2,1,3] stop K 2 K 3 [2,3,1] Yes No Yes No [1,3,2] stop stop [3,1,2] [2,3,1] stop stop [3,2,1] 삽입정렬에대한결정트리 결정트리 (decision tree) : 각노드가하나의키비교연산을나타내고간선은비교결과를나타내는트리 Copyright 2007 DBLAB, Seoul National University 22
23 얼마나빠르게정렬할수있는가? (2) 정리 7.1: n개의서로다른원소들을정렬하는결정트리의높이는적어도 log 2 (n!)+1이된다. 증명 : n개의원소정렬시 n! 개의서로다른결과가가능 정렬을위한결정트리는최소 n! 개의리프노드를가져야함 결정트리의높이는적어도 log 2 (n!)+1 계 : 비교만으로정렬하는알고리즘은최악의경우 Ω(nlogn) 연산시간을가짐 증명 : n! 개의리프노드를갖는모든결정트리는길이가 c n log 2 n인경로가존재함을보여야함 (c는상수 ) 정리에의해결정트리에는길이가 log 2 n! 인경로가있음. n! = n(n-1)(n-2),, (3)(2)(1) (n/2) n/2 log 2 n! (n/2)log 2 (n/2) = Ω(nlogn) Copyright 2007 DBLAB, Seoul National University 23
24 합병정렬 (1) 합병 (Merging) 두개의정렬된리스트를하나의정렬된리스트로합병 template <class T> void Merge(T *initlist, T *mergedlist, const int l, const int m, const int n) { // initlist[1:m] 과 initlist[m+1:n] 는정렬된리스트. // 이들은정렬된리스트 mergedlist[1:n] 으로합병된다. for(int i1 = l, iresult = l, i2 = m+1; //i1, i2 와 iresult 는리스트위치 i1 <= m && i2 <= n; // 어떤입력리스트도소진되지않음 iresult++) if(initlist[i1] <= initlist[i2]) { mergedlist[iresult] = initlist[i1]]; i1++; } else{ mergedlist[iresult] = initlist[i2]; i2++; } // 첫번째리스트의나머지레코드 ( 있다면 ) 복사 copy(initlist + i1, initlist + m + 1, mergedlist + iresult); } // 두번째리스트의나머지레코드 ( 있다면 ) 복사 copy(initlist + i2.initlist + n _1, mergedlist + iresult); 합병시간 : O(n-l+1) n-l+1 : 합병될레코드수 Copyright 2007 DBLAB, Seoul National University 24
25 합병정렬 (2) 반복합병정렬 (Iterative Merge Sort) 입력리스트를길이가 1 인 n 개의정렬된서브리스트로간주 반복합병정렬단계 첫번째합병단계 : 리스트들을쌍으로합병하여크기가 2 인 n/2 개의리스트를얻는다. n 이홀수이면리스트하나는크기가 1 두번째합병단계 : n/2 개의리스트를다시쌍으로합병하여 n/4 개의리스트를얻는다. 합병단계는하나의서브리스트가남을때까지계속된다. 한번합병할때마다서브리스트의수는반으로줄어든다. Copyright 2007 DBLAB, Seoul National University 25
26 합병정렬 (3) 반복합병정렬의예 입력리스트 : (26, 5, 77, 1, 61, 11, 59, 15, 48, 19) 각단계에서합병되는서브리스트를합병트리로나타낸것 Copyright 2007 DBLAB, Seoul National University 26
27 합병정렬 (4) 합병정렬은여러개의합병단계 (pass) 로구현된다. template <class T> void MergePass(T *initlist, T *resultlist, const int n, const int s) { // 길이가 s 인서브리스트의인접쌍들이 // initlist 에서부터 resultlist 로합병된다. n 은 initlist 에있는레코드수이다. for(int i = 1; // i 는합병되는리스트의첫번째리스트의첫번째위치 i <= n-2*s+1; // 길이가 s 인두서브리스트를위해원소들이충분한지? i+= 2*s) Merge(initList, resultlist, i, i+s-1, i+2*s-1); } // 2*s 보다작은나머지리스트를합병 if((i+s-1)<n) Merge(initList, resultlist, i, i+s-1, n); else copy(initlist+i, initlist+n+1, resultlist+i); 합병패스 Copyright 2007 DBLAB, Seoul National University 27
28 합병정렬 (5) template <class T> void MergeSort(T *a, const int n) { // a[1:n] 을비감소순으로정렬한다. T *templist = new T[n+1]; // l 은현재합병되고있는서브리스트의길이이다. for(int l=1; l<n; l*=2) { MergePass(a, templist, n, l); l *= 2; MergePass(tempList, a, n, l); // list 와 templist 의역할을교환 } delete [] templist; } MergeSort 분석 i번째패스 : 크기가 2 i-1 인리스트를합병 총 log 2n 단계가데이타에적용된다. 합병의각단계에걸리는시간 : O(n) 총연산시간 : O(nlogn) Copyright 2007 DBLAB, Seoul National University 28
29 합병정렬 (6) 순환합병정렬 (Recursive Merge Sort) 정렬할리스트를거의똑같이두개로나눈다. left 서브리스트와 right 서브리스트 서브리스트들은순환적으로정렬된다. 정렬된서브리스트들은합병된다. Copyright 2007 DBLAB, Seoul National University 29
30 합병정렬 (7) 순환적합병정렬의서브리스트분할 입력리스트 : (26, 5, 77, 1, 61, 11, 59, 15, 49, 19) Copyright 2007 DBLAB, Seoul National University 30
31 합병정렬 (7) 순환적합병정렬의서브리스트분할 두개의서브리스트를만든다 left ~ ( left right) / 2, ( left right) / 2 +1~ right 정수배열 link[1:n] 을사용 함수 Merge 가사용될때일어나는레코드복사를제거하기위하여정수포인터를각레코드에연관시키기위함 list[i] - 정렬된서브리스트에서레코드 i 다음에있는레코드 이배열의사용으로레코드복사는링크변경으로대체되고정렬함수의실행시간은레코드크기 s 에독립적이됨 필요한추가공간 : O(n) 반복적합병정렬은 O(snlogn) 시간과 O(sn) 추가공간필요 최종체인이결정하는정렬순서로레코드들을물리적으로재정돈해야하는후처리필요 Copyright 2007 DBLAB, Seoul National University 31
32 합병정렬 (8) 순환합병정렬구현 template <class T> Int rmergesort(t* a, int* link, const int left, const int right) {// 정렬할리스트는 a[left:right]. 초기에 link[i] 는모든 i 에대해 0 이다. // rmergesort 는정렬된체인의첫번째원소의인덱스를반환한다. if(left >= right) return left; int mid = (left + right)/2; return ListMerge(a, link, rmergesort(a, link, left, mid), // 왼쪽반을정렬 rmergesort(a, link, mid+1, right)); // 오른쪽반을정렬 } rmergesort 의분석 합병정렬의순환버전 안정적 연산시간 : O(nlogn) 순환합병정렬 Copyright 2007 DBLAB, Seoul National University 32
33 합병정렬 (9) 합병정렬의변형 자연합병정렬 (Natural Merge Sort) 입력리스트내에이미존재하고있는순서를고려 이미정렬되어있는레코드의서브리스트를식별할수있도록초기패스를만들어야함 자연합병정렬 Copyright 2007 DBLAB, Seoul National University 33
34 히프정렬 (1) 합병정렬의문제점 정렬한레코드수에비례하여저장공간이추가로필요 히프정렬 (heap sort) 일정한양의저장공간만추가로필요 최악의경우연산시간과평균연산시간 : O(nlogn) O(n) 의추가저장공간을사용하는합병정렬보단약간느리지만 O(1) 의추가저장공간을사용하는합병정렬보다빠름 최대 - 히프구조사용 최대 - 히프와연관된삭제, 삽입함수 : O(nlogn) 정렬방법 Adjust 함수사용 최대히프를재조정 Copyright 2007 DBLAB, Seoul National University 34
35 히프정렬 (2) Adjust 함수 왼쪽및오른쪽서브트리가모두히프인이진트리에서시작하여이진트리전체가최대히프가되도록재조정 연산시간 : O(d) (d 는트리의깊이 ) template <class T> void Adjust (T *a, const int root, const int n) { // 루트 root 를가진이진트리를히프성질을만족하도록조정한다. } // root 의왼쪽과오른쪽서브트리는히프성질을이미만족한다. // 어떤노드도 n 보다큰인덱스를갖지않는다. T e= a[root]; //e 에대한적절한위치를탐색 for(int j=2*root; j<=n; j*=2) { } if(j<n &&.a[j] < a[j+1]) j++; // j 는부모의최대자식 if(e >= a[j]) break; // e 는 j 의부모로삽입 a[j/2]= a[j]; // j 번째레코드를트리위로이동 a[j/2]=e; 최대히프의조정 Copyright 2007 DBLAB, Seoul National University 35
36 히프정렬 (3) template <class T> void HeapSort(T *a, const int n) {// a[1:n] 을비감소순으로정렬한다. for(int i=n/2; i>=1; i--) // 히프로조정 Adjust(a,i,n); } for(i=n-1; i>=1;i--) // 정렬 { swap(a[1], a[i+1]); // 현히프의처음과마지막을교환 Adjust(a, 1, i); // 히프로조정 } 정렬과정 Adjust를반복적으로호출 최대히프구조를만든다. 히프의첫번째레코드와마지막레코드를교환한다. 최대키를가진레코드가정렬된배열의정확한위치에자리잡게됨 히프의크기를줄인후히프를재조정한다. 전체연산시간 : O(nlogn) Copyright 2007 DBLAB, Seoul National University 36
37 히프정렬 (4) 이진트리로변환된배열 입력리스트 : (26, 5, 77, 1, 61, 11, 59, 15, 48, 19) [1] 26 [1] 77 [2] 5 [3] 77 [2] 61 [3] 59 [4] 1 [5] [4] 48 [5] [6] [7] [6] [7] [8] [9] [10] [8] [9] [10] (a) 입력리스트를이진트리로변환한모습 (b) 초기히프형태로구성한것 (HeapSort 코드의첫번째 for 루프를 거친후의최대히프모습 ) Copyright 2007 DBLAB, Seoul National University 37
38 히프정렬 (5) [1] 61 [1] 59 [2] 48 [3] 59 [2] 48 [3] 26 [4] 15 [5] [4] 15 [5] [6] [7] [6] [7] 5 1 [8] [9] (a) 히프크기 =9 Sorted = [77] 5 [8] (b) 히프크기 =8 Sorted = [61,77] [1] 48 [1] 26 [2] 19 [3] 26 [2] 19 [3] 11 [4] 15 [5] [4] 15 [5] 5 1 (c) 히프크기 =7 [6] [7] (d) 히프크기 =6 [6] Sorted = [59,61,77] Sorted = [48,59,61,77] Copyright 2007 DBLAB, Seoul National University 38
39 히프정렬 (6) [1] 19 [1] 15 [2] 15 [3] 11 [2] 5 [3] [4] [5] (e) 히프크기 =5 Sorted = [26,48,59,61,77] 1 [4] (f) 히프크기 =5 Sorted = [19,26,48,59,61,77] [1] (g) 히프크기 =3 Sorted = [15,19,26,48,59,61,77] [2] [3] Copyright 2007 DBLAB, Seoul National University 39
40 여러키에의한정렬 (1) K 1,K 2,...,K t (K 1 은최대유효키, K t 는최소유효키 ) 의여러개의키를갖는레코드의정렬 모든레코드쌍 i, j 에대하여 t 1 i<j, ( Ki,..., Ki ) ( K j,..., K 키 K 1,...,K t 로정렬된것 1 t j ) 이성립하면레코드 R 1,...,R n 의리스트는 카드뭉치를정렬하는문제 두개의키 ( 무늬, 숫자 ) 에대한정렬문제 K 1 [ 무늬 ] : < < < K 2 [ 숫자 ] : 2<3<4<...<10<J<Q<K<A 정렬된카드뭉치 2,...,A,...,2,...,A Copyright 2007 DBLAB, Seoul National University 40
41 여러키에의한정렬 (2) MSD(most-significant-digit-first) 정렬 최대유효숫자우선정렬 먼저최대유효키 K 1 으로정렬 K 1 에대해같은값을가지는여러레코드파일 (pile) 들이만들어짐 각파일에대해독립적으로 K 2 로정렬 K 1,K 2 에대해같은값을가지는서브파일 (sub pile) 들이만들어짐 각서브파일에대해서는 K3 로정렬 최종적으로이렇게얻어진파일들을합친다. LSD(least-significant-digit-first) 정렬 최소유효숫자우선정렬 LSD 가 MSD 보다더단순 생성된파일과서브파일을독립적으로정렬할필요가없으므로 Copyright 2007 DBLAB, Seoul National University 41
42 여러키에의한정렬 (3) 기수 (radix) 정렬 어떤기수 r 을이용하여정렬키를몇개의숫자로분해 r = 10 : 키를십진수로분할 r = 2 : 키를이진수로분할 기수 -r 정렬에서는 r 개의빈 (bin) 이필요 (why?) 정렬되어야하는레코드가 R 1,...,R n 일때, 레코드의키는기수 -r 을이용하여분할 0~(r-1) 사이의 d 개의숫자를가진키가된다. 각빈의레코드는빈의첫레코드를가리키는포인터와마지막레코드를가리키는포인터를통해체인으로연결되며, 체인은큐처럼동작 Copyright 2007 DBLAB, Seoul National University 42
43 여러키에의한정렬 (4) RadixSort 의분석 : LSD 기수-r 방법을표현 전체연산시간 : O(d(n+r)) d 패스를처리하면서각패스의연산시간은 O(n+r) 임 r 의선택을달리하면연산시간이달라진다. Copyright 2007 DBLAB, Seoul National University 43
44 여러키에의한정렬 (5) 기수정렬의예 범위가 [0, 999] 인십진수를정렬 (d=3, r=10) a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] (a) 초기입력 e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] (b) 첫번째 - 패스큐들 (First-pass queues) 과결과체인 Copyright 2007 DBLAB, Seoul National University 44
45 여러키에의한정렬 (6) e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] (c) 두번째 - 패스큐들 (Second-pass queues) 과결과체인 Copyright 2007 DBLAB, Seoul National University 45
46 여러키에의한정렬 (7) e[0] e[1] e[2] e[3] e[4] e[5] e[6] e[7] e[8] e[9] f[0] f[1] f[2] f[3] f[4] f[5] f[6] f[7] f[8] f[9] (d) 세번째 - 패스큐들 (Third-pass queues) 과결과체인 Copyright 2007 DBLAB, Seoul National University 46
47 리스트정렬 (1) 많은레코드로된리스트를정렬할때는데이타의이동을최소화하도록해야함 합병정렬, 삽입정렬 순차리스트보다는연결리스트에동작하도록변경 추가적링크필요 물리적재배치대신링크필드만수정 반드시원하는정렬순서대로레코드를물리적으로재배치해야할경우 연결리스트정렬을먼저수행 리스트에명세된순서에따라레코드들을물리적으로재배치 재배치는추가공간을사용하여선형시간내에수행가능 Copyright 2007 DBLAB, Seoul National University 47
48 리스트정렬 (2) List 1 의분석 리스트에 n 개의레코드가있고, 각레코드가 m 워드로이루어져있을때 전체연산시간 : O(mn) 체인 first 를이중연결리스트로변환하는데 O(n) 시간 한번바꾸는데드는비용 ( 레코드의이동 ) : O(m) 최악의경우 : 3(n-1) 의레코드이동이일어남 R 1 <R 2 <...<R n, R 1 >R n 인경우 Copyright 2007 DBLAB, Seoul National University 48
49 리스트정렬 (3) 정렬된연결리스트의예 입력리스트 : (26, 5, 77, 1, 61, 11, 59, 15, 48, 19) i key linka R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 9 R (a) 리스트정렬을한연결리스트, first=4 i key linka linkb R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 9 R (b) 역방향링크를만든, (a) 에대응되는이중연결리스트, first=4 Copyright 2007 DBLAB, Seoul National University 49
50 리스트정렬 (4) List1 의예제 (1) i key linka linkb i key linka linkb R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 9 R (a) List1 의 for 루프의첫번째반복후의구성, first=2 R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 9 R (b) 두번째반복후의구성, first=6 Copyright 2007 DBLAB, Seoul National University 50
51 리스트정렬 (5) List1 의예제 (2) i key linka linkb R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 9 R (c) 세번째반복후의구성, first=8 i key linka linkb R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 9 R (d) 네번째반복후의구성, first=10 Copyright 2007 DBLAB, Seoul National University 51
52 리스트정렬 (6) 하나의링크필드만사용한레코드재배치 template <class T> void List2(T *a, int *link, const int n, int first) {// 두번째링크필드 linkb 가없는것만빼고 List1 과똑같다. for(int i=1; i<n; i++) {// i 번째위치에놓을정확한레코드를찾는다. 이레코드의인덱스는 i 이고, // 위치 1,2,...,i-1 인레코드는이미정확하게자리를잡고있다. while(first<i) first=link[first]; int q=link[first]; // a[q] 는정렬된순서에서다음레코드가된다. if(first!=i) {// a[first] 는 i 번째작은키이다. 레코드를 i 번째위치로이동한다. // 또한 a[i] 의새로운위치로링크를설정한다. swap(a[i], a[first]); link[first] = link[i]); link[i]=first; } first=q; } } M.D.MacLaren 이제시한방법으로 List1 을수정 링크필드를추가로필요로하지않음 first 가항상 i 보다크거나같아야함 Copyright 2007 DBLAB, Seoul National University 52
53 리스트정렬 (7) List2의예제 (1) 입력리스트 : (26, 5, 77, 1, 61, 11, 59, 15, 48, 19) 리스트정렬후그림 7.10(a) 와같은배치를얻음 i R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 9 R 10 key link (a) List2 의 for 루프의첫번째반복후의구성, first=2 i R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 9 R 10 key link (b) 두번째반복후의구성, first=6 i R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 9 R 10 key link (c) 세번째반복후의구성, first=8 Copyright 2007 DBLAB, Seoul National University 53
54 리스트정렬 (8) List2 의예제 (2) i key link R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 9 R List2 의분석 (d) 네번째반복후의구성, first=10 i R 1 R 2 R 3 R 4 R 5 R 6 R 7 R 8 R 9 R 10 key link (e) 다섯번째반복후의구성, first=1 레코드이동순서 : List1과동일 최악의경우 3(n-1) 의레코드이동 총비용 : O(nm) while 루프의전체연산시간 : O(n) List2 가 List1 보다공간과시간적인면에서우수 두레코드교환시 List1 이더많은일을해야함 Copyright 2007 DBLAB, Seoul National University 54
55 테이블정렬 (1) 리스트정렬기법은퀵정렬이나히프정렬에는적당하지않음 히프정렬에서는히프를순차적으로표현하는것이핵심 이러한정렬방법을위해 한레코드에대응하는한엔트리로구성된보조테이블 t를유지 테이블의엔트리는레코드의간접참조를할수있게함 테이블정렬 정렬시작시 : t[i]=i, 1 i n 정렬함수가 a[i] 와 a[j] 를교환해야한다면테이블의엔트리 t[i] 와 t[j] 만교환되게함 정렬끝나면 : a[t[1]] 은키가가장작은레코드 a[t[n]] 은키가가장큰레코드 정렬된레코드의순열 : a[t[1]], a[t[2]],...,a[t[n]] t 에나타난순열에따라레코드를물리적으로재배치해야될경우도있다. Copyright 2007 DBLAB, Seoul National University 55
56 테이블정렬 (2) 정렬전의보조테이블 t R 1 R 2 R 3 R 4 R 정렬이후의테이블 t 순열 t[0],t[1],...,t[n-1] 에대응하는레코드들을재배치하는함수 모든순열은분리된사이클로만들어짐 원소 i 에대한사이클 : i,t[i],t 2 [i],...,t k [i] (t j [i]=t[t j-1 [i]],t 0 [i]=1,t k [i]=i) 위의그림의순열 t는 R 1 과 R 5 를포함하는사이클과 R 4,R 3,R 2 를포함하는사이클을가짐 Copyright 2007 DBLAB, Seoul National University 56
57 테이블정렬 (3) template <class T> void Table(T *a, const int n, int *t) {// a[1:n] 을리스트 a[t[1]],...,a[t[n]], n 1 에대응되도록재배치한다. for(int i=1;i<n;i++) if(t[i]!=i) { // i 에서시작하는사이클이있다. T p=a[i]; int j=i; do { int k=t[j]; a[j]=a[k]; t[j]=j; j=k; } while(t[j]!=i); a[j]=p; //j 는레코드 p 를위한위치 t[j]=j; } } Table 함수 - 순열의사이클분해를이용 전체연산시간 : O(mn) Copyright 2007 DBLAB, Seoul National University 57
58 테이블정렬 (4) 테이블정렬의예 (a) 의테이블 t 를가지고시작한다고가정 key t R 1 R 2 R 3 R 4 R 5 R 6 R 7 R (a) 초기구성 key t (b) 첫번째사이클의재배치후구성 key t (c) 두번째사이클의재배치후구성 Copyright 2007 DBLAB, Seoul National University 58
59 내부정렬요약 (1) 내부정렬비교 삽입정렬 : 리스트가부분적으로정렬되어있을때좋음 작은 n에대해가장좋은정렬방법 합병정렬 : 최악의경우에가장좋은방법히프정렬에비해더많은공간을필요로함 퀵정렬 : 평균성능이가장좋음 / 최악의경우 : O(n 2 ) 기수정렬 : 성능이키의크기와 r의선택에영향을받음 방법 최악의경우 평균적인경우 삽입정렬 n 2 n 2 히프정렬 nlogn nlogn 합병정렬 nlogn nlogn 퀵정렬 n 2 nlogn 정렬방법들의비교 Copyright 2007 DBLAB, Seoul National University 59
60 내부정렬요약 (2) 512MB RAM 을가진 1.7GHz Intel Pentium 4 PC 와 Microsoft Visual Studio.NET 2003 으로얻은결과 n 삽입 히프 합병 퀵 정렬방법들에대한평균시간 Copyright 2007 DBLAB, Seoul National University 60
61 내부정렬요약 (3) 평균시간 ( 밀리초 ) 의그래프 퀵정렬이적절히큰 n에대해다른정렬방법보다성능이우수 50과 100 사이에삽입과퀵정렬이분리하는점 정확한분리점을 nbreak라할때 n<nbreak일때삽입정렬이가장좋은정렬방법 n>nbreak일때퀵정렬이가장좋은정렬방법 최악의경우 n>c에대해합병정렬이가장좋게보여짐 (c는어떤상수 ) n c 에대해서는삽입정렬이최악의경우가장좋다 Copyright 2007 DBLAB, Seoul National University 61
62 외부정렬 (1) 정렬하려는리스트전체가컴퓨터의메인메모리에모두올라갈수없다면내부정렬은사용할수없음 블록 (block) 한번에디스크로부터읽거나디스크에쓸수있는데이타의단위, 여러개의레코드들로구성됨 판독 / 기록시간에영향을미치는세가지요소 (1) 탐구시간 (Seek time) : 판독 / 기록헤드가디스크상의원하는실린더로이동하는데걸리는시간. 헤드가가로질러야하는실린더수에따라결정됨 (2) 회전지연시간 (Latency time) : 트랙의해당섹트가판독 / 기록헤드밑으로회전해올때까지걸리는시간 (3) 전송시간 (Transmission time) : 디스크로또는디스크로부터데이타블록을전송하는데걸리는시간 Copyright 2007 DBLAB, Seoul National University 62
63 외부정렬 (2) 합병정렬 외부저장장치에서정렬을할때, 가장널리알려진방법 : 합병정렬 (merge sort) 1 단계 2 단계 입력리스트의여러세그먼트들을좋은내부정렬방법으로정렬. 이정렬된세그먼트들을런 (run) 이라함. 런이생성되면외부저장장치에기록됨 1 단계에서만들어진런들을하나의런이될때까지합병트리형식을따라합병함 Copyright 2007 DBLAB, Seoul National University 63
64 외부정렬 (3) 최대 750 개의레코드만정렬할수있는내부메모리를가지고있는컴퓨터를이용하여 4500 개의레코드로된리스트를정렬 입력리스트는디스크에저장되어있고 250 레코드의블록길이를가지고있음 작업공간으로사용할또다른디스크를갖고있음 (1) 내부적으로한번에 3 개의블록 (750 개의레코드 ) 을 정렬해서여섯개의런 R1-R6 을만들고, 이런들을작업 디스크에수록 run 1 run 2 run 3 run 4 run 5 run 내부정렬후얻어진블록화된런 ( 한런당세블록 ) Copyright 2007 DBLAB, Seoul National University 64
65 외부정렬 (4) (2) 런들을합병 내부메모리에 250개의레코드를수용할수있는 3개의블록을마련 2개의블록은입력버퍼로쓰고하나는출력버퍼로씀 입력버퍼로각런으로부터블록하나씩읽어들임 런의블록들은입력버퍼에서출력버퍼로합병 출력버퍼가다차면디스크에기록됨 입력버퍼가공백이되면같은런에서다음블록을읽어들여다시채움 run 1 run 2 run 3 run 4 run 5 run 6 6 개런의합병 Copyright 2007 DBLAB, Seoul National University 65
66 외부정렬 (5) - 복잡도분석 표기법 t s = 최대탐구시간 t l = 최대회전지연시간 t rw = 250 개의레코드로구성된한블록을읽거나쓰는데걸리는시간 t IO = 한블록을입력또는출력하는데걸리는시간 = t s + t l + t rw t IS = 750 개의레코드를내부적으로정렬하는시간 nt m = 입력버퍼에서출력버퍼로 n 개의레코드를합병하는데걸리는시간 연산 시간 (1) 18 블록의입력판독 : 18t IO 36t IO +6t IS 내부정렬 : 6t IS 18 블록기록 : 18t IO (2) 1-6 런을쌍으로합병 36t IO +4500t m (3) 두개의 1500 레코드로된 24t IO +3000t m 런을합병 (12 블록 ) (4) 3000 레코드의런과 t IO +4500t m 레코드의런을합병 전체시간 디스크정렬예제에대한계산시간 132t IO t m + 6t IS Copyright 2007 DBLAB, Seoul National University 66
67 외부정렬 (6) 2 원합병보다높은차수의합병을이용하면런에대해서일어나는합병패스수를줄일수있음 입력, 출력, 합병을병렬적으로처리하기위해서적당한버퍼 - 관리방법이필요 Copyright 2007 DBLAB, Seoul National University 67
68 외부정렬 (7) k- 원합병 m 개의런이있을때의합병트리 log 2 m 1의레벨을가짐 총 log 2 m 패스필요 고차합병을사용하여줄일수있음 개런에대한 4- 원합병 2- 원인경우에데이타패스가 4 였지만 2 로줄어듬 Copyright 2007 DBLAB, Seoul National University 68
69 외부정렬 (8) 병렬연산을위한버퍼관리 k 개의런이 k- 원합병에의해한꺼번에합병되기위해 k개의입력버퍼와 1개의출력버퍼필요할것 입출력과내부합병을병렬로처리하기엔불충분 두개의출력버퍼가있으면해결됨 하나가출력되는동안다른하나에레코드들이합병됨 입력시간의지연은 2k 개의입력버퍼를사용하면해결됨 단순히한개의런에두개의버퍼를배당하는것은문제의해결방법이아님 Copyright 2007 DBLAB, Seoul National University 69
70 외부정렬 (9) 고정버퍼할당의불충분의예 (1) 2- 원합병을 4 개의입력버퍼 in[i](0 i<3), 2 개의출력버퍼 ou[0], ou[1] 을이용해서수행 각버퍼에는두개의레코드를담을수있음 ou[0] ou[1] ou[0] ou[1] ou[0] ou[1] in[0] in[1] in[0] in[1] in[0] in[1] in[2] in[3] in[2] in[3] in[2] in[3] (a) ou[0] 으로합병 (b) ou[0] 출력 (c) ou[1] 출력 in[2] 에입력 ou[1] 으로합병 ou[0] 으로합병 in[3] 에입력 in[0] 에입력 Copyright 2007 DBLAB, Seoul National University 70
71 외부정렬 (10) 고정버퍼할당의불충분의예 (2) ou[0] ou[1] ou[0] ou[1] ou[0] ou[1] in[0] in[1] in[0] in[1] in[0] in[1] in[2] in[3] in[2] in[3] in[2] in[3] (d) ou[0] 출력 ou[1] 으로합병 in[1] 에입력 (e) ou[1] 출력 ou[0] 으로합병 in[2] 에입력 (f) 런당두고정버퍼할당이연속적병렬연산에불충분함을보여주는예 버퍼들을필요에따라어떤런에도할당할수있도록해야함 Copyright 2007 DBLAB, Seoul National University 71
72 외부정렬 (11) 버퍼할당방법 각런의레코드를가지는입력버퍼가최소하나가늘존재 남아있는버퍼는우선순위에따라할당하여채워짐 k-원합병알고리즘에의해입력버퍼에있는레코드들이가장먼저소모되는런이다음버퍼로채워지는런임 가장작은키를가진런의버퍼가먼저소모됨 키가똑같을때는더작은인덱스의런을우선함 같은런으로부터입력되는모든버퍼레코드는큐로처리 컴퓨터병렬처리능력에대한가정 (1) 디스크드라이브는두개, 입출력채널은동시에각디스크에대해판독 / 기록가능 (2) I/O 장치와메모리블록사이에데이타전송중이면 CPU는동일한구역의메모리블록을참조못함 (3) 입출력버퍼는모두같은크기 Copyright 2007 DBLAB, Seoul National University 72
73 외부정렬 (12) 부동버퍼를이용한 k- 원합병 (1) /* 버퍼링알고리즘의단계 */ 단계 1: k 개의런각각으로부터첫번째블록을입력하여하나의데이타블록으로된 k 개의연결큐를설정한다. 나머지 k 개의입력블록들을자유입력블록들의연결스택에넣는다. ou 를 0 으로설정한다. 단계 2: lastkey[i] 를런 i 로부터마지막입력키라고하고, lastkey 가최소값인런을 nextrun 이라고하자. 만일 lastkey[nextrun] + 이면 nextrun 런으로부터다음블록을입력하기시작한다. 단계 3: 함수 Kwaymerge 를사용하여 k 개의입력큐로부터출력버퍼 ou 로레코드를합병한다. 출력버퍼가가득차거나키값이 + 인레코드가 ou 에나타날때까지합병을계속한다. 합병을수행하는동안, 출력버퍼가가득차기전이나 + 가 ou 에합병되기전에입력버퍼가비게되면, Kwaymerge 는같은큐의다음버퍼로진행하고빈버퍼는빈버퍼스택에반환한다. 그러나만약출력버퍼가가득차는것과동시에입력버퍼가비게되거나혹은 + 가 ou 에합병되는것과동시에입력버퍼가비게되면, 빈버퍼는큐에남게되고 Kwaymerge 는큐의다음버퍼로진행하지않는다. 대신에합병은중단된다. 단계 4: 디스크입출력이진행중이면완료되기를기다린다. 단계 5: 입력버퍼가읽혀졌으면해당런의큐에넣는다. lastkey[nextrun] 이최소로되는 nextrun 을결정하여다음에읽어야하는런을결정. 단계 6: lastkey[nextrun] + 이면 nextrun 런으로부터자유입력버퍼로읽기시작한다. 단계 7: 출력버퍼 ou 의쓰기를시작한다. ou 를 1-ou 로설정한다. 단계 8: 키값이 + 인레코드가출력버퍼로합병되지않았으면단계 3 으로간다. 그렇지않으면진행중인쓰기작업이완료되기를기다린후끝낸다. Copyright 2007 DBLAB, Seoul National University 73
74 외부정렬 (12) 부동버퍼를이용한 k- 원합병 (2) (1) k 가클경우, 먼저소모되는큐를결정하는데는 last[i](1 i<k) 에대해패자트리를만듦으로써 log 2 k 번의비교가가능 (2) k 가클경우, 함수 Kwaymerge 는패자트리를사용 (3) 처음 k 개블록의입력과마지막블록의출력을제외하고는모두 입출력이연산과동시에행해진다. (4) 알고리즘은모든블록의크기가같다고가정한다. 단계 6 에서다음블록을읽기시작할때는사용가능한버퍼가항상존재 단계 3 에서 k 원합병을할동안에큐에있는다음블록은그것이필요할때까지이미얽혀져있음 Copyright 2007 DBLAB, Seoul National University 74
75 외부정렬 (13) 세개의런으로 3- 원합병을수행하는예 각런은두개의레코드로된네개의블록으로구성 모든런에서네번째블록의마지막레코드의키 : + 여섯개의입력버퍼와두개의출력버퍼 Run 0 Run 1 Run 세개의런 Copyright 2007 DBLAB, Seoul National University 75
76 외부정렬 (14) - 버퍼링 (Buffering) 의예 Line 앞의예에서입력버퍼큐의상태, 다음블록이읽혀지고있는런, 버퍼링알고리즘의 3 단계 ~8 단계까지루프의반복이시작될때마다출력되는출력버퍼의상태 Next Block Queue Run0 Run1 Line Run2 Output From no output Run Run Run Run Run Run 2 7 M Run 1 8 M Run 2 9 M M Run 1 10 M M M no next 11 M 70 M 11 M no next 12 M 12 M 70 M Copyright 2007 DBLAB, Seoul National University 76
77 외부정렬 (15) - 런의생성 패자트리 (a tree of losers) 를이용 한꺼번에내부메모리에저장할수있는레코드개수보다더긴런의생성이가능 Walters, Painter,Zalk 에의해고안된런생성알고리즘 평균적으로두배길이의런을생성 병렬적인입출력및내부처리도가능 패자트리를이용 < 사용되는변수와그의미 > r[i], 0 i<k... 토너먼트트리에있는 k 개의레코드 l[i], 1 i<k... 노드 i 에서일어난토너먼트의패자 l[0]... 토너먼트의승자 m[i], 0 i<k... r[i] 가속한런번호 rc... 현재런의런번호 q... 모든토너먼트의승자 rq... r[q] 의런번호 rmax... 생성될런의개수 lastrec... 출력되는마지막레코드의키값 MAXREC... 허용된최대키값을가진레코드 Copyright 2007 DBLAB, Seoul National University 77
78 외부정렬 (16) Runs 의분석 : 평균적으로런의크기는거의 2k n개의런리스트를만들기위해모든런을생성하는데걸리는시간 : O(nlogk) 패자트리를조정하는데걸리는시간 : O(log k) Copyright 2007 DBLAB, Seoul National University 78
79 외부정렬 (17) - 런의최적합병 (1) 여러런들이상이한크기를갖는경우 (ex) 길이가각각 2,4,5,15인네개의런 2 원합병기법을이용하여합병하는두가지방법 : 외부노드 : 내부노드 (a) 15 (b) (a) 의외부경로길이 : 43 (b) 의외부경로길이 : 52 (a) (b) 어떤레코드는한번만합병, 어떤레코드는최대 3 번까지합병 각레코드는정확히두번씩합병 완전합병패스를모든데이타에대해반복적으로수행하는전략 합병횟수는루트로부터해당외부노드까지의거리에의해결정됨 외부경로길이 (weighted external path length) 런길이와루트에서해당외부노드까지의거리를곱한결과를모두합산하여구함 - 최소가중외부경로길이를갖도록하는것이좋다 Copyright 2007 DBLAB, Seoul National University 79
80 외부정렬 (17) - 런의최적합병 (2) 메시지 M 1,..., M n+1 을위한최적의코드집합을구할때 코드 : 이진스트링, 해당메시지를전달하는데사용 받는쪽에서해독트리를이용하여코드를해독 해독트리 (decode tree) 이진트리, 외부노드는메시지를나타냄 코드단어의이진비트는해독트리의각단계에서필요로하는분기결정 (e.x 왼쪽분기 0, 오른쪽분기 1) M 1 M 2 M 3 코드단어를해독하는비용 코드의비트수에비례 비트수 : 루트노드에서부터해당외부노드까지의거리에해당 M i 가전송되는상대적빈도가 q i 일때예상해독시간 : M 4 1 Huffman 코드 M 1 : 000 M 2 : 001 M 3 : 01 M 4 : 1 d : 루트로부터메시지 M i 에대한외부노드까지의거리 코드단어를최소가중외부경로길이를가진해독트리가되도록선정하면최소화됨 Copyright 2007 DBLAB, Seoul National University 80 1 i n 1 q i d i
81 외부정렬 (18) 최소가중외부경로길이를가진이진트리찾기 D. Huffman 이제시 template <class T> void Huffman(MinHeap<Treenode<T>*>heap, int n) { // heap 는위에서설명한대로초기에 n 개의단일정점이진트리로구성된최소히프이다. for(int i = 0; i < n-1; i++) {// 두최소가중트리를결합 TreeNode<T> *first = heap.pop(); TreeNode<T> *second = heap.pop(); TreeNode<T> *bt = new BinaryTreeNode<T>(first, second, first.data+second.data); heap.push(bt); } } Huffman 의분석 주된루프는 n-1 번수행됨 Pop 과 Push 에대한호출 : O(log n) 점근적연산시간 : O(nlogn) Copyright 2007 DBLAB, Seoul National University 81
82 외부정렬 (19) - Huffman 트리구축의예 가중치 : q 1 =2, q 2 =3, q 3 =5, q 5 =7, q 6 =9, q 7 =13 이트리의가중외부경로길이 : 2*4 + 3*4 + 5*3 + 13*2 + 7*2 + 9*2 = 93 비교해보면, 최선의완전이진트리의가중치경로길이는 (a) 2 3 (c) 23 (b) (d) (e) Copyright 2007 DBLAB, Seoul National University 82
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 informationMicrosoft PowerPoint Merging and Sorting Files.ppt
자료처리 () 006 년봄학기문양세강원대학교컴퓨터과학과 정렬 / 합병의개요 정렬의종류 : 내부정렬, 외부정렬 내부정렬 (internal sorting) 데이타가적어서메인메모리내에모두저장시켜정렬가능할때사용함 레코드의판독 (read) 및기록 (write) 에걸리는시간이문제가되지않음 외부정렬 (external sorting) 데이타가많아서메인메모리의용량을초과하여보조기억장치
More information슬라이드 1
CHAP 9: 정렬 정렬이란? 정렬은물건을크기순으로오름차순이나내림차순으로나열하는것 정렬은컴퓨터공학분야에서가장기본적이고중요한알고리즘중의하나 정렬은자료탐색에있어서필수 ( 예 ) 만약사전에서단어들이정렬이안되어있다면? 정렬의단위 레코드 정렬의대상 학생들의레코드 이름학번주소연락처 레코드 필드필드필드필드 키 (key) 정렬알고리즘의개요 많은정렬알고리즘존재 단순하지만비효율적인방법
More informationchap 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쉽게 배우는 알고리즘 강의노트
쉽게배우는알고리즘 장. 정렬 Sorting http://www.hanbit.co.kr 장. 정렬 Sorting 은유, 그것은정신적상호연관성의피륙을짜는방법이다. 은유는살아있다는것의바탕이다. - 그레고리베이트슨 - 2 - 학습목표 기본정렬알고리즘을이해한다. 정렬을귀납적관점에서볼수있도록한다. 1 장과 2 장에서배운기법을사용해각정렬의수행시간을분석할수있도록한다. 비교정렬의한계를이해하고,
More information2002년 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 information6장정렬알고리즘.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
More informationMicrosoft PowerPoint - 5장 정렬
01. 버블 02. 삽입 03. 퀵 04. C 표준 라이브러리의 퀵 정렬 정렬 정렬 정렬 함수 정렬은물건을크기순으로오름차순이나내림차순으로나열하는것 정렬은컴퓨터공학분야에서가장기본적이고중요한알고리즘중의하나 정렬은자료탐색에있어서필수적이다. ( 예 ) 만약사전에서단어들이정렬이안되어있다면? 정렬은왜하는가? 학생들의레코드 이름학번주소연락처 레코드 필드 필드 필드 필드
More information슬라이드 1
Data Structure Chapter 8. 우선순위큐 Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr 우선순위큐추상데이터타입 우선순위큐 우선순위큐 (priority queue) 정의 : 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게됨 스택이나 FIFO 큐를우선순위큐로구현할수있음
More information제 11 장 다원 탐색 트리
제 11 장 다원탐색트리 Copyright 07 DBLB, Seoul National University m- 원탐색트리의정의와성질 (1) 탐색성능을향상시키려면메모리접근횟수를줄여야함 탐색트리의높이를줄여야함 차수 (degree) 가 2보다큰탐색트리가필요 m- 원탐색트리 (m-way search tree) 공백이거나다음성질을만족 (1) 루트는최대 m 개의서브트리를가진다.
More informationChap 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 informationchap 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슬라이드 1
CHAP 8: 우선순위큐 yicho@gachon.ac.kr 1 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다. 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터
More informationCh.8 Procedures and Environments
Chapter 9 정렬 (sorting) SANGJI University Kwangman KO (kkman@sangji.ac.kr) 정렬 (sorting) 이란? 정의 물건을크기순으로오름차순이나내림차순으로나열하는것 컴퓨터공학분야에서가장기본적이고중요한알고리즘중의하나 정렬은자료탐색에있어서필수적. ( 예 ) 만약사전에서단어들이정렬이안되어있다면? 정렬알고리즘의개요
More informationChapter 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 informationAlgorithms
자료구조 & 알고리즘 정렬과탐색알고리즘 Seo, Doo-okok clickseo@gmail.com http://www.clickseo.com 목 차 기초적인정렬알고리즘 고급정렬알고리즘 탐색알고리즘 2 정 렬 (Sort) 정렬 (sort) 의개념 순서없이배열되어있는자료들을재배열하는것 정렬의대상 : 레코드 정렬의기준 : 정렬키 (sort key) 필드 정렬방법의분류
More information정렬 강의자료
CHAP 9 : 정렬 정렬이란? 정렬은물건을크기순으로오름차순이나내림차순으로나열하는것 정렬은컴퓨터공학을포함한모든과학기술분야에서가장기본적이고중요한알고리즘중하나 정렬은자료탐색에있어서필수적 ( 예 ) 만약영어사전에서단어들이알파벳순으로정렬되어있지않다면? 정렬의대상 일반적으로정렬시켜야될대상은레코드 (record) 레코드는다시필드 (field) 라는보다작은단위로구성 학생들의레코드
More information설계란 무엇인가?
금오공과대학교 C++ 프로그래밍 jhhwang@kumoh.ac.kr 컴퓨터공학과 황준하 6 강. 함수와배열, 포인터, 참조목차 함수와포인터 주소값의매개변수전달 주소의반환 함수와배열 배열의매개변수전달 함수와참조 참조에의한매개변수전달 참조의반환 프로그래밍연습 1 /15 6 강. 함수와배열, 포인터, 참조함수와포인터 C++ 매개변수전달방법 값에의한전달 : 변수값,
More information슬라이드 1
CHAP 6: 큐 yicho@gachon.ac.kr 1 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 () 후단 () 2 큐 ADT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element
More information5. 화일의정렬 / 합병 DBLAB, SNU v 정렬 / 합병의개요 u 정렬 (sorting) 내부정렬 (internal sorting) 데이타가적어서메인메모리내에모두저장시켜정렬가능할때 레코드판독, 기록에걸리는시간이문제되지않는다. 외부정렬 (external sortin
5. 의정렬 / 합병 v 정렬 / 합병의개요 u 정렬 (sorting) 내부정렬 (internal sorting) 데이타가적어서메인메모리내에모두저장시켜정렬가능할때 레코드판독, 기록에걸리는시간이문제되지않는다. 외부정렬 (external sorting) 데이타가많아서메인메모리의용량을초과하여보조저장장치에저장된을정렬할때 레코드판독, 기록에걸리는시간이중요 정렬 / 합병
More informationChapter 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슬라이드 1
CHAP 7: 트리 C 로쉽게풀어쓴자료구조 생능출판사 2005 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모 - 자식관계의노드들로이루어진다. 대표이사 응용분야 : 계층적인조직표현 총무부 영업부 생산부 파일시스템 인공지능에서의결정트리 전산팀구매팀경리팀생산 1 팀생산 2 팀 트리의용어 노드 (node): 트리의구성요소 루트 (root): 부모가없는노드
More information정의 이진탐색트리 이진탐색트리 (BST: binary search tree) 는각각의노드가 BST 특성을만족하는키 - 주소쌍을가지고있는이진트리 BST 특성 트리에있는각각의키에대해, 왼쪽서브트리에있는모든키는이것보다작고, 오른쪽서브트리에있는모든키는이것보다큼 < > 2
13. 탐색트리 AVL 트리, B- 트리, 2-3-4 트리 정의 이진탐색트리 이진탐색트리 (BST: binary search tree) 는각각의노드가 BST 특성을만족하는키 - 주소쌍을가지고있는이진트리 BST 특성 트리에있는각각의키에대해, 왼쪽서브트리에있는모든키는이것보다작고, 오른쪽서브트리에있는모든키는이것보다큼 < > 2 이진탐색트리의예 3 BST 의최선과최악의경우
More informationMicrosoft 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 information06_sorting
정렬 Data Structures and Algorithms 목차 버블정렬 선택정렬 삽입정렬 힙정렬 병합정렬 퀵정렬 기수정렬 Data Structures and Algorithms 2 버블정렬 Data Structures and Algorithms 3 버블정렬 Data Structures and Algorithms 4 버블정렬 Data Structures and
More information슬라이드 1
6-1 리스트 (list) 란순서를가진항목들을표현하는자료구조 리스트를구현하는두가지방법 배열 (array) 을이용하는방법 구현간단 삽입, 삭제시오버헤드 항목의개수제한 연결리스트 (linked list) 를이용하는방법 구현복잡 삽입, 삭제가효율적 크기가제한되지않음 6-2 객체 : n 개의 element 형으로구성된순서있는모임 연산 : add_last(list,
More information11장 포인터
Dynamic Memory and Linked List 1 동적할당메모리의개념 프로그램이메모리를할당받는방법 정적 (static) 동적 (dynamic) 정적메모리할당 프로그램이시작되기전에미리정해진크기의메모리를할당받는것 메모리의크기는프로그램이시작하기전에결정 int i, j; int buffer[80]; char name[] = data structure"; 처음에결정된크기보다더큰입력이들어온다면처리하지못함
More information-09- 학습목표 기본정렬알고리즘을이해한다. 정렬을귀납적관점에서볼수있도록한다. 1 장과 2 장에서배운기법을사용해각정렬의수행시간을분석할수있도록한다. 비교정렬의한계를이해하고, 선형시간정렬이가능한조건과선형시간정렬알고리즘을이해한다. - - 한빛미디어 Sortng Algorth
-09- 쉽게배우는알고리즘 장. 정렬 Sortng http://academy.hanb.co.kr 장. 정렬 Sortng 은유, 그것은정신적상호연관성의피륙을짜는방법이다. 은유는살아있다는것의바탕이다. - 그레고리베이트슨 - 2 - 한빛미디어 1 -09- 학습목표 기본정렬알고리즘을이해한다. 정렬을귀납적관점에서볼수있도록한다. 1 장과 2 장에서배운기법을사용해각정렬의수행시간을분석할수있도록한다.
More information제 1 장 기본 개념
이진트리순회와트리반복자 트리순회 (tree traversal) 트리에있는모든노드를한번씩만방문 순회방법 : LVR, LRV, VLR, VRL, RVL, RLV L : 왼쪽이동, V : 노드방문, R : 오른쪽이동 왼쪽을오른쪽보다먼저방문 (LR) LVR : 중위 (inorder) 순회 VLR : 전위 (preorder) 순회 LRV : 후위 (postorder)
More informationPowerPoint 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 informationPowerPoint 프레젠테이션
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 information06장.리스트
---------------- DATA STRUCTURES USING C ---------------- CHAPTER 리스트 1/28 리스트란? 리스트 (list), 선형리스트 (linear list) 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 리스트의예 요일 : ( 일요일, 월요일,, 토요일 ) 한글자음의모임 : ( ㄱ, ㄴ,, ㅎ ) 카드 :
More informationMicrosoft 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 informationMicrosoft PowerPoint - 6장 탐색.pptx
01. 순차탐색 02. 이진탐색 03. 이진탐색트리 04. 레드블랙트리 탐색 (search) 기본적으로여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요. 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열, 연결리스트, 트리, 그래프등 탐색키데이터 순차탐색 (sequential
More informationMicrosoft 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 informationchap01_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정보
정보 Sangwook Lee Deogi High School III 문제해결과프로그래밍 1 추상화 2 알고리즘 3 프로그래밍 2 알고리즘 2-1 알고리즘설계 2-2 알고리즘분석 3 2-1 알고리즘설계 (p.108) 학습목표 순차, 선택, 반복구조의흐름을설명할수있다. 다양한제어구조를활용하여논리적이고효율적인알고리즘을설계할수있다. 4 [1] 알고리즘제어구조 (p.109)
More informationA 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 information05_tree
Tree Data Structures and Algorithms 목차 트리의개요 이진트리의구현 이진트리의순회 (Traversal) 수식트리 (Expression Tree) 의구현 Data Structures and Algorithms 2 트리의개요 Data Structures and Algorithms 3 트리의접근과이해 트리는계층적관계 (Hierarchical
More information08장.트리
---------------- T STRUTURES USING ---------------- HPTER 트리 /29 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모-자식관계의노드들로이루어짐 응용분야 : 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀 생산 팀 생산 2 팀 (a) 회사의조직도 내문서 동영상음악사진 영화예능드라마 여행 (b) 컴퓨터의폴더구조
More information슬라이드 1
CHAP 8: 우선순위큐 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다. 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터 응용분야 : 시뮬레이션시스템 ( 여기서의우선순위는대개사건의시각이다.)
More information원형연결리스트에대한설명중틀린것은 모든노드들이연결되어있다 마지막에삽입하기가간단한다 헤더노드를가질수있다 최종노드포인터가 NULL이다 리스트의 번째요소를가장빠르게찾을수있는구현방법은무엇인가 배열 단순연결리스트 원형연결리스트 이중연결리스트 단순연결리스트의노드포인터 가마지막노드를
리스트에대한설명중틀린것은 구조체도리스트의요소가될수있다 리스트의요소간에는순서가있다 리스트는여러가지방법으로구현될수있다 리스트는집합과동일하다 다음은순차적표현과연결된표현을비교한것이다 설명이틀린것은 연결된표현은포인터를가지고있어상대적으로크기가작아진다 연결된표현은삽입이용이하다 순차적표현은연결된표현보다액세스시간이많이걸린다 연결된표현으로작성된리스트를 개로분리하기가쉽다 다음은연결리스트에서있을수있는여러가지경우를설명했는데잘못된항목은
More information<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CBED0C3E0C7C1B7CEB1D7B7A55C D616E2E637070>
#include "stdafx.h" #include "Huffman.h" 1 /* 비트의부분을뽑아내는함수 */ unsigned HF::bits(unsigned x, int k, int j) return (x >> k) & ~(~0
More information슬라이드 1
CHAP 8: 우선순위큐 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다. 우선순위큐 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터 응용분야 : 시뮬레이션시스템
More information완벽한개념정립 _ 행렬의참, 거짓 수학전문가 NAMU 선생 1. 행렬의참, 거짓개념정리 1. 교환법칙과관련한내용, 는항상성립하지만 는항상성립하지는않는다. < 참인명제 > (1),, (2) ( ) 인경우에는 가성립한다.,,, (3) 다음과같은관계식을만족하는두행렬 A,B에
1. 행렬의참, 거짓개념정리 1. 교환법칙과관련한내용, 는항상성립하지만 는항상성립하지는않는다. < 참인명제 > (1),, (2) ( ) 인경우에는 가성립한다.,,, (3) 다음과같은관계식을만족하는두행렬 A,B에대하여 AB=BA 1 가성립한다 2 3 (4) 이면 1 곱셈공식및변형공식성립 ± ± ( 복호동순 ), 2 지수법칙성립 (은자연수 ) < 거짓인명제 >
More informationFrama-C/JESSIS 사용법 소개
Frama-C 프로그램검증시스템소개 박종현 @ POSTECH PL Frama-C? C 프로그램대상정적분석도구 플러그인구조 JESSIE Wp Aorai Frama-C 커널 2 ROSAEC 2011 동계워크샵 @ 통영 JESSIE? Frama-C 연역검증플러그인 프로그램분석 검증조건추출 증명 Hoare 논리에기초한프로그램검증도구 사용법 $ frama-c jessie
More informationMicrosoft 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 informationMicrosoft PowerPoint - 08-Queue.ppt
Chapter Queue ( 큐 ) Dongwon Jeong djeong@kunsan.ac.kr Department of Informatics & Statistics 학습목표 큐의개념및추상데이터타입에대한이해 큐의구현방법 배열 링크드리스트 덱 / 데크의개념과구현방법 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In
More information슬라이드 1
CHP 6: 큐 C 로쉽게풀어쓴자료구조 생능출판사 2005 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 () 후단 () 큐 DT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element
More information7장
CHAP 7: 트리 C 로쉽게풀어쓴자료구조 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모 - 자식관계의노드들로이루어진다. 응용분야 : 계층적인조직표현파일시스템인공지능에서의결정트리 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀생산 1 팀생산 2 팀 * 예제 : 책그림 7-2, 7-3, 7-4 트리의용어 노드 (node): 트리의구성요소 루트
More informationLab 3. 실습문제 (Single linked list)_해답.hwp
Lab 3. Singly-linked list 의구현 실험실습일시 : 2009. 3. 30. 담당교수 : 정진우 담당조교 : 곽문상 보고서제출기한 : 2009. 4. 5. 학과 : 학번 : 성명 : 실습과제목적 : 이론시간에배운 Singly-linked list를실제로구현할수있다. 실습과제내용 : 주어진소스를이용해 Singly-linked list의각함수를구현한다.
More information이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다. 2
제 17 장동적메모리와연결리스트 유준범 (JUNBEOM YOO) Ver. 2.0 jbyoo@konkuk.ac.kr http://dslab.konkuk.ac.kr 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다. 이번장에서학습할내용 동적메모리란? malloc() 와 calloc() 연결리스트 파일을이용하면보다많은데이터를유용하고지속적으로사용및관리할수있습니다.
More information7장인덱스된 순차화일 DBLAB, SNU v 인덱스된순차화일의구조 u 인덱스된순차화일 (indexed sequential file) 은순차데이타화일 (sequential data file) 과인덱스 (index) 로구성 u 순차데이타화일 키값에따라레코드들이순차적으로정렬
7장인덱스된 순차화일 v 인덱스된순차화일의구조 u 인덱스된순차화일 (indexed sequential file) 은순차데이타화일 (sequential data file) 과인덱스 (index) 로구성 u 순차데이타화일 키값에따라레코드들이순차적으로정렬 레코드전체에대한순차접근을지원 u 인덱스화일 화일의레코드들에대한키값과포인터를저장 개별레코드에대한직접접근을지원 u
More information11강-힙정렬.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 information5 장 트 리
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 으로분할
More information03_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<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CC0E7B0EDB0FCB8AE5C53746F636B5F4D616E D656E74732E637070>
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include "QuickSort.h" 7 using namespace std; 8 9 10 Node* Queue[100]; // 추가입력된데이터를저장하기위한 Queue
More informationMicrosoft PowerPoint - ch11_정렬 [호환 모드]
정렬 자바로배우는쉬운자료구조 이장에서다룰내용 1 정렬 6 셸정렬 2 선택정렬 7 병합정렬 3 버블정렬 8 기수정렬 4 퀵정렬 9 힙정렬 5 삽입정렬 10 트리정렬 2 정렬 (1) 정렬 (sort) 2 개이상의자료를작은것부터큰순서 ( 오름차순, ascending) 로정렬또는큰것부터작은것순서 ( 내림차순, descending) 로재배열하는것 키 : 자료를정렬하는데사용하는기준값
More informationLab 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리스트 (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 information14장.탐색
---------------- DATA STRUCTURES USING C ---------------- CHAPTER 탐색 1/28 탐색 (search) 이란? 여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열,
More informationData 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으로 구성될 수 있으며, 한 라인에는 임의의 갯수의 숫자가 순서대로 나열될
More information<4D F736F F F696E74202D203728B0E8BBEABAB9C0E2B5B5B0B3B7D02DC1A4B7C4B9AEC1A6292E BC8A3C8AF20B8F0B5E55D>
계산복잡도 Computatioal Complexity 계산복잡도개론정렬문제 알고리즘의분석 어떤특정알고리즘의효율 (efficiecy 을측정 시간복잡도 (time complexity 공간복잡도 (space/memory complexity 문제의분석 일반적으로 계산복잡도분석 이란이를지칭 어떤문제에대해서그문제를풀수있는모든알고리즘의효율의하한 (lower-bou 을결정한다.
More information슬라이드 1
-Part3- 제 4 장동적메모리할당과가변인 자 학습목차 4.1 동적메모리할당 4.1 동적메모리할당 4.1 동적메모리할당 배울내용 1 프로세스의메모리공간 2 동적메모리할당의필요성 4.1 동적메모리할당 (1/6) 프로세스의메모리구조 코드영역 : 프로그램실행코드, 함수들이저장되는영역 스택영역 : 매개변수, 지역변수, 중괄호 ( 블록 ) 내부에정의된변수들이저장되는영역
More information1장. 리스트
01. 순차탐색 02. 이진탐색 03. 이진탐색트리 04. 레드블랙트리 탐색 (search) 기본적으로여러개의자료중에서원하는자료를찾는작업 컴퓨터가가장많이하는작업중의하나 탐색을효율적으로수행하는것은매우중요. 탐색키 (search key) 항목과항목을구별해주는키 (key) 탐색을위하여사용되는자료구조 배열, 연결리스트, 트리, 그래프등 탐색키데이터 순차탐색 (sequential
More information학습목차 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 information1장. 리스트
01. 링크드리스트 02. 더블링크드리스트 03. 환형링크드리스트 배열과는달리유연하게크기를바꿀수있는자료구조 각노드는다음노드를가리키는포인터를가짐. 각노드를다음노드를가리키는포인터로연결하여만든리스트. Single Linked List 라고도함. 링크드리스트의첫번째노드를헤드 (Head), 마지막노드를테일 (Tail) 이라고한다. C 언어로표현하는링크드리스트의노드 typedef
More informationPowerPoint 프레젠테이션
정렬알고리즘 9 장. 정렬알고리즘 가장많이, 그리고가장잘알려진알고리즘방법과효율빅오기호로분석 학습목표 정렬알고리즘의분류방법을이해한다. 정렬알고리즘별로작동원리에대해이해한다. 정렬알고리즘별로효율분석방법을이해한다. 정렬알고리즘에따라효율을개선하기위한방법을이해한다. 1 Section 01 정렬의분류 - 정렬의분류정렬 정렬의대상 = 레코드정렬의기준 = 정렬키 (Sort
More information제 11 장포인터 유준범 (JUNBEOM YOO) Ver 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다.
제 11 장포인터 유준범 (JUNBEOM YOO) Ver. 2.0 jbyoo@konkuk.ac.kr http://dslab.konkuk.ac.kr 본강의자료는생능출판사의 PPT 강의자료 를기반으로제작되었습니다. 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습합니다.
More informationMicrosoft PowerPoint - 제8장-트리.pptx
제 8 강의. 트리 (Tree) 자료구조 1. 트리의개념 2. 이진트리 3. 이진트리의저장 1 트리자료구조필요성연결리스트의삽입삭제시데이터를이동하지않는장점을살리자. 연결리스트의검색시노드의처음부터찾아가야하는단점을보완하자. 데이터를중간부터찾아가는이진검색의장점을이용하자. 연결리스트의포인터를리스트의중간에두는방법? ptr 10 23 34 42 56 검색을중간부터시작하여좌우중하나로분기,
More information입학사정관제도
자료구조 강의노트 교재 : C 로배우는쉬운자료구조 ( 개정판 ) 출판사 : 한빛미디어 (2011 년 3 월발행 ) 저자 : 이지영 소프트웨어학과원성현교수 1 8 장트리 소프트웨어학과원성현교수 93 1. 트리 트리개요 트리 (tree) 란? 리스트, 스택, 큐등은선형자료구조 (linear data structure) 인것에반해서트리는계층 (hierarchy)
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 informationMicrosoft PowerPoint - chap10_tree
Chap. 10 : Tree 2007 학년도 2 학기 1. 개요 재귀 (recursion) 의정의, 순환 ~ 정의하고있는개념자체에대한정의내부에자기자신이포함되어있는경우를의미 ~ 알고리즘이나함수가수행도중에자기자신을다시호출하여문제를해결하는기법 ~ 정의자체가순환적으로되어있는경우에적합한방법 ~ 예제 ) 팩토리얼값구하기 피보나치수열 이항계수 하노이의탑 이진탐색 -2-
More informationMicrosoft PowerPoint - chap-11.pptx
쉽게풀어쓴 C 언어 Express 제 11 장포인터 컴퓨터프로그래밍기초 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습한다. 컴퓨터프로그래밍기초 2 포인터란? 포인터 (pointer): 주소를가지고있는변수 컴퓨터프로그래밍기초 3 메모리의구조 변수는메모리에저장된다. 메모리는바이트단위로액세스된다.
More informationadfasdfasfdasfasfadf
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 information11장 포인터
누구나즐기는 C 언어콘서트 제 9 장포인터 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습한다. 포인터란? 포인터 (pointer): 주소를가지고있는변수 메모리의구조 변수는메모리에저장된다. 메모리는바이트단위로액세스된다. 첫번째바이트의주소는 0, 두번째바이트는 1, 변수와메모리
More informationMicrosoft PowerPoint - chap11-포인터의활용.pptx
#include int main(void) int num; printf( Please enter an integer: "); scanf("%d", &num); if ( num < 0 ) printf("is negative.\n"); printf("num = %d\n", num); return 0; 1 학습목표 포인터를 사용하는 다양한 방법에
More informationCh.1 Introduction
Tree & Heap SANGJI University Kwangman Ko (kkman@sangji.ac.kr) 트리개요 트리 (Tree) ~ 계층적인구조를나타내는비선형 (Non-linear) 자료구조 ~ 트리는부모-자식관계의노드로구성 ~ 응용분야 계층적인조직표현 파일시스템 인공지능에서의결정트리 kkman@sangji.ac.kr 2 트리자료구조를사용하는이유?
More informationJAVA 프로그래밍실습 실습 1) 실습목표 - 메소드개념이해하기 - 매개변수이해하기 - 새메소드만들기 - Math 클래스의기존메소드이용하기 ( ) 문제 - 직사각형모양의땅이있다. 이땅의둘레, 면적과대각
JAVA 프로그래밍실습 실습 1) 실습목표 - 메소드개념이해하기 - 매개변수이해하기 - 새메소드만들기 - Math 클래스의기존메소드이용하기 ( http://java.sun.com/javase/6/docs/api ) 문제 - 직사각형모양의땅이있다. 이땅의둘레, 면적과대각선의길이를계산하는메소드들을작성하라. 직사각형의가로와세로의길이는주어진다. 대각선의길이는 Math클래스의적절한메소드를이용하여구하라.
More informationMicrosoft PowerPoint - lec07_tree [호환 모드]
Tree 2008학년도 2학기 kkman@sangji.ac.krac kr -1- 트리 (Tree) 1. 개요 ~ 계층적인구조를나타내는비선형 (Non-linear) 자료구조 ~ 트리는부모 - 자식관계의노드로구성 ~ 응용분야 계층적인조직표현 파일시스템 인공지능에서의결정트리 -2- 트리자료구조를사용하는이유? ~ 다른자료구조와달리비선형구조. ~ 정렬된배열 탐색은빠르지만
More information(Hyunoo Shim) 1 / 24 (Discrete-time Markov Chain) * 그림 이산시간이다연쇄 (chain) 이다왜 Markov? (See below) ➀ 이산시간연쇄 (Discrete-time chain): : Y Y 의상태공간 = {0, 1, 2,..., n} Y n Y 의 n 시점상태 {Y n = j} Y 가 n 시점에상태 j 에있는사건
More informationchap x: G입력
재귀알고리즘 (Recursive Algorithms) 재귀알고리즘의특징 문제자체가재귀적일경우적합 ( 예 : 피보나치수열 ) 이해하기가용이하나, 비효율적일수있음 재귀알고리즘을작성하는방법 재귀호출을종료하는경계조건을설정 각단계마다경계조건에접근하도록알고리즘의재귀호출 재귀알고리즘의두가지예 이진검색 순열 (Permutations) 1 장. 기본개념 (Page 19) 이진검색의재귀알고리즘
More informationContents v 학습목표 자료구조큐에대한개념을스택과비교하여이해한다. 큐의특징과연산방법에대해알아본다. 순차표현방법을이용한큐와연결표현방법을이용한큐를구현해본다. 큐의응용방법을알아본다. v 내용 큐 큐의구현 큐의응용 2/74
큐 IT CookBook, C 로배우는쉬운자료구조 ( 개정판 ) Contents v 학습목표 자료구조큐에대한개념을스택과비교하여이해한다. 큐의특징과연산방법에대해알아본다. 순차표현방법을이용한큐와연결표현방법을이용한큐를구현해본다. 큐의응용방법을알아본다. v 내용 큐 큐의구현 큐의응용 2/74 1. 큐 v 큐 (Queue) 데이터의삽입과삭제가양쪽끝에서일어나는자료구조
More informationPowerPoint Presentation
Package Class 3 Heeseung Jo 목차 section 1 패키지개요와패키지의사용 section 2 java.lang 패키지의개요 section 3 Object 클래스 section 4 포장 (Wrapper) 클래스 section 5 문자열의개요 section 6 String 클래스 section 7 StringBuffer 클래스 section
More information01장.자료구조와 알고리즘
---------------- DATA STRUCTURES USING C ---------------- CHAPTER 자료구조와알고리즘 1/30 자료구조 일상생활에서자료를정리하고조직화하는이유는? 사물을편리하고효율적으로사용하기위함 다양한자료를효율적인규칙에따라정리한예 2/30 컴퓨터에서의자료구조 자료구조 (Data Structure) 컴퓨터에서자료를정리하고조직화하는다양한구조
More informationChap 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
More informationC 언어 강의노트
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<4D F736F F F696E74202D20C1A637C0E52DB0EDB1DEBFACB0E1B8AEBDBAC6AE2E >
제 7 강의. 고급연결리스트 1. 원형연결리스트 2. 이중연결리스트 3. 연결리스트알고리즘 1 1. 원형연결리스트 (Circularly Linked Lists) 원형연결리스트란? 연결리스트의맨끝노드를첫번째노드와연결시켜서원형으로만든리스트 단순연결리스트 (Singly Linked List) 불편한점 - 연결리스트의노드포인터를알고있을때첫번째노드는바로찾아갈수있지만마지막노드는리스트전체를따라가면서끝을찾아가야한다
More informationMicrosoft PowerPoint - 제11장 포인터(강의)
쉽게풀어쓴 C 언어 Express 제 11 장포인터 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습한다. 포인터란? 포인터 (pointer): 주소를가지고있는변수 1003 1004 1005 영화관 1002 1006 1001 포인터 (pointer) 1007 메모리의구조
More informationMicrosoft PowerPoint - Java7.pptx
HPC & OT Lab. 1 HPC & OT Lab. 2 실습 7 주차 Jin-Ho, Jang M.S. Hanyang Univ. HPC&OT Lab. jinhoyo@nate.com HPC & OT Lab. 3 Component Structure 객체 (object) 생성개념을이해한다. 외부클래스에대한접근방법을이해한다. 접근제어자 (public & private)
More informationChapter 4. LISTS
연결리스트의응용 류관희 충북대학교 1 체인연산 체인을역순으로만드는 (inverting) 연산 3 개의포인터를적절히이용하여제자리 (in place) 에서문제를해결 typedef struct listnode *listpointer; typedef struct listnode { char data; listpointer link; ; 2 체인연산 체인을역순으로만드는
More informationPowerPoint 프레젠테이션
실습 1 배효철 th1g@nate.com 1 목차 조건문 반복문 System.out 구구단 모양만들기 Up & Down 2 조건문 조건문의종류 If, switch If 문 조건식결과따라중괄호 { 블록을실행할지여부결정할때사용 조건식 true 또는 false값을산출할수있는연산식 boolean 변수 조건식이 true이면블록실행하고 false 이면블록실행하지않음 3
More information슬라이드 1
CHAP 6: 큐 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 (front) 후단 (rear) 큐 ADT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element 형으로구성된요소들의순서있는모임
More informationMicrosoft 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
More information쉽게배우는알고리즘 6장. 해시테이블 테이블 Hash Table
쉽게배우는알고리즘 6장. 해시테이블 테이블 Hash Table http://academy.hanb.co.kr 6장. 해시테이블 테이블 Hash Table 사실을많이아는것보다는이론적틀이중요하고, 기억력보다는생각하는법이더중요하다. - 제임스왓슨 - 2 - 학습목표 해시테이블의발생동기를이해한다. 해시테이블의원리를이해한다. 해시함수설계원리를이해한다. 충돌해결방법들과이들의장단점을이해한다.
More information<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 informationMicrosoft PowerPoint - chap06-2pointer.ppt
2010-1 학기프로그래밍입문 (1) chapter 06-2 참고자료 포인터 박종혁 Tel: 970-6702 Email: jhpark1@snut.ac.kr 한빛미디어 출처 : 뇌를자극하는 C프로그래밍, 한빛미디어 -1- 포인터의정의와사용 변수를선언하는것은메모리에기억공간을할당하는것이며할당된이후에는변수명으로그기억공간을사용한다. 할당된기억공간을사용하는방법에는변수명외에메모리의실제주소값을사용하는것이다.
More information제 9 장 우선순위 큐
제 9 장 우선순위큐 Copyright 007 DBLAB, Seoul National University 한쪽끝과양쪽끝우선순위큐 우선순위큐 (priority queue) - 각원소가연관된우선순위를갖고있는원소들의모임 최소우선순위큐에서의연산 - SP: 최소우선순위를가진원소의반환 - SP: 임의의우선순위를가진원소의삽입 - SP3: 최소우선순위를가진원소의삭제 최대우선순위큐에서의연산
More informationMicrosoft PowerPoint - chap06-1Array.ppt
2010-1 학기프로그래밍입문 (1) chapter 06-1 참고자료 배열 박종혁 Tel: 970-6702 Email: jhpark1@snut.ac.kr 한빛미디어 출처 : 뇌를자극하는 C프로그래밍, 한빛미디어 -1- 배열의선언과사용 같은형태의자료형이많이필요할때배열을사용하면효과적이다. 배열의선언 배열의사용 배열과반복문 배열의초기화 유연성있게배열다루기 한빛미디어
More information