Microsoft PowerPoint - Chap1-전반부 [호환 모드]

Size: px
Start display at page:

Download "Microsoft PowerPoint - Chap1-전반부 [호환 모드]"

Transcription

1 05666 데이터구조 (Data Structure) 2011 년봄학기 숙명여자대학교멀티미디어과학과 박영호

2 05666 데이터구조론강좌개요 담당교수 : 박영호 ( 내선 : , yhpark@sm.ac.kr, 새함관 508 호, ) 강의시간 교재 : 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

3 데이터구조란무엇인가요? 여러분은어떻게생각하나요? 그럼, 쉽게설명해주세요 ~^^ Sookmyung W. Univ., Prof. Youngho Park

4 Sookmyung W. Univ., Prof. Youngho Park

5 Sookmyung W. Univ., Prof. Youngho Park

6 데이터구조란? 흩어져있는다양한형태의 데이터 ( 자료 ) 들을체계적으로모으거나연결하여 구조 를형성하는방법을배우는과목 Sookmyung W. Univ., Prof. Youngho Park

7 배우는내용 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

8 Chapter Overview 1.2 Algorithm Specification 1.3 Data Abstraction 1.4 Performance Analysis 1.5 Performance Measurement

9 Chapter 1 ( 전반 )Basic Concepts 1.1 Overview 1.2 Algorithm Specification 1.3 Data Abstraction

10 프로그램은 단계적기획이다 Sookmyung W. Univ., Prof. Youngho Park

11 데이터구조는 프로그램의구조 와연산방법을 배우는과목이다. Sookmyung W. Univ., Prof. Youngho Park

12 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

13 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

14 System Life Cycle 예제 #1: Selection Sort 1 단계 ) Requirement: 현재정렬되어있지않은정수들을대상으로, 가장작은수를찾고, 그것을정렬된리스트에끼워넣어보자. 2 단계 ) Description: 상기문제를단계적으로설명 : List[0] List[1] List[2] List[3] List[4] step1 step2 step3 step4 step5 Sookmyung W. Univ., Prof. Youngho Park

15 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

16 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

17 System Life Cycle 예제 #2: Binary Search 1 단계 ) Requirement:: 서로다른 n 개의정렬된수가 list 에저장되어있을때, 특정한값을찾아라. 2 단계 ) Description: 상기문제에대한자세한설명 : - 다음리스트 A[10] 에서 searchnum == 4 를찾는문제 Index: A 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

18 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

19 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

20 ( 참고 ) 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

21 예제 : 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

22 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

23 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

24 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

25 Chapter 1 ( 후반 ) 성능분석과측정 1.4 Performance Analysis 1.5 Performance Measurement

26 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

27 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

28 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

29 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

30 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

31 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

32 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

33 ( 중요 ) 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

34 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

35 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

36 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

37 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!) Θ(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

38 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

39 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

40 프로그램은 단계적기획이다 Sookmyung W. Univ., Prof. Youngho Park 17

41 데이터구조는 프로그램의구조 와연산방법을 배우는과목이다. Sookmyung W. Univ., Prof. Youngho Park 18

42 프로그램의성능은 O, Ω, Θ 으로알수있다. Sookmyung W. Univ., Prof. Youngho Park 19

43 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

chap x: G입력

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

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

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

슬라이드 1

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

More information

C# Programming Guide - Types

C# Programming Guide - Types C# Programming Guide - Types 최도경 lifeisforu@wemade.com 이문서는 MSDN 의 Types 를요약하고보충한것입니다. http://msdn.microsoft.com/enus/library/ms173104(v=vs.100).aspx Types, Variables, and Values C# 은 type 에민감한언어이다. 모든

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

슬라이드 1

슬라이드 1 CHAP 1: 자료구조와알고리즘 C 로쉽게풀어쓴자료구조 생능출판사 2005 일상생활에서의사물의조직화 조직도 일상생활에서의사물의조직화 Ticket Box 일상생활과자료구조의비교 a b c N 일상생활에서의예 물건을쌓아두는것 영화관매표소의줄 할일리스트 자료구조 스택 큐 리스트 영어사전사전, 탐색구조 지도 조직도 그래프 트리 Ticket Box C B A 전단 (front)

More information

슬라이드 1

슬라이드 1 CHAP 1: 자료구조와알고리즘 일상생활에서의사물의조직화 조직도 일상생활에서의사물의조직화 Ticket Box 일상생활과자료구조의비교 일상생활에서의예 물건을쌓아두는것 영화관매표소의줄 할일리스트 자료구조 스택 큐 리스트 a b c NULL C B A 영어사전사전, 탐색구조 Ticket Box 지도 조직도 그래프 트리 전단 (front) 후단 (rear) 자료구조와알고리즘

More information

Line (A) å j a k= i k #define max(a, b) (((a) >= (b))? (a) : (b)) long MaxSubseqSum0(int A[], unsigned Left, unsigned Right) { int Center, i; long Max

Line (A) å j a k= i k #define max(a, b) (((a) >= (b))? (a) : (b)) long MaxSubseqSum0(int A[], unsigned Left, unsigned Right) { int Center, i; long Max 알고리즘설계와분석 (CSE3081-2반 ) 중간고사 (2013년 10월24일 ( 목 ) 오전 10시30분 ) 담당교수 : 서강대학교컴퓨터공학과임인성수강학년 : 2학년문제 : 총 8쪽 12문제 ========================================= < 주의 > 답안지에답을쓴후제출할것. 만약공간이부족하면답안지의뒷면을이용하고반드시답을쓰는칸에답안지의어느쪽의뒷면에답을기술하였는지명시할것.

More information

데이터 구조의 개요

데이터 구조의 개요 자료구조와알고리즘 충북대학교 소프트웨어학과이충세 문의사항 Email : csrhee@cbnu.ac.kr 전화 : 043-26-2237 강의자료 : web.cbu.ac.kr/~algor 참조 2 알고리즘 : 주제 기초자료구조 알고리즘의분석기법 트리와그래프 점화식 알고리즘기법분할정복, 동적프로그램, Greedy 방법 3 . 데이터와데이터객체.. 데이터의개념 *

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

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 프레젠테이션 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

강의10

강의10 Computer Programming gdb and awk 12 th Lecture 김현철컴퓨터공학부서울대학교 순서 C Compiler and Linker 보충 Static vs Shared Libraries ( 계속 ) gdb awk Q&A Shared vs Static Libraries ( 계속 ) Advantage of Using Libraries Reduced

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

01장.자료구조와 알고리즘

01장.자료구조와 알고리즘 ---------------- DATA STRUCTURES USING C ---------------- CHAPTER 자료구조와알고리즘 1/30 자료구조 일상생활에서자료를정리하고조직화하는이유는? 사물을편리하고효율적으로사용하기위함 다양한자료를효율적인규칙에따라정리한예 2/30 컴퓨터에서의자료구조 자료구조 (Data Structure) 컴퓨터에서자료를정리하고조직화하는다양한구조

More information

歯sql_tuning2

歯sql_tuning2 SQL Tuning (2) SQL SQL SQL Tuning ROW(1) ROW(2) ROW(n) update ROW(2) at time 1 & Uncommitted update ROW(2) at time 2 SQLDBA> @ UTLLOCKT WAITING_SESSION TYPE MODE_REQUESTED MODE_HELD LOCK_ID1

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

[ 마이크로프로세서 1] 2 주차 3 차시. 포인터와구조체 2 주차 3 차시포인터와구조체 학습목표 1. C 언어에서가장어려운포인터와구조체를설명할수있다. 2. Call By Value 와 Call By Reference 를구분할수있다. 학습내용 1 : 함수 (Functi

[ 마이크로프로세서 1] 2 주차 3 차시. 포인터와구조체 2 주차 3 차시포인터와구조체 학습목표 1. C 언어에서가장어려운포인터와구조체를설명할수있다. 2. Call By Value 와 Call By Reference 를구분할수있다. 학습내용 1 : 함수 (Functi 2 주차 3 차시포인터와구조체 학습목표 1. C 언어에서가장어려운포인터와구조체를설명할수있다. 2. Call By Value 와 Call By Reference 를구분할수있다. 학습내용 1 : 함수 (Function) 1. 함수의개념 입력에대해적절한출력을발생시켜주는것 내가 ( 프로그래머 ) 작성한명령문을연산, 처리, 실행해주는부분 ( 모듈 ) 자체적으로실행되지않으며,

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

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 강의소개 1. 교재 C로쓴자료구조론, Horowitz, Sahi, Aderso-Freed 보조 : itroductio to algorithms, corme 외 3명, MIT press 2. 강의자료 E 강의실게시판 3. 교수컴퓨터공학부지상문연구실 : 8관 606호전화 : 607-5146 E-mail: smchiks@ks.ac.kr 4. 성적퀴즈 20%, 중간

More information

11장 포인터

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

More information

C 언어 프로그래밊 과제 풀이

C 언어 프로그래밊 과제 풀이 과제풀이 (1) 홀수 / 짝수판정 (1) /* 20094123 홍길동 20100324 */ /* even_or_odd.c */ /* 정수를입력받아홀수인지짝수인지판정하는프로그램 */ int number; printf(" 정수를입력하시오 => "); scanf("%d", &number); 확인 주석문 가필요한이유 printf 와 scanf 쌍

More information

Microsoft PowerPoint - chap02-C프로그램시작하기.pptx

Microsoft PowerPoint - chap02-C프로그램시작하기.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 학습목표 을 작성하면서 C 프로그램의

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

0. 표지에이름과학번을적으시오. (6) 1. 변수 x, y 가 integer type 이라가정하고다음빈칸에 x 와 y 의계산결과값을적으시오. (5) x = (3 + 7) * 6; x = 60 x = (12 + 6) / 2 * 3; x = 27 x = 3 * (8 / 4

0. 표지에이름과학번을적으시오. (6) 1. 변수 x, y 가 integer type 이라가정하고다음빈칸에 x 와 y 의계산결과값을적으시오. (5) x = (3 + 7) * 6; x = 60 x = (12 + 6) / 2 * 3; x = 27 x = 3 * (8 / 4 Introduction to software design 2012-1 Final 2012.06.13 16:00-18:00 Student ID: Name: - 1 - 0. 표지에이름과학번을적으시오. (6) 1. 변수 x, y 가 integer type 이라가정하고다음빈칸에 x 와 y 의계산결과값을적으시오. (5) x = (3 + 7) * 6; x = 60 x

More information

02장.배열과 클래스

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

More information

C++-¿Ïº®Çؼ³10Àå

C++-¿Ïº®Çؼ³10Àå C C++. (preprocessor directives), C C++ C/C++... C++, C. C++ C. C C++. C,, C++, C++., C++.,.. #define #elif #else #error #if #itdef #ifndef #include #line #pragma #undef #.,.,. #include #include

More information

슬라이드 1

슬라이드 1 -Part3- 제 4 장동적메모리할당과가변인 자 학습목차 4.1 동적메모리할당 4.1 동적메모리할당 4.1 동적메모리할당 배울내용 1 프로세스의메모리공간 2 동적메모리할당의필요성 4.1 동적메모리할당 (1/6) 프로세스의메모리구조 코드영역 : 프로그램실행코드, 함수들이저장되는영역 스택영역 : 매개변수, 지역변수, 중괄호 ( 블록 ) 내부에정의된변수들이저장되는영역

More information

Microsoft Word - FunctionCall

Microsoft Word - FunctionCall Function all Mechanism /* Simple Program */ #define get_int() IN KEYOARD #define put_int(val) LD A val \ OUT MONITOR int add_two(int a, int b) { int tmp; tmp = a+b; return tmp; } local auto variable stack

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

C 프로그래밍 언어 입문 C 프로그래밍 언어 입문 김명호저 숭실대학교 출판국 머리말..... C, C++, Java, Fortran, Python, Ruby,.. C. C 1972. 40 C.. C. 1999 C99. C99. C. C. C., kmh ssu.ac.kr.. ,. 2013 12 Contents 1장 프로그래밍 시작 1.1 C 10 1.2 12

More information

중간고사

중간고사 중간고사 예제 1 사용자로부터받은두개의숫자 x, y 중에서큰수를찾는알고리즘을의사코드로작성하시오. Step 1: Input x, y Step 2: if (x > y) then MAX

More information

1

1 1 1....6 1.1...6 2. Java Architecture...7 2.1 2SDK(Software Development Kit)...8 2.2 JRE(Java Runtime Environment)...9 2.3 (Java Virtual Machine, JVM)...10 2.4 JVM...11 2.5 (runtime)jvm...12 2.5.1 2.5.2

More information

6.1 Addresses and Pointers Recall memory concepts from Ch2 ch6_testbasicpointer.c int x1=1, x2=7; double distance; int *p; int q=8; p = &q; name addre

6.1 Addresses and Pointers Recall memory concepts from Ch2 ch6_testbasicpointer.c int x1=1, x2=7; double distance; int *p; int q=8; p = &q; name addre GEN1031 Computer Programming Chapter 6 Pointer 포인터 Kichun Lee Department of Industrial Engineering Hanyang Univesity 1 6.1 Addresses and Pointers Recall memory concepts from Ch2 ch6_testbasicpointer.c

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

example code are examined in this stage The low pressure pressurizer reactor trip module of the Plant Protection System was programmed as subject for

example code are examined in this stage The low pressure pressurizer reactor trip module of the Plant Protection System was programmed as subject for 2003 Development of the Software Generation Method using Model Driven Software Engineering Tool,,,,, Hoon-Seon Chang, Jae-Cheon Jung, Jae-Hack Kim Hee-Hwan Han, Do-Yeon Kim, Young-Woo Chang Wang Sik, Moon

More information

Frama-C/JESSIS 사용법 소개

Frama-C/JESSIS 사용법 소개 Frama-C 프로그램검증시스템소개 박종현 @ POSTECH PL Frama-C? C 프로그램대상정적분석도구 플러그인구조 JESSIE Wp Aorai Frama-C 커널 2 ROSAEC 2011 동계워크샵 @ 통영 JESSIE? Frama-C 연역검증플러그인 프로그램분석 검증조건추출 증명 Hoare 논리에기초한프로그램검증도구 사용법 $ frama-c jessie

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

4. #include <stdio.h> #include <stdlib.h> int main() { functiona(); } void functiona() { printf("hihi\n"); } warning: conflicting types for functiona

4. #include <stdio.h> #include <stdlib.h> int main() { functiona(); } void functiona() { printf(hihi\n); } warning: conflicting types for functiona 이름 : 학번 : A. True or False: 각각항목마다 True 인지 False 인지적으세요. 1. (Python:) randint 함수를사용하려면, random 모듈을 import 해야한다. 2. (Python:) '' (single quote) 는한글자를표현할때, (double quote) 는문자열을표현할때사용한다. B. 다음에러를수정하는방법을적으세요.

More information

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CBED0C3E0C7C1B7CEB1D7B7A55C D616E2E637070>

<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

Discrete Mathematics

Discrete Mathematics 이산수학 () 알고리즘 (Algorithms) 0 년봄학기 강원대학교컴퓨터과학전공문양세 Algorithms The foundation of computer programming. ( 컴퓨터프로그래밍의기초 / 기반이다.) Most generally, an algorithm just means a definite procedure for performing some

More information

Microsoft PowerPoint - 제3장-배열.pptx

Microsoft PowerPoint - 제3장-배열.pptx 제 3 강. 배열 (Array) 자료구조 1 제 3 강. 배열자료구조 학습목차 1. 배열의개념 2. 구조체 3. 희소 (Sparce) 행렬 4. 다차원배열의저장 2 1. 배열의개념 리스트는일상생활에서가장많이쓰이는자료형태이다. 예 ) 학생의명단, 은행거래고객명단, 월별판매액등 배열 (Array) 은컴퓨터언어에서리스트를저장하는데이터타입이다. 리스트와배열은같은개념이지만다른차원의용어이다.

More information

Introduction to Geotechnical Engineering II

Introduction to  Geotechnical Engineering II Fundamentals of Computer System - chapter 9. Functions 민기복 Ki-Bok Min, PhD 서울대학교에너지자원공학과조교수 Assistant Professor, Energy Resources Engineering Last week Chapter 7. C control statements: Branching and Jumps

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 @ Lesson 2... ( ). ( ). @ vs. logic data method variable behavior attribute method field Flow (Type), ( ) member @ () : C program Method A ( ) Method B ( ) Method C () program : Java, C++, C# data @ Program

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 프레젠테이션

PowerPoint 프레젠테이션 Programming Languages 모듈과펑터 2016 년봄학기 손시운 (ssw5176@kangwon.ac.kr) 담당교수 : 임현승교수님 모듈 (module) 관련있는정의 ( 변수또는함수 ) 를하나로묶은패키지 예약어 module과 struct end를사용하여정의 아래는모듈의예시 ( 우선순위큐, priority queue) # module PrioQueue

More information

Microsoft PowerPoint - [2009] 02.pptx

Microsoft PowerPoint - [2009] 02.pptx 원시데이터유형과연산 원시데이터유형과연산 원시데이터유형과연산 숫자데이터유형 - 숫자데이터유형 원시데이터유형과연산 표준입출력함수 - printf 문 가장기본적인출력함수. (stdio.h) 문법 ) printf( Test printf. a = %d \n, a); printf( %d, %f, %c \n, a, b, c); #include #include

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

HW5 Exercise 1 (60pts) M interpreter with a simple type system M. M. M.., M (simple type system). M, M. M., M.

HW5 Exercise 1 (60pts) M interpreter with a simple type system M. M. M.., M (simple type system). M, M. M., M. 오늘할것 5 6 HW5 Exercise 1 (60pts) M interpreter with a simple type system M. M. M.., M (simple type system). M, M. M., M. Review: 5-2 7 7 17 5 4 3 4 OR 0 2 1 2 ~20 ~40 ~60 ~80 ~100 M 언어 e ::= const constant

More information

歯9장.PDF

歯9장.PDF 9 Hello!! C printf() scanf() getchar() putchar() gets() puts() fopen() fclose() fprintf() fscant() fgetc() fputs() fgets() gputs() fread() fwrite() fseek() ftell() I/O 2 (stream) C (text stream) : `/n'

More information

Microsoft PowerPoint - ch00 - Introduction to Programming Language Lecture

Microsoft PowerPoint - ch00 - Introduction to Programming Language Lecture 2014-1 프로그래밍언어 프로그래밍언어강의소개 2014. 3. 1. 교수김영탁 영남대학교공과대학정보통신공학과 (Tel : +82-53-810-2497; Fax : +82-53-810-4742 http://antl.yu.ac.kr/; E-mail : ytkim@yu.ac.kr) 프로그래밍언어강의개요 목적 C 프로그래밍언어를기반으로한공학문제의해결방법습득, C++

More information

컴파일러

컴파일러 YACC 응용예 Desktop Calculator 7/23 Lex 입력 수식문법을위한 lex 입력 : calc.l %{ #include calc.tab.h" %} %% [0-9]+ return(number) [ \t] \n return(0) \+ return('+') \* return('*'). { printf("'%c': illegal character\n",

More information

2007_2_project4

2007_2_project4 Programming Methodology Instructor: Kyuseok Shim Project #4: external sort with template Due Date: 0:0 a.m. between 2007-12-2 & 2007-12-3 Introduction 이프로젝트는 C++ 의 template을이용한 sorting algorithm과정렬해야할데이터의크기가

More information

Microsoft PowerPoint - 제11장 포인터(강의)

Microsoft PowerPoint - 제11장 포인터(강의) 쉽게풀어쓴 C 언어 Express 제 11 장포인터 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습한다. 포인터란? 포인터 (pointer): 주소를가지고있는변수 1003 1004 1005 영화관 1002 1006 1001 포인터 (pointer) 1007 메모리의구조

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

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

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 Chapter 08 함수 01 함수의개요 02 함수사용하기 03 함수와배열 04 재귀함수 함수의필요성을인식한다. 함수를정의, 선언, 호출하는방법을알아본다. 배열을함수의인자로전달하는방법과사용시장점을알아본다. 재귀호출로해결할수있는문제의특징과해결방법을알아본다. 1.1 함수의정의와기능 함수 (function) 특별한기능을수행하는것 여러가지함수의예 Page 4 1.2

More information

A Dynamic Grid Services Deployment Mechanism for On-Demand Resource Provisioning

A Dynamic Grid Services Deployment Mechanism for On-Demand Resource Provisioning C Programming Practice (II) Contents 배열 문자와문자열 구조체 포인터와메모리관리 구조체 2/17 배열 (Array) (1/2) 배열 동일한자료형을가지고있으며같은이름으로참조되는변수들의집합 배열의크기는반드시상수이어야한다. type var_name[size]; 예 ) int myarray[5] 배열의원소는원소의번호를 0 부터시작하는색인을사용

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

김기남_ATDC2016_160620_[키노트].key

김기남_ATDC2016_160620_[키노트].key metatron Enterprise Big Data SKT Metatron/Big Data Big Data Big Data... metatron Ready to Enterprise Big Data Big Data Big Data Big Data?? Data Raw. CRM SCM MES TCO Data & Store & Processing Computational

More information

Microsoft Word - ExecutionStack

Microsoft Word - ExecutionStack Lecture 15: LM code from high level language /* Simple Program */ external int get_int(); external void put_int(); int sum; clear_sum() { sum=0; int step=2; main() { register int i; static int count; clear_sum();

More information

프로그래밍개론및실습 2015 년 2 학기프로그래밍개론및실습과목으로본내용은강의교재인생능출판사, 두근두근 C 언어수업, 천인국지음을발췌수정하였음

프로그래밍개론및실습 2015 년 2 학기프로그래밍개론및실습과목으로본내용은강의교재인생능출판사, 두근두근 C 언어수업, 천인국지음을발췌수정하였음 프로그래밍개론및실습 2015 년 2 학기프로그래밍개론및실습과목으로본내용은강의교재인생능출판사, 두근두근 C 언어수업, 천인국지음을발췌수정하였음 CHAPTER 9 둘중하나선택하기 관계연산자 두개의피연산자를비교하는연산자 결과값은참 (1) 아니면거짓 (0) x == y x 와 y 의값이같은지비교한다. 관계연산자 연산자 의미 x == y x와 y가같은가? x!= y

More information

Microsoft PowerPoint APUE(Intro).ppt

Microsoft PowerPoint APUE(Intro).ppt 컴퓨터특강 () [Ch. 1 & Ch. 2] 2006 년봄학기 문양세강원대학교컴퓨터과학과 APUE 강의목적 UNIX 시스템프로그래밍 file, process, signal, network programming UNIX 시스템의체계적이해 시스템프로그래밍능력향상 Page 2 1 APUE 강의동기 UNIX 는인기있는운영체제 서버시스템 ( 웹서버, 데이터베이스서버

More information

10주차.key

10주차.key 10, Process synchronization (concurrently) ( ) => critical section ( ) / =>, A, B / Race condition int counter; Process A { counter++; } Process B { counter ;.. } counter++ register1 = counter register1

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

Microsoft PowerPoint - a10.ppt [호환 모드]

Microsoft PowerPoint - a10.ppt [호환 모드] Structure Chapter 10: Structures t and Macros Structure 관련된변수들의그룹으로이루어진자료구조 template, pattern field structure를구성하는변수 (cf) C언어의 struct 프로그램의 structure 접근 entire structure 또는 individual fields Structure는

More information

슬라이드 1

슬라이드 1 / 유닉스시스템개요 / 파일 / 프로세스 01 File Descriptor file file descriptor file type unix 에서의파일은단지바이트들의나열임 operating system 은파일에어떤포맷도부과하지않음 파일의내용은바이트단위로주소를줄수있음 file descriptor 는 0 이나양수임 file 은 open 이나 creat 로 file

More information

untitled

untitled Step Motor Device Driver Embedded System Lab. II Step Motor Step Motor Step Motor source Embedded System Lab. II 2 open loop, : : Pulse, 1 Pulse,, -, 1 +5%, step Step Motor (2),, Embedded System Lab. II

More information

Microsoft PowerPoint - chap10-함수의활용.pptx

Microsoft PowerPoint - chap10-함수의활용.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 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

chap8.PDF

chap8.PDF 8 Hello!! C 2 3 4 struct - {...... }; struct jum{ int x_axis; int y_axis; }; struct - {...... } - ; struct jum{ int x_axis; int y_axis; }point1, *point2; 5 struct {....... } - ; struct{ int x_axis; int

More information

untitled

untitled - -, (insert) (delete) - - (insert) (delete) (top ) - - (insert) (rear) (delete) (front) A A B top A B C top push(a) push(b) push(c) A B top pop() top A B D push(d) top #define MAX_STACK_SIZE 100 int

More information

Microsoft PowerPoint - 27.pptx

Microsoft PowerPoint - 27.pptx 이산수학 () n-항관계 (n-ary Relations) 2011년봄학기 강원대학교컴퓨터과학전공문양세 n-ary Relations (n-항관계 ) An n-ary relation R on sets A 1,,A n, written R:A 1,,A n, is a subset R A 1 A n. (A 1,,A n 에대한 n- 항관계 R 은 A 1 A n 의부분집합이다.)

More information

<4D F736F F F696E74202D20B8AEB4AABDBA20BFC0B7F920C3B3B8AEC7CFB1E22E BC8A3C8AF20B8F0B5E55D>

<4D F736F F F696E74202D20B8AEB4AABDBA20BFC0B7F920C3B3B8AEC7CFB1E22E BC8A3C8AF20B8F0B5E55D> 리눅스 오류처리하기 2007. 11. 28 안효창 라이브러리함수의오류번호얻기 errno 변수기능오류번호를저장한다. 기본형 extern int errno; 헤더파일 라이브러리함수호출에실패했을때함수예 정수값을반환하는함수 -1 반환 open 함수 포인터를반환하는함수 NULL 반환 fopen 함수 2 유닉스 / 리눅스 라이브러리함수의오류번호얻기 19-1

More information

슬라이드 1

슬라이드 1 CHAP 2: 순환 (Recursion) 순환 (recursion) 이란? 알고리즘이나함수가수행도중에자기자신을다시호출하여문제를해결하는기법 정의자체가순환적으로 되어있는경우에적합한방법 순환 (recursion) 의예 팩토리얼값구하기 피보나치수열 1 n! n*( n 1)! fib( n) 0 1 fib( n 2) n n 0 ` 1 fib( n 1) if n 0 if

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

예제 1.1 ( 관계연산자 ) >> A=1:9, B=9-A A = B = >> tf = A>4 % 4 보다큰 A 의원소들을찾을경우 tf = >> tf = (A==B) % A

예제 1.1 ( 관계연산자 ) >> A=1:9, B=9-A A = B = >> tf = A>4 % 4 보다큰 A 의원소들을찾을경우 tf = >> tf = (A==B) % A 예제 1.1 ( 관계연산자 ) >> A=1:9, B=9-A A = 1 2 3 4 5 6 7 8 9 B = 8 7 6 5 4 3 2 1 0 >> tf = A>4 % 4 보다큰 A 의원소들을찾을경우 tf = 0 0 0 0 1 1 1 1 1 >> tf = (A==B) % A 의원소와 B 의원소가똑같은경우를찾을때 tf = 0 0 0 0 0 0 0 0 0 >> tf

More information

RVC Robot Vaccum Cleaner

RVC Robot Vaccum Cleaner RVC Robot Vacuum 200810048 정재근 200811445 이성현 200811414 김연준 200812423 김준식 Statement of purpose Robot Vacuum (RVC) - An RVC automatically cleans and mops household surface. - It goes straight forward while

More information

윈도우즈프로그래밍(1)

윈도우즈프로그래밍(1) 제어문 (2) For~Next 문 윈도우즈프로그래밍 (1) ( 신흥대학교컴퓨터정보계열 ) 2/17 Contents 학습목표 프로그램에서주어진특정문장을부분을일정횟수만큼반복해서실행하는문장으로 For~Next 문등의구조를이해하고활용할수있다. 내용 For~Next 문 다중 For 문 3/17 제어문 - FOR 문 반복문 : 프로그램에서주어진특정문장들을일정한횟수만큼반복해서실행하는문장

More information

Microsoft PowerPoint - chap04-연산자.pptx

Microsoft PowerPoint - chap04-연산자.pptx int num; printf( Please enter an integer: "); scanf("%d", &num); if ( num < 0 ) printf("is negative.\n"); printf("num = %d\n", num); } 1 학습목표 수식의 개념과 연산자, 피연산자에 대해서 알아본다. C의 를 알아본다. 연산자의 우선 순위와 결합 방향에

More information

프로그램을 학교 등지에서 조금이라도 배운 사람들을 위한 프로그래밍 노트 입니다. 저 역시 그 사람들 중 하나 입니다. 중고등학교 시절 학교 도서관, 새로 생긴 시립 도서관 등을 다니며 책을 보 고 정리하며 어느정도 독학으르 공부하긴 했지만, 자주 안하다 보면 금방 잊어

프로그램을 학교 등지에서 조금이라도 배운 사람들을 위한 프로그래밍 노트 입니다. 저 역시 그 사람들 중 하나 입니다. 중고등학교 시절 학교 도서관, 새로 생긴 시립 도서관 등을 다니며 책을 보 고 정리하며 어느정도 독학으르 공부하긴 했지만, 자주 안하다 보면 금방 잊어 개나리 연구소 C 언어 노트 (tyback.egloos.com) 프로그램을 학교 등지에서 조금이라도 배운 사람들을 위한 프로그래밍 노트 입니다. 저 역시 그 사람들 중 하나 입니다. 중고등학교 시절 학교 도서관, 새로 생긴 시립 도서관 등을 다니며 책을 보 고 정리하며 어느정도 독학으르 공부하긴 했지만, 자주 안하다 보면 금방 잊어먹고 하더라구요. 그래서,

More information

Microsoft PowerPoint 세션.ppt

Microsoft PowerPoint 세션.ppt 웹프로그래밍 () 2006 년봄학기 문양세강원대학교컴퓨터과학과 세션변수 (Session Variable) (1/2) 쇼핑몰장바구니 장바구니에서는사용자가페이지를이동하더라도장바구니의구매물품리스트의내용을유지하고있어야함 PHP 에서사용하는일반적인변수는스크립트의수행이끝나면모두없어지기때문에페이지이동시변수의값을유지할수없음 이러한문제점을해결하기위해서 PHP 에서는세션 (session)

More information

untitled

untitled while do-while for break continue while( ) ; #include 0 i int main(void) int meter; int i = 0; while(i < 3) meter = i * 1609; printf("%d %d \n", i, meter); i++; return 0; i i< 3 () 0 (1)

More information

Microsoft PowerPoint - 제11장 포인터

Microsoft PowerPoint - 제11장 포인터 쉽게풀어쓴 C 언어 Express 제 11 장포인터 이번장에서학습할내용 포인터이란? 변수의주소 포인터의선언 간접참조연산자 포인터연산 포인터와배열 포인터와함수 이번장에서는포인터의기초적인지식을학습한다. 포인터란? 포인터 (pointer): 주소를가지고있는변수 1003 1004 1005 영화관 1002 1006 1001 포인터 (pointer) 1007 메모리의구조

More information

Microsoft PowerPoint - chap-11.pptx

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

More information

<4D F736F F F696E74202D2031C1D6C2F72D31C2F7BDC32028B0ADC0C7C0DAB7E D20C7C1B7CEB1D7B7A1B9D6BEF0BEEE20B0FAB8F1BCD2B

<4D F736F F F696E74202D2031C1D6C2F72D31C2F7BDC32028B0ADC0C7C0DAB7E D20C7C1B7CEB1D7B7A1B9D6BEF0BEEE20B0FAB8F1BCD2B 2015-1 프로그래밍언어 프로그래밍언어강의소개 2015. 3. 1. 교수김영탁 영남대학교공과대학정보통신공학과 (Tel : +82-53-810-2497; Fax : +82-53-810-4742 http://antl.yu.ac.kr/; E-mail : ytkim@yu.ac.kr) 프로그래밍언어강의개요 목적 C 프로그래밍언어를기반으로한공학문제의해결방법습득, C++

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 Verilog: Finite State Machines CSED311 Lab03 Joonsung Kim, joonsung90@postech.ac.kr Finite State Machines Digital system design 시간에배운것과같습니다. Moore / Mealy machines Verilog 를이용해서어떻게구현할까? 2 Finite State

More information

OCaml

OCaml OCaml 2009.. (khheo@ropas.snu.ac.kr) 1 ML 2 ML OCaml INRIA, France SML Bell lab. & Princeton, USA nml SNU/KAIST, KOREA 3 4 (let) (* ex1.ml *) let a = 10 let add x y = x + y (* ex2.ml *) let sumofsquare

More information

public key private key Encryption Algorithm Decryption Algorithm 1

public key private key Encryption Algorithm Decryption Algorithm 1 public key private key Encryption Algorithm Decryption Algorithm 1 One-Way Function ( ) A function which is easy to compute in one direction, but difficult to invert - given x, y = f(x) is easy - given

More information

13주-14주proc.PDF

13주-14주proc.PDF 12 : Pro*C/C++ 1 2 Embeded SQL 3 PRO *C 31 C/C++ PRO *C NOT! NOT AND && AND OR OR EQUAL == = SQL,,, Embeded SQL SQL 32 Pro*C C SQL Pro*C C, C Pro*C, C C 321, C char : char[n] : n int, short, long : float

More information

Data structure: Assignment 1 Seung-Hoon Na October 1, Assignment 1 Binary search 주어진 정렬된 입력 파일이 있다고 가정하자. 단, 파일내의 숫자는 공백으로 구 분, file내에 숫자들은

Data structure: Assignment 1 Seung-Hoon Na October 1, Assignment 1 Binary search 주어진 정렬된 입력 파일이 있다고 가정하자. 단, 파일내의 숫자는 공백으로 구 분, file내에 숫자들은 Data structure: Assignment 1 Seung-Hoon Na October 1, 018 1 1.1 Assignment 1 Binary search 주어진 정렬된 입력 파일이 있다고 가정하자. 단, 파일내의 숫자는 공백으로 구 분, file내에 숫자들은 multiline으로 구성될 수 있으며, 한 라인에는 임의의 갯수의 숫자가 순서대로 나열될

More information

ºÎ·ÏB

ºÎ·ÏB B B.1 B.2 B.3 B.4 B.5 B.1 2 (Boolean algebra). 1854 An Investigation of the Laws of Thought on Which to Found the Mathematical Theories of Logic and Probabilities George Boole. 1938 MIT Claude Sannon [SHAN38].

More information

< E20C6DFBFFEBEEE20C0DBBCBAC0BB20C0A7C7D12043BEF0BEEE20492E707074>

< E20C6DFBFFEBEEE20C0DBBCBAC0BB20C0A7C7D12043BEF0BEEE20492E707074> Chap #2 펌웨어작성을위한 C 언어 I http://www.smartdisplay.co.kr 강의계획 Chap1. 강의계획및디지털논리이론 Chap2. 펌웨어작성을위한 C 언어 I Chap3. 펌웨어작성을위한 C 언어 II Chap4. AT89S52 메모리구조 Chap5. SD-52 보드구성과코드메모리프로그래밍방법 Chap6. 어드레스디코딩 ( 매핑 ) 과어셈블리어코딩방법

More information

untitled

untitled Logic and Computer Design Fundamentals Chapter 4 Combinational Functions and Circuits Functions of a single variable Can be used on inputs to functional blocks to implement other than block s intended

More information

PowerPoint Presentation

PowerPoint Presentation Class - Property Jo, Heeseung 목차 section 1 클래스의일반구조 section 2 클래스선언 section 3 객체의생성 section 4 멤버변수 4-1 객체변수 4-2 클래스변수 4-3 종단 (final) 변수 4-4 멤버변수접근방법 section 5 멤버변수접근한정자 5-1 public 5-2 private 5-3 한정자없음

More information

쉽게 풀어쓴 C 프로그래밍

쉽게 풀어쓴 C 프로그래밍 제 3 장함수와문자열 1. 함수의기본적인개념을이해한다. 2. 인수와매개변수의개념을이해한다. 3. 함수의인수전달방법 2가지를이해한다 4. 중복함수를이해한다. 5. 디폴트매개변수를이해한다. 6. 문자열의구성을이해한다. 7. string 클래스의사용법을익힌다. 이번장에서만들어볼프로그램 함수란? 함수선언 함수호출 예제 #include using

More information

Microsoft PowerPoint - chap05-제어문.pptx

Microsoft PowerPoint - chap05-제어문.pptx int num; printf( Please enter an integer: "); scanf("%d", &num); if ( num < 0 ) printf("is negative.\n"); printf("num = %d\n", num); 1 학습목표 제어문인,, 분기문에 대해 알아본다. 인 if와 switch의 사용 방법과 사용시 주의사항에 대해 알아본다.

More information

<3130C0E5>

<3130C0E5> Redundancy Adding extra bits for detecting or correcting errors at the destination Types of Errors Single-Bit Error Only one bit of a given data unit is changed Burst Error Two or more bits in the data

More information