05666 데이터구조 (Data Structure) 2011 년봄학기 숙명여자대학교멀티미디어과학과 박영호
05666 데이터구조론강좌개요 담당교수 : 박영호 ( 내선 : 2077-7297, yhpark@sm.ac.kr, 새함관 508 호, 010-6417-5541) 강의시간 교재 : C 로쓴자료구조, 이석호역, 교보, 2008 년판 (Fundamentals of Data Structures in C, Horowitz ) 성적 : Midterm Exam : 30%% Final Exam : 40% Homework (Programming 포함 ) : 30% 출석 : 감점 ( 결석 2점, 지각 1점 ) Sookmyung W. Univ., Prof. Youngho Park
데이터구조란무엇인가요? 여러분은어떻게생각하나요? 그럼, 쉽게설명해주세요 ~^^ Sookmyung W. Univ., Prof. Youngho Park
Sookmyung W. Univ., Prof. Youngho Park
Sookmyung W. Univ., Prof. Youngho Park
데이터구조란? 흩어져있는다양한형태의 데이터 ( 자료 ) 들을체계적으로모으거나연결하여 구조 를형성하는방법을배우는과목 Sookmyung W. Univ., Prof. Youngho Park
배우는내용 Chapter 01: Basic Concepts Chapter 02: Arrays and Structures Chapter 03: Stacks and Queues Chapter 04: Lists Chapter 05: Trees Chapter 06: Graphs Chapter 07: Sorting Chapter 08: Hashing Chapter 09: Heap Structures Chapter 10: Search Structures Sookmyung W. Univ., Prof. Youngho Park
Chapter 1 1.1 Overview 1.2 Algorithm Specification 1.3 Data Abstraction 1.4 Performance Analysis 1.5 Performance Measurement
Chapter 1 ( 전반 )Basic Concepts 1.1 Overview 1.2 Algorithm Specification 1.3 Data Abstraction
프로그램은 단계적기획이다 Sookmyung W. Univ., Prof. Youngho Park
데이터구조는 프로그램의구조 와연산방법을 배우는과목이다. Sookmyung W. Univ., Prof. Youngho Park
1.1 Overview 자료구조의 선행지식 : 비교적작은문제를해결하는구조적프로그래밍 (structured programming) 기술 목표 : 대규모컴퓨터시스템을설계, 구현하는도구들 (tools) 과기술들 (techniques) 을습득 System Life Cycle (= 프로그램을구현하는 5단계 ) 1. Requirements: ( 문제정의 à 요구사항수집 ) 2. Description (and Analysis): ( 정리 ( 문제분석 ) 해서기술함 ) 3. Algorithm Design: ( 합당한알고리즘설계 ) 4. Coding (Refinement 후 ): ( 검토, 프로그램작성 ) 5. Verification: ( 다양한방법으로검증 ) Sookmyung W. Univ., Prof. Youngho Park
1.2 Algorithm Specification 정의 : 알고리즘 어떤문제를해결하기위한 instruction 들의유한집합 (finite set) 으로써다음사항을만족하면, 알고리즘 이라한다. input: 외부에서알고리즘으로공급 ( 입력 ) 되는하나이상의 quantities ( 정량자들 ) 가존재해야한다. Output: 알고리즘수행후, 적어도하나의 quantity( 가시적결과 ) 가생성 ( 출력 ) 되어야한다. Definiteness: 각명령어들이명확하고, 애매함이없어야한다. Finiteness: 모든경우에, 유한 step 들이후반드시종료해야한다. Effectiveness: 각명령어들은기본적 ( basic) 이어야한다. 주의 : 계산이론 분야에서는알고리즘과프로그램을구분하지만 본과목에서는종료되는프로그램만다루므로, 모든프로그램을알고리즘이라생각하고이야기를전개한다. 일반적인알고리즘기술방법 : (1) natural language 와 (2) flow chart 등으로기술하지만 본과목에서는 (1) C 언어와 (2) natural language 를혼용하여기술한다. Sookmyung W. Univ., Prof. Youngho Park
System Life Cycle 예제 #1: Selection Sort 1 단계 ) Requirement: 현재정렬되어있지않은정수들을대상으로, 가장작은수를찾고, 그것을정렬된리스트에끼워넣어보자. 2 단계 ) Description: 상기문제를단계적으로설명 : List[0] 6 2 2 2 2 List[1] 5 5 3 3 3 List[2] 3 3 5 4 4 List[3] 4 4 4 5 5 List[4] 2 6 6 6 6 step1 step2 step3 step4 step5 Sookmyung W. Univ., Prof. Youngho Park
Selection Sort ( 계속 ) 3 단계 ) Algorithm Design: (1) natural language 나 (2) C 언어로기술 for (i=0; i < n; i++) { (1) 자연어 Examine list[i] to list[n-1] and suppose that the smallest integer is at list[min]; Swap list[i] and list[min]; void swap (int *x, int *y) { int temp = *x; // declares temp as an int and assigns to it // the contents of what x points to *x = *y; // stores what y points to into the location // where x points *y = temp; // places the contents of temp in location // pointed to by y (2) C언어 Sookmyung W. Univ., Prof. Youngho Park
4 단계 ) Coding: Program 작성단계 #include <stdio.h> #include <math.h> #define MAX_SIZE 101 #define SWAP(x,y,t) ((t)=(x), (x)=(y), (y)=(t)) void main(viod) { int i, n; int list[max_size]; printf( What number to sort: ); scanf( %d, &n); if (n < 1 n > MAX_SIZE) { fprintf(stderr, Wrong Num.\n ); exit(1); for (i=0; i < n; i++){ //randomly list[i] = rand() % 1000;//generate printf( %d, list[i]);//numbers sort (list, n); printf( \nsorted Array: \n ); for (i=0; i < n; i++) printf( %d, list[i]); printf( \n ); // print out sorted numbers void sort(int list [], int n) { int i, j, min, tmp; for (i=0; i < n; i++) { min = i; for(j=i+1; j < n; j++) if (list[j] < list[min]) min = j; swap(list[i], list[min], temp); 앞페이지에있는 swap함수호출 Sookmyung W. Univ., Prof. Youngho Park
System Life Cycle 예제 #2: Binary Search 1 단계 ) Requirement:: 서로다른 n 개의정렬된수가 list 에저장되어있을때, 특정한값을찾아라. 2 단계 ) Description: 상기문제에대한자세한설명 : - 다음리스트 A[10] 에서 searchnum == 4 를찾는문제 Index: A 0 1 2 3 4 5 6 7 8 9 2 3 4 5 6 7 8 9 10 11 Step 1: left=0 middle=4 right=9 Step 2: left=0 middle=1 right=3 Step 3: left=2right=3 middle=2 à FOUND! Sookmyung W. Univ., Prof. Youngho Park
Binary Search ( 계속 ) 3 단계 ) Algorithm Design: (1) natural language 나 (2) C 언어로기술 while (there are more integers to check) { middle = (left + right ) / 2; if (searchnum < list[middle]) right = middle -1; else if (searchnum == list[middle]) return middle; else left = middle + 1; Sookmyung W. Univ., Prof. Youngho Park
4 단계 ) Coding: Program 작성단계 int binsearch (int list [], { int searchnum, int left, int right) /* search list[0] <= list[1] <= <= list[n- 1] for searchnum,return its position if found. Otherwise, return -1 */ int middle; while (left <= right) { middle = (right+lest) / 2; switch (compare(list[middle],searchnum){ case -1: left = middle + 1; /* list[middle] < searchnum */ case 0: return middle; case 1: right = middle 1; return -1; int compare (int x, int y) { /* compare x and y, return -1 for less than, 0 for equal, 1 for greater */ if (x < y) return -1; else if (x == y) return 0; else return 1; Sookmyung W. Univ., Prof. Youngho Park
( 참고 ) Recursive Algorithm Recursion 이란? The technique of defining a process in terms of itself ( 자기자신내부 (in self body) 에, 새로운프로세스를또다시만들어내는기술 ) Example: n! = n * (n-1) * (n-2) * * 1 if n = 0, return f (n) = 1; otherwise, return n * f (n-1); Recursive Algorithm : Algorithm 의몸체 (body) 에서자기자신을또부르는 algorithm 어떤경우에 Recursive Algorithm 기법을쓰는가? 문제에대한자료구조가 반복적 으로 (recursive 하게 ) 정의된다고판단되는경우, 반복되는유형을발췌해서, 프로그램에간단하게표현하기위해사용되는기법이다. recursive algorithm 의 2 가지유형 유형 1: Direct recursion: algorithm A 가 A 를직접부름 유형 2: Indirect recursion: algorithm A 가 B 를 call 하고, B 가 A 를 call 함 Sookmyung W. Univ., Prof. Youngho Park
예제 : Recursive Binary Search Algorithm 문제분석 : 리스트전체 A[1, n] 에서 v를찾는문제는왼쪽리스트 A[1, middle] 과오른쪽리스트 A[middle+1, n] 에서 v를찾는문제로쪼개질수있으므로, 2개로쪼개진각리스트에서도동일한알고리즘을사용할수있다. int binsearch (int list [], int searchnum, int left, int right) { /* list[0] <= list[1] <= <= list[n-1] 인상태의리스트에서, 입력으로주어진 searchnum 를찾아보고, 발견되면, 그것의위치를출력하고, 만약없으면, -1 을출력하는프로그램을작성하시오. */ int middle; /* 리스트인덱스 ( 위치 ) 중, 중간위치를저장해놓는다. */ if (left <= right) { middle = (right + left) / 2; switch (compare(list[middle], searchnum) {/* searchnum 이크면우측, 아니면좌측 */ case 0: return middle; /* 그값이찾는값이면, middle 을반환한다 */ case -1: return binsearch (list, searchnum, middle+1, right); /* 우측 */ case 1: return binsearch (list, searchnum, left, middle-1); /* 좌측 */ return -1 Sookmyung W. Univ., Prof. Youngho Park
1.3 Data Abstraction ( 요약화혹은추상화 ) Definition: Data Type ( 자료형 ) 이란? 데이터객체와, 그에적용되는연산의집합 Pre-defined data type 과 user-defined data type 으로다시구분됨 Pre-defined data type: integer, char, float, (system dependent) User-defined data type: struct, array, class (in C++), An example of the data type: integer( 정수 ) data type ( 대상 ) Data objects: {INT-MIN, -2, -1, 0, 1, 2,, INT-MAX ( 연산들 ) Operations: integer plus (+), integer minus(-), integer multiplication(*), integer division(/), integer modulation (%) and so on. Sookmyung W. Univ., Prof. Youngho Park
Abstract Data Type (ADT) 정의 : ADT (1) 데이터객체 (Data object) 와연산들 (operations) 에대한간략한명세와 (2) 그들의구현 (implementation) 을분리시켜놓은 data type 을 à 추상데이터타입 (ADT) 이라고말한다. 즉, (1) 만존재하는타입이다. ( 또다른정의 : interface 를통해서만 data 를 access 할수있는 data type) 상기 (1) 데이터객체 (Data object) 와연산들 (operations) 에대한명세 는무엇? (1) Function name, (2) Arguments (name, type), (3) Return type, (4) Descriptions (natural language) 를의미함 à 상위레벨정보 ( 기능을개략적으로소개하는레벨, 이것이 ADT 이다.) 상기 (2) 그들의구현 (implementation) 이의미하는것은? (1) data structures (list, array, ), (2) real program code 를의미함 à 하위레벨정보 ( 위개념을프로그램으로어떻게구현할것인지의구체적레벨 ) ADT 에존재하는연산들은크게다음과같이구분된다. Creator/constructor: ADT의 new instance를생성하는기능 Transformers: ADT의기존 instances를받고, new instance를생성함 Observers/Reporters: ADT의 instances에대한설명정보를제공하는기능 Destructor: 생성되어운용중이던 instance를소멸시키는기능 Sookmyung W. Univ., Prof. Youngho Park
ADT 예제 : Nat_No (Natural Number) Structure Nat_No is (ß 여기서 Nat_No 는추상데이터타입이름임 ) object ( 대상 ): an ordered subrange of the integers starting at zero and ending at the maximum integer (INT_MAX) in the computer. functions ( 연산들 ): for all x, y in Nat_No, TRUE, FALSE in Boolean and where +, -, <, and == are the usual integer operations Nat_No Zero() ::= 0 Boolean IS_ZERO(x) ::= if (x) return FALSE else return TRUE Nat_No Add(x,y) ::= if ((x+y) < INT_MAX) return x+y else return INT_MAX Boolean Equal(x,y) ::= if (x == y) return TRUE else FALSE Nat_No Successor(x) ::= if (x == INT_MAX) return x else x+1 Nat_No Subtract(x, y) ::= if (x < y) return 0 else x-y End Nat_No Sookmyung W. Univ., Prof. Youngho Park
Chapter 1 ( 후반 ) 성능분석과측정 1.4 Performance Analysis 1.5 Performance Measurement
1.4 Performance Analysis ( 분석, 계산에의한것임 ) 특정컴퓨터의성능과상관없이, 어떤 Program 의, time 과 ( 효율성, efficiency, 빠른속도의프로그램이목표 ) space 사용정도 ( 메모리공간점유도, economy, 경제성목표 ) 를분석하여, 프로그램자체가잘만들어졌는지를판별할, 평가기준으로삼음 ( 참고 ) 작성된 Program 을평가하는일반적인기준들 ( 평가항목들 ) 문제의 specifications 을만족하는가? Program 이 correct 한가? Program 의 documentation 이충분한가? 문제의 logical units 을생성하는데 functions 을효율적으로사용했는가? Program 이 readable 한가? Program 이 storage (memory, disk) 를효과적으로사용하는가? Program 의수행시간이늦지않은가? Sookmyung W. Univ., Prof. Youngho Park 3
a Program, P 의 time, space complexity( 복잡도 ) Time 과 Space 의복잡한정도 ( 복잡도 ) 를사용하여측정하는이유 프로그램의 (1) 수행시간과프로그램수행시사용하는 (2) 메모리공간을계산해서어떤프로그램의성능정도를정량적으로판단하기위함 à 어떤프로그램의성능을표현하기위해시간과공간을 metric 으로사용한다! Definition (metric 이되는용어정의 ) Space complexity: Program P의수행완료에필요한 memory용량 S(P): Space Degree of the Program Time complexity: Program P의수행완료에필요한 CPU 사용시간 T(P): Time Efficiency of the Program Sookmyung W. Univ., Prof. Youngho Park 4
Space Complexity(:= S(P)) Fixed Space와 variable space로구성됨 Fixed space: program의 input/output size에무관한다음공간의합 (:= c) 1. Instruction space ( 실제 p 자체, 프로그래머가작성한 code 자체크기 ) 2. Space for simple variables ( p 내에서선언된변수들을모두합산한크기 ) 3. Fixed size structured variable들의크기 ( 크기를미리알수있는 struct 등 ) 4. Constants 들의크기 ( 상수들의크기 ) Variable space: program 이 input/output size 에종속된공간의합 (:= S p (I)) 프로그램의수행중 (Run Time) 에, instance I 에의해발생된 (1) 구조화된변수들 (Structured variables) 의메모리공간과 (2) 재귀호출 (Recursion) 로인해서재차반복적으로생기게되는메모리공간의합으로계산됨. instance I 의어떤특성들의함수 ( 첫번째계산해야하는것 ) Program P 의 total space 요구량계산방법 S(P) = c + S p (I) Sookmyung W. Univ., Prof. Youngho Park 5
Time Complexity (:= T(P)) ( 두번째계산해야하는것 ) T(P) = Compile time (T c ) + Run time (T p ) 예제 : n 개의수를더하고빼는 program 의 (run) time complexity T p (n) = C a ADD(n) + C s SUB(n) + C l LDA(n) + C st STA(n) C a, C s, C l, C st : 각연산 (addition, subtraction, load, store) 연산시간소요비용 (Cost) ADD, SUB, LDA, STA: 각연산의회수를나타내는함수 n : instance characteristics (n 개의수를더하고, 뺀다 ) Run time (execution time) 추정방법 정확한계산 : 시스템 clock 수로계산가능하지만, machine dependent 하여큰의미가없다. 실용적인대안 : program 이수행하는연산 (operation)_ 의수로추정하며, machine independent 하게추정하면된다. à 그럼, Program Step 을이용하자! Sookmyung W. Univ., Prof. Youngho Park 6
Program Step( 을세는 ) 방법 Definition: program 에서의미있는것은 Syntactical Segment (code 자체 ) 이다. ( 수행중의 instance 특성과전혀상관없이, 코드의스텝을세는방법이다.) 세는방법의예 : 할당문 (Assignment Statement) A = 2 A = 2*b+3*c/d-e+f/g à One step à One step 반복문을세는방법의예 : iterative summing of a list of numbers float sum (float list [], int n) { float tempsum = 0; int i; for (i=0; i < n; i++) tempsum += list[i]; return tempsum; Next Page Sookmyung W. Univ., Prof. Youngho Park 7
Program Step (cont) count 변수를두어, 할당문, loop 변수, return 문등의개수를센다. float sum (float list [], int n) { int count = 0; /* 세기위해서, 먼저 count 변수를둔다. */ float tempsum = 0; count++; /* 할당문은센다. */ int i; /* 선언문은세지않는다. */ for (i=0; i < n; i++) { count++; /* for loop를센다. */ tempsum += list[i]; count++; /* 할당문을센다. */ count++; /* 마지막 for loop를센다. */ count++; /* return 문을여기서센다. */ return tempsum; Sookmyung W. Univ., Prof. Youngho Park 8
Example: Program Steps in recursive summing of a list numbers float rsum (float list [], int n) { if (n) return rsum(list, n-1) + list[n-1]; return 0; float rsum (float list [], int n) { count++; /* 아래에있는 if 문장의수행수를센다. */ if (n) { count++; /* 아래 return 과 rsum 이호출될때마다센다. */ return rsum(list, n-1) + list[n-1]; count++; /* 아래에있는 return 문의호출수를센다. */ return 0; Sookmyung W. Univ., Prof. Youngho Park 9
( 중요 ) Asymptotic Notation (O, Ω, Θ) Program 의 step 을 counting 하는목적은 (1) 두 program 들의 time complexity 를상대적으로분석 / 비교 ( 예, f 와 g 프로그램 ) (2) Instance (n) 의 characteristic 들 ( 움직임, 루프등 ) 이변할때, run time 의증가치분석 문제점 : 정확한 step count 는일반적으로어려우며, 위의목적에유용하지않음 à 해결방안 : program 의 time 과 space complexity 를잘나타내는새로운개념이필요함. Definition: Upper bound complexity, Big oh O Let f and g are non-negative functions, f(n) = O (g(n)) iff there exist positive constants c and n 0 such that f(n) <= cᆞg(n) for all n > n 0 예제 : 3n + 2 = O (n) : since 3n + 2 <= 4n, for n=2) 10n 2 + 4n + 2 = O (n 4 ) : Since 10n 2 + 4n + 2 <= 10n 4, for n >= 2) 해설 : g(n) 은 f(n) 을포함할정도로설정한후, f(n) 은 g(n) 보다작다고말한다. f(n) 은항상 g(n) 보다작으므로, f(n) 이자신을소개할때, 난 g(n) 보다작다. g(n) 은나의 Upper Bound 다 라고말할수있다는것이다. Sookmyung W. Univ., Prof. Youngho Park 10
Big O Notation (cont.) Upper Bound Complexity(O) Notes: f(n) = O (g(n)) 은 g(n) 이 f(n) 의 upper bound 이므로가능한 g(n) 을작은값으로잡아야유용하다. 가능한손해안보는근접한값으로하자! O (g(n)) = f(n) 은 f(n) = O (g(n)) 과다르다. 또한, 연산자체가무의미하다. Theorem: if f(n) = a m n m + + a 1 n 1 + a 0 (polynomial), then f(n) = O(n m ) Example: big oh O(1): constant complexity O(n): linear complexity O(n 2 ): quadratic complexity O(n 3 ): cubic complexity O(2 n ): exponential complexity Sookmyung W. Univ., Prof. Youngho Park 11
Lower Bound Complexity(Ω), Upper and Lower(Both) Bound Complexity(Θ) Definition: Lower bound Complexity, Ω f(n) = Ω (g(n)) iff there exist positive constants c and n 0 such that f(n) >= cᆞg(n) for all n > n 0 Example 3n + 2 = Ω (n) : since 3n + 2 >= 3n, for n=1) 10n 2 + 4n + 2 = Ω (n 2 ) : Since 10n 2 + 4n + 2 >= n 2, for n >= 1) Notes: lower bound 를찾는것이중요하므로, g(n) 을가능한크게잡는다. 해설 g(n) 은 f(n) 이포함될정도로설정한후, f(n) 은 g(n) 보다는크다고말한다. f(n) 은항상 g(n) 보다크므로, f(n) 이자신을소개할때, 난 g(n) 보다는크다. g(n) 은나의 Lower Bound 다 라고말할수있다는것이다. ( 중요 ) Definition: Upper and Lower bound Complexity, Θ f(n) = Θ (g(n)), iff g(n) is both an upper and lower bound on f(n). Sookmyung W. Univ., Prof. Youngho Park 12
Program Step 을세는방법예제 : Matrix Addition 의 time complexity 를구하시오 void add (int a[][max_size], int b[][max_size], int c[][max_size], int rows, int cols) { int i, j; for (i=0; i < rows; i++) for (j=0; j < cols; j++) c[i][j] = a[i][j] + n[i][j]; void add (int a[][max_size], int b[][max_size], int c[][max_size], int rows, int cols) { int i, j, count; for (i=0; i < rows; i++){ count++; for (j=0; j < cols; j++){ count++; c[i][j] = a[i][j] + n[i][j]; count++; count++; count++; Sookmyung W. Univ., Prof. Youngho Park 13
Time Complexity 구하는방법예제 : Matrix Addition 의 time complexity 를구하시오 Statements void add (int a[][max_size], int b[][max_size], int c[][max_size], int rows, int cols) { int i, j; for (i=0; i < rows; i++) for (j=0; j < cols; j++) c[i][j] = a[i][j] + n[i][j]; total Asymptotic complexity (good!) 0 0 0 0 0 0 Θ(rows) : n (i) 번루프돈다 Θ(rows*cols) : n 2 ( i 2 ) 번루프돈다 Θ(rows*cols) : n 2 0 Θ(rows*cols) : n 2 Sookmyung W. Univ., Prof. Youngho Park 14
1.4 Practical Complexities Time complexity 는 f (instance characteristics of P) 의함수형태로주어짐 Instance characteristics ( 예를들어, 변수 n 의 looping 과같은상태변화 ) 이변할때 time complexity 의변화량을추정하고, 같은기능을수행하는, 서로다른프로그램 P, Q 의 time complexity 를비교하는데유용함. 프로그램 P, Q 의 time complexity 비교에서 충분히큰 instance characteristics 에대해비교해야함 instance characteristics 의증가에따른 time complexity 증가비율 à page 45, 그림 1.7 을보자. Sookmyung W. Univ., Prof. Youngho Park 15
1.5 Performance Measurement ( 측정, 실험 ( 실측 ) 에의한것임 ) How does the algorithm execute on our machine? Analysis( 분석, 계산에의함 ) 보다 measurement( 측정, 실험에의함 ) 가필요 ß 상기 2 가지개념 ( 분석, 측정 ) 을분명하게구분해야한다. C 의 standard library 사용 #define <time.h> 2 가지측정도구사용 CPU clock 과 time (Elapsed Time) 성능분석 (1.4) 및측정 (1.5) 정확성을위해아래두가지모두필요 알고리즘의성능 : 분석을실시 - Analysis 프로그램의성능 : 측정을실시 - Measurement Sookmyung W. Univ., Prof. Youngho Park 16
프로그램은 단계적기획이다 Sookmyung W. Univ., Prof. Youngho Park 17
데이터구조는 프로그램의구조 와연산방법을 배우는과목이다. Sookmyung W. Univ., Prof. Youngho Park 18
프로그램의성능은 O, Ω, Θ 으로알수있다. Sookmyung W. Univ., Prof. Youngho Park 19
Review of Chapter 1 (1) 아래를읽고, 상호비교하며정리해보기 (a) P.24 ~ P.36 : 시간. 공간복잡도 2 번이상읽기 (b) P.36 ~ P.52 : 점근표기법 3 번이상읽기 (2) P.41 ~ P.44 Magic Square 프로그램실행및제출 복잡도이해해서자기이해한방식으로정리해보기 (3) P.50 ~ P.51 Selection Sort 의시간측정프로그램 2 개실행및제출 출력결과보이고, 분석방법과무슨차이가있는지정리하기 Sookmyung W. Univ., Prof. Youngho Park 20