Chap 6: Graphs

Size: px
Start display at page:

Download "Chap 6: Graphs"

Transcription

1 5. 작업네트워크 (Activity Networks) 작업 (Activity) 부분프로젝트 (divide and conquer) 각각의작업들이완료되어야전체프로젝트가성공적으로완료 두가지종류의네트워크 Activity on Vertex (AOV) Networks Activity on Edge (AOE) Networks 6 장. 그래프 (Page 1)

2 5.1 AOV Network 몇가지정의들 : AOV Network: Digraph G (vertex = 작업, edge = 작업들간의선행관계 ) u 에서 v 까지방향경로 (directed path) 가존재할경우 u = predecessor of v, v = successor of u Immediate Predecessor (Successor): <u, v> Partial Order: transitive 이며 irreflexive 한선행관계 Topological Order: vertex 들간의선행관계를고려하여모든 vertex 의선형순서 (linear ordering) 를정의 Topological Sort 작업들간에는 partial order 만존재할수있으므로, topological order 는여러개존재가능 Topological sort: 그중하나의 topological order 생성 6 장. 그래프 (Page 2)

3 AOV Network 의예 과목번호 과목명 선수과목 C1 C언어 None C2 이산수학 None C3 자료구조 C1, C2 C4 미분적분 I None C5 미분적분 II C4 C6 선형대수 C5 C7 알고리즘분석 C3, C6 C8 어셈블리어 C3 C9 운영체제 C7, C8 C1 프로그래밍언어 C7 C11 컴파일러설계 C1 C12 인공지능 C7 C13 계산이론 C7 C14 병렬알고리즘 C13 C15 수치해석 C5 C1 C2 C4 C3 C5 C8 C7 C6 C15 C9 C1 C12 C13 C11 C14 (b) AOV network representing courses as vertices and edges as prerequisites (a) Courses needed for a computer science degree at a hypothetical university 6 장. 그래프 (Page 3)

4 Program 6.13: Topological Sort for ( i = ; i < n; i++) { if (every vertex has a predecessor) { fprintf (stderr, "Network has a cycle.\ n"); exit (1); } pick a vertex v that has no predecessors; output v; delete v and all edges leading out of v from the network; } 6 장. 그래프 (Page 4)

5 그림 6.39: Topological Sort 의동작 V 1 V 1 V 1 V V 2 V 4 V 2 V 4 V 2 V 4 V 3 V 5 V 3 V 5 V 5 (a) initial (b) V (c) V 3 V 1 V 1 V 4 V 4 V 4 V 5 (d) V 2 (e) V 5 (f) V 1 (g) V 4 생성된 topological order : V, V 3, V 2, V 5, V 1, V 4 6 장. 그래프 (Page 5)

6 AOV Network 의표현 임의의 vertex 가 predecessor 를갖는지조사 각 vertex 에대해 immediate predecessor 의수를나타내는 count field 저장 Vertex 와그에부속된모든 edge 들을삭제 AOV network 을인접리스트로표현 count link struct node { int vertex; struct node *link; }; typedef struct { int count; struct node *link; } hdnode; hdnode graph[max_vertices]; v v 1 v 2 v 3 v 4 v Null 2 Null Null 4 5 Null 5 4 Null 3 Null 6 장. 그래프 (Page 6)

7 Program 6.14: topsort() void topsort(hdnodes graph[], int n) { int i, j, k, top; struct node *ptr; top = -1; // Predecessor가없는 vertex들의 stack 구성 for (i = ; i < n; i++) if (!graph[i].count) { graph[i].count = top; top = i; } for (i = ; i < n; i++) if (top == -1) { fprintf(stderr, "Network has a cycle.\ n"); exit(1); } else { j = top; top = graph[top].count; // Stack에서제거 printf("v%d, ", j); for (ptr = graph[j].link; ptr!= NULL; ptr = ptr->link) { k = ptr->vertex; // Successor vertex들의 count 감소 graph[k].count--; if (!graph[k].count) { // 새로운 vertex를 stack에삽입 graph[k].count = top; top = k; } } } } 6 장. 그래프 (Page 7)

8 5.2 AOE Network AOE Network 의정의 Edge: 작업 Vertex: 사건 (event) vertex 로들어오는모든작업이완료할때발생 vertex 에서나가는작업은사건이발생하기전까지는시작될수없다. start v a = 6 a 2 = 5 a 1 = 4 v 1 v 2 v 3 a 3 = 1 v 4 a 4 = 1 a 5 = 2 v 5 a 6 = 8 a 7 = 6 v 6 v 7 a 8 = 4 a 9 = 2 v 8 a 1 = 4 finish event v v 1 v 4 v 7 v 8 interpretation start of project completion of activity a completion of activity a 3 and a 4 completion of activity a 7 and a 8 completion of project (b) Interpretation of some of the events in the activity graph of (a) (a) AOE Network. Activity graph of a hypothetical project 6 장. 그래프 (Page 8)

9 AOE Network 에서 Critical Path 임계경로 (Critical Path) 시작 vertex 에서종료 vertex 까지가장긴경로 병목현상의원인이됨. Event v i 의 Earliest Time, earliest(i) 시작 vertex v 에서 v i 까지가는가장긴경로의길이 earliest(4) = 7 early(i): 작업 a i 의가장빠른시작시간 a i 가 <k, l> 일경우, early(i) = earliest(k) early(6) = 7 작업 a i 의 Latest Time, late(i) 프로젝트기간을증가시키지않으면서작업이시작될수있는가장나중시간 early(5) = 5 & late(5) = 7, early(7) = 7 & late(7) = 7 임계작업 (Critical Activity) early(i) = late(i) 인작업 a i 6 장. 그래프 (Page 9)

10 Earliest Time 의계산 작업 a i 가 edge <k, l> 로표현된다고가정 early(i) = earliest[k] late(i) = latest[l] duration of a i earliest[j] 의계산 topsort 알고리즘을이용하여시작 vertex 부터 AOE network 를순회 earliest[] = earliest[j] = max{earliest[i] + duration of <i, j>} for i {immediate predecessors of j} 아래문장을 topsort() 함수의 else 절마지막에추가 if (earliest[k] < earliest[j] + ptr->duration) earliest[k] = earliest[j] + ptr->duration 6 장. 그래프 (Page 1)

11 그림 6.42: 그림 6.41 의인접리스트 count link vertex dur link V NULL V NULL V NULL V NULL V NULL V NULL V NULL V NULL V 8 2 NULL 장. 그래프 (Page 11)

12 그림 6.42: earliest 의계산 Earliest [] [1] [2] [3] [4] [5] [6] [7] [8] Stack initial [] output V [3, 2, 1] output V [5, 2, 1] output V [2, 1] output V [1] output V [4] output V [7, 6] output V [6] output V [8] output V 8 6 장. 그래프 (Page 12)

13 Latest Times 의계산 마지막 vertex 부터 topsort 알고리즘을이용하여 AOE network 을역방향으로순회 latest[n-1] = earliest[n-1] latest[j] = min{latest[i] duration of <j, i>} for i {immediate successors of j} 역인접리스트 (inverse adjacency list) 를이용 아래문장을 topsort() 함수의 else 절마지막에추가 if (latest[k] > latest[j] ptr->duration) latest[k] = latest[j] ptr->duration 6 장. 그래프 (Page 13)

14 그림 6.43: 그림 6.41 의역인접리스트 count link vertex dur link V 3 NULL V 1 1 V 2 1 V 3 1 V 4 2 V 5 1 V 6 1 V 7 1 V 8 6 NULL 4 NULL 5 NULL NULL 4 8 NULL NULL 5 4 NULL 7 4 NULL 장. 그래프 (Page 14)

15 그림 6.43: latest 의계산 Earliest [] [1] [2] [3] [4] [5] [6] [7] [8] Stack initial [8] output V [7, 6] output V [5, 6] output V [3, 6] output V [6] output V [4] output V [2, 1] output V [1] output V [] 6 장. 그래프 (Page 15)

16 작업 a i 의 Early(i) 와 Late(i) 계산 작업 a i 가 edge <k, l> 로표현된다고가정 early(i) = earliest[k] late(i) = latest[l] duration of a i Activity Early Late Late Early Critical a a 1 a 2 a 3 a 4 a 5 a 6 a 7 a 8 a 9 a Yes No No Yes No No Yes Yes No Yes Yes 6 장. 그래프 (Page 16)

Chap 6: Graphs

Chap 6: Graphs AOV Network 의표현 임의의 vertex 가 predecessor 를갖는지조사 각 vertex 에대해 immediate predecessor 의수를나타내는 count field 저장 Vertex 와그에부속된모든 edge 들을삭제 AOV network 을인접리스트로표현 count link struct node { int vertex; struct node

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

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

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

11장.그래프

11장.그래프 ---------------- T STRUTURS USIN ---------------- PTR 그래프 1/32 그래프 (graph) 란? 연결되어있는객체간의관계를표현하는자료구조 가장일반적인자료구조형태 그래프의예 트리 (tree) 지도, 지하철노선도 전기회로의연결상태 OS의프로세스와자원관계 인맥지도 2/32 그래프역사 오일러문제 (1800 년대 ) 다리를한번만건너서처음출발했던장소로돌아오는문제

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

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

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

11장 포인터

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

More information

제 6 장 그래프

제 6 장 그래프 제 장 그래프 Copyright DBLAB, Seoul National University 그래프추상데이타타입 () 개요.. Koenigsberg 다리문제 차수 (degree) : 정점에연결된간선의수 오일러행로 (Eulerian walk) c C d g a A Kneiphof B e b D f c a C A B d b e g f D (a) Koenigsberg

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

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

06장.리스트

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

More information

Microsoft PowerPoint - ch12 - Graph, Graph Algorithms

Microsoft PowerPoint - ch12 - Graph, Graph Algorithms 2015-1 12. 그래프와관련알고리즘 2015 년 5 월 28 일 교수김영탁 영남대학교공과대학정보통신공학과 (Tel : +82-53-810-2497; Fax : +82-53-810-4742 http://antl.yu.ac.kr/; E-mail : ytkim@yu.ac.kr) 그래프 (Graph) 그래프의응용예 Outline 미로찾기 인터넷라우터에서의패킷 forwarding

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

歯MW-1000AP_Manual_Kor_HJS.PDF

歯MW-1000AP_Manual_Kor_HJS.PDF Page 2 Page 3 Page 4 Page 5 Page 6 Page 7 Page 8 Page 9 Page 10 Page 11 Page 12 Page 13 Page 14 Page 15 Page 16 Page 17 Page 18 Page 19 Page 20 Page 21 Page 22 Page 23 Page 24 Page 25 Page 26 Page 27 Page

More information

..........(......).hwp

..........(......).hwp START START 질문을 통해 우선순위를 결정 의사결정자가 질문에 답함 모형데이터 입력 목표계획법 자료 목표계획법 모형에 의한 해의 도출과 득실/확률 분석 END 목표계획법 산출결과 결과를 의사 결정자에게 제공 의사결정자가 결과를 검토하여 만족여부를 대답 의사결정자에게 만족하는가? Yes END No 목표계획법 수정 자료 개선을 위한 선택의 여지가 있는지

More information

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

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

More information

1장. 유닉스 시스템 프로그래밍 개요

1장.  유닉스 시스템 프로그래밍 개요 Unix 프로그래밍및실습 7 장. 시그널 - 과제보충 응용과제 1 부모프로세스는반복해서메뉴를출력하고사용자로부터주문을받아자식프로세스에게주문내용을알린다. (SIGUSR1) ( 일단주문을받으면음식이완료되기전까지 SIGUSR1 을제외한다른시그널은모두무시 ) timer 자식프로세스는주문을받으면조리를시작한다. ( 일단조리를시작하면음식이완성되기전까지 SIGALARM 을제외한다른시그널은모두무시

More information

슬라이드 1

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

More information

Microsoft PowerPoint - ch12 - Graph, Graph Algorithms

Microsoft PowerPoint - ch12 - Graph, Graph Algorithms 그래프탐색 (Graph Search) 그래프의가장기본적인연산 하나의정점으로부터시작하여차례대로모든정점들을한번씩방문 많은문제들이단순히그래프의노드를탐색하는것으로해결 ( 예 ) 도로망에서특정도시에서다른도시로갈수있는지여부 ( 예 ) 전자회로에서특정단자와다른단자가서로연결되어있는지여부 ch12-44 깊이우선탐색 (DFS) 깊이우선탐색 (DFS: depth-first search)

More information

Microsoft PowerPoint - 제10장-그래프.pptx

Microsoft PowerPoint - 제10장-그래프.pptx 제 강의. 그래프개념과그래프탐색 학습목차. 그래프의개념. 그래프의표현. 그래프탐색 . 그래프의개념 graph? chart? 오래된그래프문제로다음과 Köenigsberg 다리문제가있다. 이문제는다음과같은지형이있을때임의의한곳 (A,B,C,D) 에서출발하여 a 부터 f 까지 모든다리를한번씩건널수있는가? 하는문제이다. 자료구조의그래프는이러한문제를컴퓨터에표현하고알고리즘을개발하는분야이다.

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

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

<4D F736F F F696E74202D20C1A637C0E52DB0EDB1DEBFACB0E1B8AEBDBAC6AE2E >

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

More information

**Market Ins_잇단

**Market Ins_잇단 2012 2 NETWORK TIMES 149 01. 150 www.datanet.co.kr 2012 2 NETWORK TIMES 151 152 www.datanet.co.kr 2012 2 NETWORK TIMES 153 154 www.datanet.co.kr 2012 2 NETWORK TIMES 155 156 www.datanet.co.kr 02. 2012

More information

**창간특집1-스마트

**창간특집1-스마트 20119 NETWORK TIMES 127 1 2 128 www.datanet.co.kr 20119 NETWORK TIMES 129 130 www.datanet.co.kr 20119 NETWORK TIMES 131 132 www.datanet.co.kr 20119 NETWORK TIMES 133 134 www.datanet.co.kr 1 2 20119 NETWORK

More information

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

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

More information

*½ºÆä¼È¸®Æ÷Æ®-½ºÅ丮Áö

*½ºÆä¼È¸®Æ÷Æ®-½ºÅ丮Áö 201011 NETWORK TIMES 129 130 www.datanet.co.kr 201011 NETWORK TIMES 131 132 www.datanet.co.kr 201011 NETWORK TIMES 133 134 www.datanet.co.kr 201011 NETWORK TIMES 135 136 www.datanet.co.kr 201011 NETWORK

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

CTS사보-2월

CTS사보-2월 2 Program 3 선배님 감사합니다 - CTS은퇴목회자 초청 섬김행사 성황리에 은혜롭게 열려! - 사회전반 이슈 기독교적 관점으로 해석하고 해법 제시 4 후원자 이야기 - 복음 전파를 향한 후원자의 따뜻한 이야기 #이야기 하나 #이야기 둘 # 이야기 셋 5 복음동네이야기 CTS미디어최고위 과정 6기 모집 - 멀티미디어 시대, 스마트목회를 디자인하다! 6

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

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 - Ch_8._Project_Management_(1).ppt [호환 모드]

Microsoft PowerPoint - Ch_8._Project_Management_(1).ppt [호환 모드] Ch 8. Project Management (1) 오중산 11 년 5 월 13 일 PERT/CPM 이란? 프로젝트관리 프로젝트관련일정 / 비용을관리하는것으로두가지기법이있음 PERT (Program Evaluation and Review Technique) and CPM (Critical Path Method) 네트워크모형을이용하여프로젝트와관련된여러가지활동들의일정및비용을관리하여,

More information

슬라이드 1

슬라이드 1 CHAP 10: 그래프 C 로쉽게풀어쓴자료구조 생능출판사 2005 그래프 그래프 (graph): 연결되어있는객체간의관계를표현하는자료구조 그래프의예 : 전기회로, 프로젝트관리, 지도에서도시들의연결 그래프 : 아주일반적인자료구조 ( 예 ) 트리도그래프의일종으로볼수있다. 그래프이론 (graph theory): 그래프를문제해결의도구로이용하는연구분야 그래프역사 1800

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

본 강의에 들어가기 전

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

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

Microsoft PowerPoint Relations.pptx

Microsoft PowerPoint Relations.pptx 이산수학 () 관계와그특성 (Relations and Its Properties) 2010년봄학기강원대학교컴퓨터과학전공문양세 Binary Relations ( 이진관계 ) Let A, B be any two sets. A binary relation R from A to B, written R:A B, is a subset of A B. (A 에서 B 로의이진관계

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 x: G입력

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

More information

<4D F736F F F696E74202D20C1A63137C0E520B5BFC0FBB8DEB8F0B8AEBFCD20BFACB0E1B8AEBDBAC6AE>

<4D F736F F F696E74202D20C1A63137C0E520B5BFC0FBB8DEB8F0B8AEBFCD20BFACB0E1B8AEBDBAC6AE> 쉽게풀어쓴 C 언어 Express 제 17 장동적메모리와연결리스트 이번장에서학습할내용 동적메모리할당의이해 동적메모리할당관련함수 연결리스트 동적메모리할당에대한개념을이해하고응용으로연결리스트를학습합니다. 동적할당메모리의개념 프로그램이메모리를할당받는방법 정적 (static) 동적 (dynamic) 정적메모리할당 정적메모리할당 프로그램이시작되기전에미리정해진크기의메모리를할당받는것

More information

Microsoft PowerPoint - 26.pptx

Microsoft PowerPoint - 26.pptx 이산수학 () 관계와그특성 (Relations and Its Properties) 2011년봄학기 강원대학교컴퓨터과학전공문양세 Binary Relations ( 이진관계 ) Let A, B be any two sets. A binary relation R from A to B, written R:A B, is a subset of A B. (A 에서 B 로의이진관계

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

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 Network Programming Jo, Heeseung Network 실습 네트워크프로그래밍 멀리떨어져있는호스트들이서로데이터를주고받을수있도록프로그램을구현하는것 파일과는달리데이터를주고받을대상이멀리떨어져있기때문에소프트웨어차원에서호스트들간에연결을해주는장치가필요 이러한기능을해주는장치로소켓이라는인터페이스를많이사용 소켓프로그래밍이란용어와네트워크프로그래밍이랑용어가같은의미로사용

More information

선형자료구조 16.1 그래프 배열, 스택, 큐, 리스트를사용하여해결할수있다. 비선형자료구조 순환, 트리, 이진트리로복잡한문제를해결한다. 그래프 (graph) ; 인터넷과같은통신네트워크나고속도로나철도와같은교통네트워크에적합하다. 그래프 (graph) 링크에의해연결되어있는노

선형자료구조 16.1 그래프 배열, 스택, 큐, 리스트를사용하여해결할수있다. 비선형자료구조 순환, 트리, 이진트리로복잡한문제를해결한다. 그래프 (graph) ; 인터넷과같은통신네트워크나고속도로나철도와같은교통네트워크에적합하다. 그래프 (graph) 링크에의해연결되어있는노 16. 그래프 선형자료구조 16.1 그래프 배열, 스택, 큐, 리스트를사용하여해결할수있다. 비선형자료구조 순환, 트리, 이진트리로복잡한문제를해결한다. 그래프 (graph) ; 인터넷과같은통신네트워크나고속도로나철도와같은교통네트워크에적합하다. 그래프 (graph) 링크에의해연결되어있는노드들로구성된구조이다. 노드를정점 (vertex) 이라고부르고, 링크를간선 (edge)

More information

7장

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

More information

chap7.key

chap7.key 1 7 C 2 7.1 C (System Calls) Unix UNIX man Section 2 C. C (Library Functions) C 1975 Dennis Ritchie ANSI C Standard Library 3 (system call). 4 C?... 5 C (text file), C. (binary file). 6 C 1. : fopen( )

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

슬라이드 1

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

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

EA0015: 컴파일러

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

More information

07.pert.cpm

07.pert.cpm 제7장 PRT CPM 일정계획 /7-01 제7장 PRT CPM 일정계획 1. 단독사업 PRT/CPM 일정계획 / 7-0. PRT/CPM 기타문제 / 7-17 3. 기출 예상 문제 및 착안점 / 7-0 7-0 / [최신]기술지도사-생산계획편 1. 단독사업 PRT/CPM 일정계획 [경지 008] [공기 198, 010] * 네트워크 계획 및 통제 기법을 이용하여

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

<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

Ch.8 Procedures and Environments

Ch.8 Procedures and Environments Chapter 10 그래프 (graph) SANGJI University Kwangman KO (kkman@sangji.ac.kr) 그래프 (graph) 그래프 연결되어있는객체간의관계를표현하는자료구조 예 : 전기회로, 프로젝트관리, 지도에서도시들의연결 다양한모델에적용할수있는유연성있는자료구조 연결되어있는객체간의관계를표현하는자료구조 꼭지점 (vertex) 와변

More information

Chapter 10 그래프 (graph) SANGJI University Kwangman KO

Chapter 10 그래프 (graph) SANGJI University Kwangman KO Chapter 10 그래프 (graph) SANGJI University Kwangman KO (kkman@sangji.ac.kr) 그래프 (graph) 그래프 연결되어있는객체간의관계를표현하는자료구조 예 : 전기회로, 프로젝트관리, 지도에서도시들의연결 다양한모델에적용할수있는유연성있는자료구조 연결되어있는객체간의관계를표현하는자료구조 꼭지점 (vertex) 와변

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

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

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

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

예제 1.3 K 5 와 K 3,3 의결합행렬을만들고, 각꼭지점의차수를표시하여라. >> K5 = ones(5,5) - diag(diag(ones(5,5))); degree = sum(k5) degree = 4 4 4 4 4 >> K33 = [zeros(3) ones(3); ones(3) zeros(3)], degree = sum(k33) K33 = 0 0 0

More information

서강대학교공과대학컴퓨터공학과 CSE3081 알고리즘설계와분석 (2 반 ) 기말고사 (2015 년 12 월 17 일 ) 알고리즘설계와분석 (CSE3081(2 반 )) 기말고사 (2015년 12월17일 ( 목 ) 오전 9시 30분 ) 담당교수 : 서강대학교컴퓨터공학과임인성

서강대학교공과대학컴퓨터공학과 CSE3081 알고리즘설계와분석 (2 반 ) 기말고사 (2015 년 12 월 17 일 ) 알고리즘설계와분석 (CSE3081(2 반 )) 기말고사 (2015년 12월17일 ( 목 ) 오전 9시 30분 ) 담당교수 : 서강대학교컴퓨터공학과임인성 알고리즘설계와분석 (CSE3081(2 반 )) 기말고사 (2015년 12월17일 ( 목 ) 오전 9시 30분 ) 담당교수 : 서강대학교컴퓨터공학과임인성대상 : 2학년 2학기생 < 주의 > 문제지는총6쪽이며, 제공한답안지에답을쓴후제출할것. 만약공간이부족하면답안지의뒷면을이용하고반드시답을쓰는칸에어느쪽의뒷면에답을기술하였는지명시할것. 연습지는수거하지않음. 1. 다음은

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

PowerPoint 프레젠테이션

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

More information

**¼Û³âƯÁý2

**¼Û³âƯÁý2 2010 12 NETWORK TIMES 121 SPECIAL 01. 122 www.datanet.co.kr 2010 12 NETWORK TIMES 123 SPECIAL 01. 124 www.datanet.co.kr 2010 12 NETWORK TIMES 125 SPECIAL 02. 126 www.datanet.co.kr 2010 12 NETWORK TIMES

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

Algorithms

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

More information

슬라이드 1

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

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 시스템소프트웨어 : 운영체제, 컴파일러, 어셈블러, 링커, 로더, 프로그래밍도구등 소프트웨어 응용소프트웨어 : 워드프로세서, 스프레드쉬트, 그래픽프로그램, 미디어재생기등 1 n ( x + x +... + ) 1 2 x n 00001111 10111111 01000101 11111000 00001111 10111111 01001101 11111000

More information

01 EDITOR S PICK: 068_ _069

01 EDITOR S PICK: 068_ _069 01 EDITOR S PICK: 068_ _069 070_ _071 02 072_ _073 074_ _075 076_ _077 03 078_ _079 080_ _081 082_ _083 01 086_ _087 088_ _089 090_ _091 092_ _093 094_ _095 02 096_ _097 098_ _099 100_ _101 102_ _103

More information

vi 사용법

vi 사용법 유닉스프로그래밍및실습 gdb 사용법 fprintf 이용 단순디버깅 확인하고자하는코드부분에 fprintf(stderr, ) 를이용하여그지점까지도달했는지여부와관심있는변수의값을확인 여러유형의단순한문제를확인할수있음 그러나자세히살펴보기위해서는디버깅툴필요 int main(void) { int count; long large_no; double real_no; init_vars();

More information

05_tree

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

More information

슬라이드 1

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

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

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

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

Microsoft PowerPoint - 05-chap03-ArrayAndPointer.ppt

Microsoft PowerPoint - 05-chap03-ArrayAndPointer.ppt 배열이란? Chapter. 배열구조체포인터 같은형의변수를여러개만드는경우에사용 int A, A, A, A,, A; int A[]; 4 5 6 반복코드등에서배열을사용하면효율적인프로그래밍이가능 예 ) 최대값을구하는프로그램 : 만약배열이없었다면? tmp=score[]; for(i=;i tmp ) tmp = score[i]; Today...

More information

11 템플릿적용 - Java Program Performance Tuning (김명호기술이사)

11 템플릿적용 - Java Program Performance Tuning (김명호기술이사) Java Program Performance Tuning ( ) n (Primes0) static List primes(int n) { List primes = new ArrayList(n); outer: for (int candidate = 2; n > 0; candidate++) { Iterator iter = primes.iterator(); while

More information

chap 5: Trees

chap 5: Trees Chapter 5. TREES 목차 1. Introduction 2. 이진트리 (Binary Trees) 3. 이진트리의순회 (Binary Tree Traversals) 4. 이진트리의추가연산 5. 스레드이진트리 (Threaded Binary Trees) 6. 히프 (Heaps) 7. 이진탐색트리 (Binary Search Trees) 8. 선택트리 (Selection

More information

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

PowerPoint Template

PowerPoint Template 18 동적할당과고급처리 인터넷정보과 1 2/19 동적할당 목적 다음과같은일반변수의선언과사용은변수를정적 (static) 으로사용 int a = 10; 메모리사용예측이부정확한경우는충분한메모리를미리확보해야하는것은비효율 동적 (dynamic) 메모리할당 (Memory Allocation) 동적인메모리할당을위해서는함수 malloc() 을이용, 메모리공간을확보 함수 malloc()

More information

Chapter #01 Subject

Chapter #01  Subject Device Driver March 24, 2004 Kim, ki-hyeon 목차 1. 인터럽트처리복습 1. 인터럽트복습 입력검출방법 인터럽트방식, 폴링 (polling) 방식 인터럽트서비스등록함수 ( 커널에등록 ) int request_irq(unsigned int irq, void(*handler)(int,void*,struct pt_regs*), unsigned

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.1 관계

4.1 관계 심볼테이블 사전 (dictionary) 철자검색기, 시소러스, 데이터베이스관리응용에서데이터사전 로더, 어셈블러, 컴파일러에의해생성되는심볼테이블 컴퓨터분야에서는심볼테이블이라는용어를사용 심볼테이블 이름 - 속성쌍의집합 C++ 에서 map words ; words[ time ] = 1 ; 시소러스는이름은단어, 속성은동의어 컴파일러는이름은식별자로,

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

Microsoft PowerPoint - 부호기와 복호기.PPT

Microsoft PowerPoint - 부호기와 복호기.PPT 논리회로실험부호기와복호기 2005. 5. 3. 부호기와복호기란? 이론실험내용 개요 Encoder & Decoder 서로다른부호간의변환에사용되는것으로디지털신호를압축하거나전송시깨지지않도록바꾸는등여러가지목적에의해부호화라는장치와부호화되어전송되어온신호를다시원래의디지털신호로복호하는장치들을말한다. CODEC(enCOder DECoder) 이라고도한다. 기타 10진 to

More information

제목

제목 Development Technology Seminar 작 성 자 : 고형호 이 메 일 : hyungho.ko@gmail.com 최초작성일 : 2007.01.19 최종작성일 : 2007.02.05 버 전 : 01.05 홈 피 : www.innosigma.com Goal Exception Handling 1. SEH vs. CEH Exception Handling

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

강의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

Microsoft PowerPoint Predicates and Quantifiers.ppt

Microsoft PowerPoint Predicates and Quantifiers.ppt 이산수학 () 1.3 술어와한정기호 (Predicates and Quantifiers) 2006 년봄학기 문양세강원대학교컴퓨터과학과 술어 (Predicate), 명제함수 (Propositional Function) x is greater than 3. 변수 (variable) = x 술어 (predicate) = P 명제함수 (propositional function)

More information

Data structure: Assignment 3 Seung-Hoon Na December 14, 2018 레드 블랙 트리 (Red-Black Tree) 1 본 절에서는 레드 블랙 트리를 2-3트리 또는 2-3-4트리 대한 동등한 자료구조로 보고, 두 가지 유형의 레

Data structure: Assignment 3 Seung-Hoon Na December 14, 2018 레드 블랙 트리 (Red-Black Tree) 1 본 절에서는 레드 블랙 트리를 2-3트리 또는 2-3-4트리 대한 동등한 자료구조로 보고, 두 가지 유형의 레 Data structure: Assignment 3 Seung-Hoon Na December 14, 2018 레드 블랙 트리 (Red-Black Tree) 1 본 절에서는 레드 블랙 트리를 2-3트리 또는 2-3-4트리 대한 동등한 자료구조로 보고, 두 가지 유형의 레드 블랙 트리를 구현하고자 한다. 1.1 2-3트리와 동등한 레드 블랙 트리 2-3트리와 동등한

More information

슬라이드 1

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

More information

untitled

untitled 1 hamks@dongguk.ac.kr (goal) (abstraction), (modularity), (interface) (efficient) (robust) C Unix C Unix (operating system) (network) (compiler) (machine architecture) 1 2 3 4 5 6 7 8 9 10 ANSI C Systems

More information