chap01_time_complexity.key

Size: px
Start display at page:

Download "chap01_time_complexity.key"

Transcription

1 1 :

2 (resource),,, 2

3 (time complexity),,, (worst-case analysis) (average-case analysis) 3

4 (Asymptotic) n growth rate Θ-, Ο- ( ) 4

5 : n data, n/2. int sample( int data[], int n ) { int k = n/2 ; return data[k] ; n. O(1). 5

6 : n data,. int sum(int data[], int n) { int sum = 0 ; for (int i = 0; i < n; i++) sum = sum + data[i]; return sum;, n. n n, n. O(n). 6

7 : data target. int search(int n, int data[], int target) { for (int i=0; i<n; i++) { if (data[i] == target) return i; return -1;, n. O(n). 7

8 Quadratic x. bool is_distinct( int n, int x[] ) { for (int i=0; i<n-1; i++) for (int j=i+1; j<n; j++) if (x[i]==x[j]) return false; return true;, n(n-1)/2. n(n-1)/2. O(n 2 ). 8

9 ? for (i=1; i<n; i*=2) { // Do something? 9

10 10

11 f(n) 2 O(g(n)) if there exist constant c>0 and n 0 0 such that for all n n 0 we have f(n) apple cg(n) f(n) = 32n n 2 32 f(n) 2 O(n 2 ) but also f(n) 2 O(n 3 ) and O(n 2 log n) 11

12 f(n) 2 (g(n)) if there exist constant c>0 and n 0 0 such that for all n n 0 we have f(n) cg(n). f(n) = 32n n 2 32 f(n) 2 (n 2 ) but also f(n) 2 (n) and (n log n) 12

13 :Θ- f(n) 2 (g(n)) if there exist constants c 1 > 0,c 2 > 0, and n 0 0 such that for all n n 0 we have 0 apple c 1 g(n) apple f(n) apple c 2 g(n). f(n) 2 (g(n)) if f(n) 2 O(g(n)) and f(n) 2 (g(n)) f(n) = 32n n 2 32 f(n) 2 (n 2 ) but f(n) 62 (n 3 ),f(n) 62 (n) 13

14 f(n) =O(g(n)) f(n) 2 O(g(n)) k 0 O(n k ) f(n) =c k n k + c k 1 n k c 1 n + c 0 = O(n k ) p q O(n max{p,q ) If g(n) =O(n p ) and h(n) =O(n q ), then f(n) =g(n)+h(n) =O(n max(p,q) ) 14

15 A B A = O(B)? A = (B)? log k n n k p n n c n n sin n 2 n 2 n/2 n log c c log n log(n!) log(n n ) 15

16 16 Common Growth Rate

17 17 Common Growth Rate

18 18 Common Growth Rate

19 19

20 20

21 (Binary Search). target Dustin Caryn Debbie Dustin Elliot Jacquie Jonathon Rich first = 0 middle = 3 last = 6 21

22 (Binary Search). target Dustin Caryn Debbie Dustin Elliot Jacquie Jonathon Rich first = 0 last = 2 middle = 1 22

23 (Binary Search). target Dustin Caryn Debbie Dustin Elliot Jacquie Jonathon Rich first= middle = last = 2 23

24 data n. int binarysearch(int n, char *data[], char *target) { int begin = 0, end = n-1; while(begin <= end) { int middle = (begin + end)/2; int result = strcmp(data[middle], target); if (result == 0) return middle; else if (result < 0) begin = middle+1; else end = middle-1; return -1;. O(log2n). 24

25 ? (middle) O(1). O(n) O(log2n).. 25

26 (bubble sort) void bubblesort(int data[], int n) { for ( int i=n-1; i>0; i--) { for ( int j=0; j<i; j++ ) { if (data[j] > data[j+1]) { int tmp = data[j]; data[j] = data[j+1]; data[j+1] = tmp;? 26

27 (Insertion sort) void insertion_sort(int n, int data[]) { for ( int i=1; i<n; i++) { int tmp = data[i]; int j = i-1; while (j>=0 && data[j]>data[i]) { data[j+1] = data[j]; j ; data[j+1] = tmp; data[i] 를 data[0] ~ data[i-1] i i i i? 27

28 (quicksort) O(n 2 ), O(nlog2n) O(nlog2n) (merge sort) (heap sort)? 28

29 Code Review 29

30 push and pop: void push(stack s, Item i) { if (is_full(s)) reallocate(s); s->top++; s->contents[s->top] = i; Item pop(stack s) { if (is_empty(s)) terminate("error in pop: stack is empty. ); s->top -; return s->contents[s->top+1]; n reallocate O(n). reallocate O(1). pop() O(1). 30

31 push and pop: void push(stack s, Item i) { struct node *new_node = malloc(sizeof(struct node)); if (new_node == NULL) terminate("error in push: stack is full."); new_node->data = i; new_node->next = s->top; s->top = new_node; Item pop(stack s) { struct node *old_top; Item i; if (is_empty(s)) terminate("error in pop: stack is empty."); old_top = s->top; i = old_top->data; s->top = old_top->next; free(old_top); return i; push pop O(1). 31

32 enqueue and dequeue reallocate enqueue dequeue O(1). enqueue dequeue O(1). 32

33 (ordered list) : void insert_to_ordered_array(int n, int data[], int item) { int i = n-1; for (; i>=0 && data[i]>item; i--) data[i+1] = data[i]; data[i+1] = item; O(n). 33

34 (ordered list) : Node *insert_to_ordered_linked_list(node *head, int item) { Node *new_node = (Node *)malloc(sizeof(node)); new_node->data = item; new_node->next = NULL; Node *p = head, *q=null; while (p!=null && p->data < item) { q = p; p = p->next; if (q==null) { new_node->next = head; head = new_node; else { new_node->next = p; q->next = new_node; return head; O(n)... 34

35 a b A B m n C. c void merge_sorted_arrays(int m, int a[], int n, int b[], int c[]) { for (int i=0; i<m; i++) a c c[i] = a[i]; for (int j=0; j<n; j++) b c insert. insert_to_ordered_array(m+j, c, b[j]); O(mn). 35

36 a b c void merge_sorted_arrays_linear(int m, int a[], int n, int b[], int c[]) { int i=0, j=0, k=0; while (i<m && j<n) { if (a[i] <= b[j]) c[k++] = a[i++]; else c[k++] = b[j++]; while(i<m) c[k++] = a[i++]; while(j<n) c[k++] = b[j++]; O(m+n). 36

37 Node *merge_two_ordered_list(node *first, Node *second) { /* insert nodes of the second list into the first list */ Node *p = second; Node *q = first; while (p!=null) { Node *the_node = p; p = p->next; first = insert_to_ordered_list(first); return first; O(mn). 37

38 2 Node *merge_two_ordered_lists2(node *first, Node *second) { Node *head = NULL, *tail = NULL; Node *tmp; while (first!= NULL && second!= NULL) { if (first->data <= second->data) { tmp = first; first = first->next; else { tmp = second; second = second->next; first tmp->next = NULL; if (tail == NULL) { head = tail = tmp; else { tail->next = tmp; tail = tmp; second head tail 38

39 2 first NULL if (first!= NULL) tail->next = first; else if (second!= NULL) tail->next = second; return head; second head tail O(m+n). 39

40 3 Node *merge_two_ordered_list3(node *first, Node *second) { /* insert nodes of second into first */ Node *p = second; Node *q = first, *pre_q = NULL; while (p!=null) { Node *the_node = p; p = p->next; while(q!=null && q->data < the_node->data) { pre_q = q; q = q->next; if (pre_q == NULL) { /* add p at the front */ the_node->next = first; first = the_node; else { /* add after pre_q */ the_node->next = q; pre_q->next = the_node; pre_q = the_node; return first; O(m+n). 40

41 Node *inverse_list(node *head) { if (head == NULL head->next == NULL) return head; Node *p = head; Node *q = NULL; /* before p */ Node *r = p->next; /* next to p */ while (p!= NULL) { p->next = q; q = p; p = r; if (r!=null) r = r->next; return q; O(n). 41

42 Node *remove_all_divisible(node *head, int divisor) { Node *p = head; Node *q = NULL, *deleted = NULL; while(p!=null) { if (p->data%divisor == 0) { if (q==null) head = p->next; else q->next = p->next; deleted = p; p = p->next; free(deleted); else { q = p; p = p->next; return head; O(n). 42

43 int maze() { Stack s = create(); Position cur; cur.x = 0; cur.y = 0; int init_dir = 0; /* */ while(1) { maze[cur.x][cur.y] = VISITED; /* visited */ if (cur.x == n-1 && cur.y == n-1) { break; bool forwarded = false; for (int dir = init_dir; dir<4; dir++) { if (movable(cur, dir)) { push(s, dir); cur = move_to(cur, dir); forwarded = true; init_dir = 0; break; if (!forwarded) { maze[cur.x][cur.y] = BACKTRACKED; /* backtracked */ if (is_empty(s)) break; int d = pop(s); cur = move_to(cur, (d+2)%4); init_dir = d+1; 2 4. O(n 2 ). 43

44 Queue queue = create_queue(); Position cur; cur.x = 0; cur.y = 0; enqueue(queue, cur); maze[0][0] = -1; bool found = false; while(!is_empty(queue)) { Position cur = dequeue(queue); for (int dir=0; dir<4; dir++) { if (movable(cur, dir)) { Position p = move_to(cur, dir); maze[p.x][p.y] = maze[cur.x][cur.y] - 1; if (p.x == n-1 && p.y == n-1) { printf("found the path.\n"); found = true; break; enqueue(queue, p); 2. O(n 2 ). 44

5.스택(강의자료).key

5.스택(강의자료).key CHP 5: https://www.youtube.com/watch?v=ns-r91557ds ? (stack): (LIFO:Last-In First-Out):. D C B C B C B C B (element) C (top) B (bottom) (DT) : n element : create() ::=. is_empty(s) ::=. is_full(s) ::=.

More information

11강-힙정렬.ppt

11강-힙정렬.ppt 11 (Heap ort) leejaku@shinbiro.com Topics? Heap Heap Opeations UpHeap/Insert, DownHeap/Extract Binary Tree / Index Heap ort Heap ort 11.1 (Priority Queue) Operations ? Priority Queue? Priority Queue tack

More information

03장.스택.key

03장.스택.key ---------------- DATA STRUCTURES USING C ---------------- 03CHAPTER 1 ? (stack): (LIFO:Last-In First-Out) 2 : top : ( index -1 ),,, 3 : ( ) ( ) -> ->. ->.... 4 Stack ADT : (LIFO) : init():. is_empty():

More information

03_queue

03_queue Queue Data Structures and Algorithms 목차 큐의이해와 ADT 정의 큐의배열기반구현 큐의연결리스트기반구현 큐의활용 덱 (Deque) 의이해와구현 Data Structures and Algorithms 2 큐의이해와 ADT 정의 Data Structures and Algorithms 3 큐 (Stack) 의이해와 ADT 정의 큐는 LIFO(Last-in,

More information

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

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

6장정렬알고리즘.key

6장정렬알고리즘.key 6 : :. (Internal sort) (External sort) (main memory). :,,.. 6.1 (Bubbble Sort).,,. 1 (pass). 1 pass, 1. (, ), 90 (, ). 2 40-50 50-90, 50 10. 50 90. 40 50 10 비교 40 50 10 비교 40 50 10 40 10 50 40 10 50 90

More information

Chapter 4. LISTS

Chapter 4. LISTS C 언어에서리스트구현 리스트의생성 struct node { int data; struct node *link; ; struct node *ptr = NULL; ptr = (struct node *) malloc(sizeof(struct node)); Self-referential structure NULL: defined in stdio.h(k&r C) or

More information

Chapter 4. LISTS

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

More information

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

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

A Hierarchical Approach to Interactive Motion Editing for Human-like Figures 단일연결리스트 (Singly Linked List) 신찬수 연결리스트 (linked list)? tail 서울부산수원용인 null item next 구조체복습 struct name_card { char name[20]; int date; } struct name_card a; // 구조체변수 a 선언 a.name 또는 a.date // 구조체 a의멤버접근 struct

More information

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

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

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

61 62 63 64 234 235 p r i n t f ( % 5 d :, i+1); g e t s ( s t u d e n t _ n a m e [ i ] ) ; if (student_name[i][0] == \ 0 ) i = MAX; p r i n t f (\ n :\ n ); 6 1 for (i = 0; student_name[i][0]!= \ 0&&

More information

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

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

More information

C프로-3장c03逞풚

C프로-3장c03逞풚 C h a p t e r 03 C++ 3 1 9 4 3 break continue 2 110 if if else if else switch 1 if if if 3 1 1 if 2 2 3 if if 1 2 111 01 #include 02 using namespace std; 03 void main( ) 04 { 05 int x; 06 07

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

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

K&R2 Reference Manual 번역본

K&R2 Reference Manual 번역본 typewriter structunion struct union if-else if if else if if else if if if if else else ; auto register static extern typedef void char short int long float double signed unsigned const volatile { } struct

More information

슬라이드 1

슬라이드 1 CHAP 5 : 스택 yicho@gachon.ac.kr 1 5.1 스택추상데이터타입 스택 (stack) 이란?: 쌓아놓은더미 2 스택의특징 후입선출 (LIFO:Last-In First-Out): 가장최근에들어온데이터가가장먼저나감. D C B C B C B C B A A A A 3 스택의구조 요소 (element) 스택에저장되는것 C 스택상단 (top) : 스택에서입출력이이루어지는부분

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

ABC 10장

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

More information

06장.리스트

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

More information

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

Microsoft PowerPoint - ch10 - 이진트리, AVL 트리, 트리 응용 pm0600 균형이진탐색트리 -VL Tree delson, Velskii, Landis에의해 1962년에제안됨 VL trees are balanced n VL Tree is a binary search tree such that for every internal node v of T, the heights of the children of v can differ by at

More information

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

chap x: G입력

chap x: G입력 원형큐 (Circular Queue) [2] [3] [2] [3] [1] [4] [1] [4] [0] [5] front = 0, rear = 0 [2] [3] [0] [5] front = 0, rear = 3 [1] [4] [0] [5] front = 0, rear = 0 최대큐이용률 = MAX_Q_SIZE 1 3 장. 스택과큐 (Page 13) 원형큐의구현

More information

슬라이드 1

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

More information

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

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

More information

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

Microsoft PowerPoint - 07-chap05-Stack.ppt

Microsoft PowerPoint - 07-chap05-Stack.ppt / 스택이란? 스택 stack): 쌓아놓은더미 hapter 5 스택 Dongwon Jeong djeong@kunsan.ac.kr Department of Informatics & Statistics 학습목표 스택의개념이해 스택의동작원리이해 배열과연결리스트를이용한스택구현 스택응용프로그램 스택의특징 후입선출 LIFO:Last-In First-Out) 가장최근에들어온데이터가가장먼저나감.

More information

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CC0E7B0EDB0FCB8AE5C53746F636B5F4D616E D656E74732E637070>

<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 information

untitled

untitled 1. void inorder(tree_ptr ptr) { if(ptr) { inorder(ptr->left_child); printf( %d,ptr->data); inorder(ptr->right_child); 2) => A / B * C * D + E () A / B * C * D + E void preorder(tree_ptr ptr) { if(ptr)

More information

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

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

More information

슬라이드 제목 없음

슬라이드 제목 없음 Chapter 5: TREES Trees Trees Def) a tree is finite set of one or more nodes such that 1) there is a special node (root) 2) remaining nodes are partitioned into n 0 disjoint trees T 1,T 2,,T n where each

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 @ Lesson 3 if, if else, if else if, switch case for, while, do while break, continue : System.in, args, JOptionPane for (,, ) @ vs. logic data method variable Data Data Flow (Type), ( ) @ Member field

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

데이터구조 (Chapter 3: Stacks and Queues) 2011 년봄학기 숙명여자대학교이과대학멀티미디어과학과박영호

데이터구조 (Chapter 3: Stacks and Queues) 2011 년봄학기 숙명여자대학교이과대학멀티미디어과학과박영호 데이터구조 (Chapter 3: Stacks and Queues) 2011 년봄학기 숙명여자대학교이과대학멀티미디어과학과박영호 Index Chapter 01: Basic Concepts Chapter 02: Arrays and Structures Chapter 03: Stacks and Queues Chapter 04: Lists Chapter 05: Trees

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

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

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

More information

Algorithms

Algorithms 자료구조 & 알고리즘 스택과큐 (Stack and Queue) Seo, Doo-okok clickseo@gmail.com http://www.clickseo.com 목 차 스택의개념및구현 큐의개념및구현 2 스택 스택의개념및구현 스택의구현 스택의응용 큐의개념및구현 3 스택 (Stack) 스택의구조 후입선출 (LIFO, Last-In-First-Out) 삽입 PUSH

More information

슬라이드 1

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

More information

슬라이드 1

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

More information

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

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

More information

Microsoft PowerPoint - 자료구조2008Chap06

Microsoft PowerPoint - 자료구조2008Chap06 제 6 장연결리스트 연결리스트개요 2 일정한순서를가지는데이터요소들을표현하는방법중의하나이다. 배열과다르게데이터요소들의논리적인순서만유지되고기억장소내에서는각데이터요소들은논리적인순서와는상관없는임의의위치를가지도록하는자료구조이다. 연결리스트에서는각데이터요소들이기억장소내의어떤위치에어떤항목이있는지를표시해주어야한다. 이를위해데이터요소에는데이터값 (value) 뿐만아니라위치정보

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

슬라이드 1

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

More information

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

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

More information

슬라이드 1

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

More information

중간고사 (자료 구조)

중간고사 (자료 구조) Data Structures 215 중간고사 문제에서명시적으로기술하지않은부분은교재의내용에근거함. 215. 1. 27. 1 다음용어에대하여간단하게설명하시오 ( 각 3 점 *1=3 점 ) 1 abstract data type 6 Circular linked list 2 recursion 3 time complexity 4 space complexity 5 Single

More information

Microsoft PowerPoint - ch07_스택 [호환 모드]

Microsoft PowerPoint - ch07_스택 [호환 모드] 스택 (Stack) 자바로배우는쉬운자료구조 이장에서다룰내용 1 스택 2 스택의추상자료형 3 스택의구현 4 스택의응용 2 스택 (1) 스택 (stack) 접시를쌓듯이자료를차곡차곡쌓아올린형태의자료구조 스택에저장된원소는 top 으로정한곳에서만접근가능 top 의위치에서만원소를삽입하므로먼저삽입한원소는밑에쌓이고, 나중에삽입한원소는위에쌓인다. 마지막에삽입 (Last-In)

More information

<4D F736F F F696E74202D20C1A637C0E52DB0EDB1DEBFACB0E1B8AEBDBAC6AE2E >

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

More information

11장 포인터

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

More information

슬라이드 1

슬라이드 1 C programming and Data Structures Overview T. H. Cormen, C. E. Leiserson and R. L. Rivest Introduction to, 3rd Edition, MIT Press, 2009 Sungkyunkwan University Hyunseung Choo choo@skku.edu Copyright 2000-2018

More information

untitled

untitled if( ) ; if( sales > 2000 ) bonus = 200; if( score >= 60 ) printf(".\n"); if( height >= 130 && age >= 10 ) printf(".\n"); if ( temperature < 0 ) printf(".\n"); // printf(" %.\n \n", temperature); // if(

More information

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

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

More information

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

저작자표시 - 비영리 - 변경금지 2.0 대한민국 이용자는아래의조건을따르는경우에한하여자유롭게 이저작물을복제, 배포, 전송, 전시, 공연및방송할수있습니다. 다음과같은조건을따라야합니다 : 저작자표시. 귀하는원저작자를표시하여야합니다. 비영리. 귀하는이저작물을영리목적으로이용할

저작자표시 - 비영리 - 변경금지 2.0 대한민국 이용자는아래의조건을따르는경우에한하여자유롭게 이저작물을복제, 배포, 전송, 전시, 공연및방송할수있습니다. 다음과같은조건을따라야합니다 : 저작자표시. 귀하는원저작자를표시하여야합니다. 비영리. 귀하는이저작물을영리목적으로이용할 저작자표시 - 비영리 - 변경금지 2.0 대한민국 이용자는아래의조건을따르는경우에한하여자유롭게 이저작물을복제, 배포, 전송, 전시, 공연및방송할수있습니다. 다음과같은조건을따라야합니다 : 저작자표시. 귀하는원저작자를표시하여야합니다. 비영리. 귀하는이저작물을영리목적으로이용할수없습니다. 변경금지. 귀하는이저작물을개작, 변형또는가공할수없습니다. 귀하는, 이저작물의재이용이나배포의경우,

More information

chap x: G입력

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

More information

CompareAndSet(CAS) 함수는 address 주소의값이 oldvalue 인지비교해서같으면 newvalue 로 바꾼다. 소프트웨어 lock 을사용하는것이아니고, 하드웨어에서제공하는기능이므로더빠르고 간편하다. X86 에서는 _InterlockedCompareEx

CompareAndSet(CAS) 함수는 address 주소의값이 oldvalue 인지비교해서같으면 newvalue 로 바꾼다. 소프트웨어 lock 을사용하는것이아니고, 하드웨어에서제공하는기능이므로더빠르고 간편하다. X86 에서는 _InterlockedCompareEx NON-BLOCKING ALGORITHM Homepage: https://sites.google.com/site/doc4code/ Email: goldpotion@outlook.com 2011/10/23 멀티쓰레드환경에서알아두면유용한자료구조에대해소개해본다. HARDWARE PRIMITIVE 효율적인구현을위해, Hardware 에서제공하는기능을이용해야한다. 자주쓰는기능에대해

More information

UI TASK & KEY EVENT

UI TASK & KEY EVENT KEY EVENT & STATE 구현 2007. 1. 25 PLATFORM TEAM 정용학 차례 Key Event HS TASK UI TASK LONG KEY STATE 구현 소스코드및실행화면 질의응답및토의 2 KEY EVENT - HS TASK hs_task keypad_scan_keypad hs_init keypad_pass_key_code keypad_init

More information

4장

4장 CHAP 5: 스택 스택이란? 스택 (stack): 쌓아놓은더미 스택의특징 후입선출 (LIFO:Last-In First-Out): 가장최근에들어온데이터가가장먼저나감. D C B C B C B C B A A A A 스택의구조 요소 (element) C 스택상단 (top) B A 스택하단 (bottom) 스택추상데이터타입 (ADT) 객체 : n개의 element형의요소들의선형리스트

More information

»ê¾÷¿¬±¸¿øÇ¥Áö

»ê¾÷¿¬±¸¿øÇ¥Áö Contents Contents Contents Contents Contents Contents Contents 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 Z = X i - X S S, X 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52

More information

<4D F736F F F696E74202D20C1A63132B0AD20B5BFC0FB20B8DEB8F0B8AEC7D2B4E7>

<4D F736F F F696E74202D20C1A63132B0AD20B5BFC0FB20B8DEB8F0B8AEC7D2B4E7> 제14장 동적 메모리 할당 Dynamic Allocation void * malloc(sizeof(char)*256) void * calloc(sizeof(char), 256) void * realloc(void *, size_t); Self-Referece NODE struct selfref { int n; struct selfref *next; }; Linked

More information

C 언어 강의노트

C 언어 강의노트 C언어 (CSE2035) (15-1 Lists) Linear list 의구성, Insertion, deletion 윤용운, Ph.D. Dept. of Computer Science and Engineering Sogang University Seoul, Korea Tel: 010-3204-6811 Email : yuyoon0@sogang.ac.kr 2018-01-11

More information

Microsoft PowerPoint - ch08_큐 [호환 모드]

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

More information

Microsoft PowerPoint - chap-11.pptx

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

More information

슬라이드 1

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

More information

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 자료형 기본자료형 : char, int, float, double 등 파생자료형 : 배열, 열거형, 구조체, 공용체 vs struct 구조체 _ 태그 _ 이름 자료형멤버 _ 이름 ; 자료형멤버 _ 이름 ;... ; struct student int number; // char name[10]; // double height; // ; // x값과 y값으로이루어지는화면의좌표

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

본 강의에 들어가기 전

본 강의에 들어가기 전 C 기초특강 종합과제 과제내용 구조체를이용하여교과목이름과코드를파일로부터입력받아관리 구조체를이용하여학생들의이름, 학번과이수한교과목의코드와점수를파일로부터입력 학생개인별총점, 평균계산 교과목별이수학생수, 총점및평균을계산 결과를파일에저장하는프로그램을작성 2 Makefile OBJS = score_main.o score_input.o score_calc.o score_print.o

More information

슬라이드 1

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

More information

Microsoft PowerPoint - 08-Queue.ppt

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

More information

3. 1 포인터란 3. 2 포인터변수의선언과사용 3. 3 다차원포인터변수의선언과사용 3. 4 주소의가감산 3. 5 함수포인터

3. 1 포인터란 3. 2 포인터변수의선언과사용 3. 3 다차원포인터변수의선언과사용 3. 4 주소의가감산 3. 5 함수포인터 - Part2-3 3. 1 포인터란 3. 2 포인터변수의선언과사용 3. 3 다차원포인터변수의선언과사용 3. 4 주소의가감산 3. 5 함수포인터 3.1 포인터란 ü ü ü. ü. ü. ü ( ) ? 3.1 ü. ü C ( ).? ü ü PART2-4 ü ( ) PART3-4 3.2 포인터변수의선언과사용 3.2 포인터 변수의 선언과 사용 (1/8) 포인터 변수의

More information

chap x: G입력

chap x: G입력 3. 미로찾기 (Mazing Problem) 2 차원배열을이용한미로의구현 maze[row][column]: 0 길, 1 벽 그림 3.8 참조 이동방향 8 방향 (N, NE, E, SE, S, SW, W, NW) 각방향에대한 maze 배열의첨자변환 : 그림 3.9 경계지역 : 8 방향이아님. ( 모서리 : 3 방향, 변 : 5 방향 ) m p 미로를 (m +

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

신림프로그래머_클린코드.key

신림프로그래머_클린코드.key CLEAN CODE 6 11st Front Dev. Team 6 1. 2. 3. checked exception 4. 5. 6. 11 : 2 4 : java (50%), javascript (35%), SQL/PL-SQL (15%) : Spring, ibatis, Oracle, jquery ? , (, ) ( ) 클린코드를 무시한다면 . 6 1. ,,,!

More information

문서의 제목 나눔명조R, 40pt

문서의 제목  나눔명조R, 40pt 이문서는나눔글꼴로작성되었습니다. 설치하기 11차시 : 함수동적메모리할당다차원배열 프로그래밍및실험 제 11주 동국대학교조영석 6.6 함수인자로써의배열 - 함수정의에서배열로선언된형식매개변수는 pointer임. - 함수의인자로배열이전달되면배열의기본주소가 ( 배열의내용이아님 ) call-by-value로전달됨. - 배열원소는복사되지않음. 2 ( 예 ) #include

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

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

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

More information

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

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

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

More information

WISHBONE System-on-Chip Interconnection Architecture for Portable IP Cores

WISHBONE System-on-Chip Interconnection Architecture for Portable IP Cores 프로젝트정리 1주차 : 미로를텍스트파일로만들어출력하는프로그램작성. 2주차 : 텍스트형태의미로를 MC의그래픽기능을이용하여그리는프로그램작성. 3주차 : 미로에서길찾는프로그램작성. Dept. of CS, Sogang Univ. 1 DS를이용한미로길찾기문제 DS를이용한미로길찾기문제는 2주차까지설계한미로의출발점과도착점을연결하는가장짧은경로를탐색해출력하는문제이다. NxM

More information

USER GUIDE

USER GUIDE Solution Package Volume II DATABASE MIGRATION 2010. 1. 9. U.Tu System 1 U.Tu System SeeMAGMA SYSTEM 차 례 1. INPUT & OUTPUT DATABASE LAYOUT...2 2. IPO 중 VB DATA DEFINE 자동작성...4 3. DATABASE UNLOAD...6 4.

More information

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

리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L = n ( item0, item1,..., item -1) l 리스트의예 l 요일 : ( 일요일, 월요일,, 토요일 ) l 한글자음의모임 : ( ㄱ, ㄴ 00. 리스트 자료구조 01. 링크드 리스트 02. 더블 링크드 리스트 03. 환형 링크드 리스트 리스트 (list), 선형리스트 (linear list): 순서를가진항목들의모임 집합 : 항목간의순서의개념이없음 L = n ( item0, item1,..., item -1) l 리스트의예 l 요일 : ( 일요일, 월요일,, 토요일 ) l 한글자음의모임 : (

More information

1장. 리스트

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

More information

Javascript.pages

Javascript.pages JQuery jquery part1 JavaScript : e-mail:leseraphina@naver.com http://www.webhard.co.kr I.? 2 ......,,. : : html5 ; ; .

More information

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

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

More information

(Microsoft Word - \301\337\260\243\260\355\273\347.docx)

(Microsoft Word - \301\337\260\243\260\355\273\347.docx) 내장형시스템공학 (NH466) 중간고사 학번 : 이름 : 문제 배점 점수 1 20 2 20 3 20 4 20 5 10 6 10 7 15 8 20 9 15 합계 150 1. (20 점 ) 다음용어에대해서설명하시오. (1) 정보은닉 (Information Hiding) (2) 캡슐화 (Encapsulation) (3) 오버로딩 (Overloading) (4) 생성자

More information

Microsoft PowerPoint - 08-chap06-Queue.ppt

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

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 동적할당 Heeseung Jo 이장의내용 동적할당개념동적할당활용동적할당과스택자기참조구조체 2 동적할당개념 메모리할당에따른변수분류 할당과해제 할당 (allocation): 변수를나타내기위해메모리일부를점유하는것 해제 (deallocation): 더이상변수가필요없을때, 변수를위해점유해두었던메모리를반납하는것 메모리할당방법에따른변수분류 변수구분 정적변수 동적변수 변수종류전역변수,

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 C 언어포인터정복하기 16 강. 포인터로자료구조화하기 TAE-HYONG KIM COMPUTER ENG, KIT 2 학습내용 구조체멤버와구조체포인터멤버 다른구조체 ( 변수 ) 를가리키는구조체 ( 변수 ) 연결된리스트 의구성및관리 포인터로 연결된리스트 탐색하기 3 중첩구조체에자료저장하기 중첩된구조체변수에값저장하기 struct person { char PRID[15];

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

106 107, ( ),, ( ), 3, int kor[5]; int eng[5]; int Microsoft Windows 4 (ANSI C2 ) int kor[5] 20 # define #define SIZE 20 int a[10]; char c[10]; float

106 107, ( ),, ( ), 3, int kor[5]; int eng[5]; int Microsoft Windows 4 (ANSI C2 ) int kor[5] 20 # define #define SIZE 20 int a[10]; char c[10]; float Part 2 31 32 33 106 107, ( ),, ( ), 3, int kor[5]; int eng[5]; int Microsoft Windows 4 (ANSI C2 ) int kor[5] 20 # define #define SIZE 20 int a[10]; char c[10]; float f[size]; /* 10 /* c 10 /* f 20 3 1

More information

09-interface.key

09-interface.key 9 Database insert(record r): boolean find(key k): Record 1 Record getkey(): Key * Record Key Database.? Key equals(key y): boolean Database insert(record r): boolean find(key k): Record * Database OK 1

More information

untitled

untitled 年 識 料 ˍˍˍˍˍˍ 不 80 1.25 2 1~80 不 1 列 array A n n matrix 零 lower triangular matrix 列 來 n n(n+1)/2 n(n 1)/2 n n 2 例 行 Y[1][3] 列 INT Y[4][4]; FOR(I=0; I

More information

hlogin7

hlogin7 0x07. Return Oriented Programming ROP? , (DEP, ASLR). ROP (Return Oriented Programming) (excutable memory) rop. plt, got got overwrite RTL RTL Chain DEP, ASLR gadget Basic knowledge plt, got call function

More information

; struct point p[10] = {{1, 2, {5, -3, {-3, 5, {-6, -2, {2, 2, {-3, -3, {-9, 2, {7, 8, {-6, 4, {8, -5; for (i = 0; i < 10; i++){ if (p[i].x > 0 && p[i

; struct point p[10] = {{1, 2, {5, -3, {-3, 5, {-6, -2, {2, 2, {-3, -3, {-9, 2, {7, 8, {-6, 4, {8, -5; for (i = 0; i < 10; i++){ if (p[i].x > 0 && p[i ; struct point p; printf("0이아닌점의좌표를입력하시오 : "); scanf("%d %d", &p.x, &p.y); if (p.x > 0 && p.y > 0) printf("1사분면에있다.\n"); if (p.x < 0 && p.y > 0) printf("2사분면에있다.\n"); if (p.x < 0 && p.y < 0) printf("3사분면에있다.\n");

More information

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

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

More information