Microsoft PowerPoint - ch12 - Graph, Graph Algorithms

Size: px
Start display at page:

Download "Microsoft PowerPoint - ch12 - Graph, Graph Algorithms"

Transcription

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

2 깊이우선탐색 (DFS) 깊이우선탐색 (DFS: depth-first search) 한방향으로갈수있을때까지가다가더이상갈수없게되면가장가까운갈림길로돌아와서이곳으로부터다른방향으로다시탐색진행 되돌아가기위해서는스택필요 ( 순환함수호출로묵시적인스택이용가능 ) ch12-45

3 DFS 알고리즘 depth_first_search(v) v를방문되었다고표시 ; for all u (v에인접한정점 ) do if (u가아직방문되지않았으면 ) then depth_first_search(u) ch12-46

4 DFS 알고리즘 ch12-47

5 DFS 프로그램 // 인접행렬로표현된그래프에대한깊이우선탐색 void dfs_mat(graphtype *g, int v) int w; visited[v] = TRUE; // 정점 v의방문표시 printf("%d ", v); // 방문한정점출력 for(w=0; w<g->n; w++) // 인접정점탐색 if( g->adj_mat[v][w] &&!visited[w] ) dfs_mat(g, w); // 정점 w에서 DFS 새로시작 // 인접리스트로표현된그래프에대한깊이우선탐색 void dfs_list(graphtype *g, int v) GraphNode *w; visited[v] = TRUE; // 정점 v 의방문표시 printf("%d ", v); // 방문한정점출력 for(w=g->adj_list[v]; w; w=w->link) // 인접정점탐색 if(!visited[w->vertex]) dfs_list(g, w->vertex); // 정점 w->vertex 에서 DFS 새로시작 ch12-48

6 너비우선탐색 (BFS) 너비우선탐색 (BFS: breadth-first search) 시작정점으로부터가까운정점을먼저방문하고멀리떨어져있는정점을나중에방문하는순회방법 큐를사용하여구현됨 너비우선탐색알고리즘 breadth_first_search(v) v를방문되었다고표시 ; 큐Q에정점v를삽입 ; while (not is_empty(q)) do 큐 Q에서정점 w를삭제 ; for all u (w에인접한정점 ) do if (u가아직방문되지않았으면 ) then u를큐 Q에삽입 ; u를방문되었다고표시 ; ch12-49

7 ch12-50

8 ch12-51

9 DFS 와 BFS 의 C 프로그램구현 /* Graph.h (5) */ typedef struct Graph Vertex **vrtxptrarr; // vertex array EdgeList *adjlstarr; // adjacency list array int num_vertices; int **ppdistmtrx; Graph(int num_nodes); Graph; typedef struct DepthFirstSearch Graph *pgrp; VertexStatus *pvrtxstatus; EdgeStatus **ppedgestatus; DepthFirstSearch(Graph *pgrp); DFS_DONE searchdone; // used in depth first search int *pleastcost; DepthFirstSearch; /* Graph.h (6) */ typedef struct BreathFirstSearch Graph *pgrp; VertexStatus *pvrtxstatus; int *pleastcost; int *pprev; BFS_PROCSS_STATUS* pbfs_proc_stat; BreathFirstSearch(Graph *pgrp); BreathFirstSearch; void bfstraversal(breathfirstsearch *pbfs, Vertex *pstart, Vertex *ptarget, VertexList *pvtl); void dfstraversal(depthfirstsearch *pdfs, Vertex *pv, Vertex *ptarget, VertexList *pvtl); ch12-52

10 /* Graph.cpp (13) */ DepthFirstSearch::DepthFirstSearch(Graph *pgraph) int num_nodes; pgrp = pgraph; num_nodes = pgrp->num_vertices; pvrtxstatus = (VertexStatus *)malloc(sizeof(vertexstatus)* num_nodes); for (int i = 0; i < num_nodes; i++) pvrtxstatus[i] = VRTX_NOT_VISITED; ppedgestatus = (EdgeStatus **)malloc(sizeof(edgestatus *)* num_nodes); for (int i = 0; i < num_nodes; i++) ppedgestatus[i] = (EdgeStatus *)malloc(sizeof(edgestatus)* num_nodes); for (int i = 0; i < num_nodes; i++) for (int j = 0; j < num_nodes; j++) ppedgestatus[i][j] = EDGE_UNEXPLORED; searchdone = NOT_DONE; // used in depth first search (dfs) traversal pleastcost = (int *)malloc(sizeof(int)* num_nodes); ch12-53

11 /* Graph.cpp (14) */ void dfstraversal(depthfirstsearch *pdfs, Vertex *pv, Vertex *ptarget, VertexList *pvtl) int num_nodes = pdfs->pgrp->num_vertices, num_selected = 0; Vertex *pv2; int **distmtrx = pdfs->pgrp->ppdistmtrx; int *pleastcost = pdfs->pleastcost; int start_id, target_id, cur_id, vrtx_id, v2_id; EdgeList *pel; EdgeListNode *peln; Edge *pe; vrtx_id = pv->id; target_id = ptarget->id; pdfs->pgrp->vrtxptrarr[vrtx_id]->vtxstatus = VRTX_VISITED; if (vrtx_id == target_id) printf("depth First Search is done!! n"); pdfs->searchdone = DONE; return; ch12-54

12 /* Graph.cpp (15) */ pel = &(pdfs->pgrp->adjlstarr[vrtx_id]); peln = pel->pfirst; for (int i = 0; (i < pel->num_edges) & (pdfs->searchdone!= DONE); i++) pe = peln->pe; if (pe->edgestatus == EDGE_UNEXPLORED) pe->edgestatus = EDGE_VISITED; pv2 = pe->pv2; v2_id = pv2->id; if (pv2->vtxstatus!= VRTX_VISITED) listpushback(pvtl, pv2); pdfs->ppedgestatus[vrtx_id][v2_id] = DISCOVERY; if (pdfs->searchdone!= DONE) dfstraversal(pdfs, pv2, ptarget, pvtl); if (pdfs->searchdone!= DONE) Vertex *plast_pushed = pvtl->plast->pv; listpopback(pvtl); else // V2 has been visited already pe->edgestatus = BACK; // end if peln = peln->pnext; // end for ch12-55

13 /* Graph.cpp (16) */ BreathFirstSearch::BreathFirstSearch(Graph *pgraph) pgrp = pgraph; int num_nodes = pgrp->num_vertices; pprev = (int *)malloc(sizeof(int)* num_nodes); pleastcost = (int *)malloc(sizeof(int)* num_nodes); pbfs_proc_stat = (BFS_PROCSS_STATUS*)malloc(sizeof(BFS_PROCSS_STATUS)* num_nodes); void bfstraversal(breathfirstsearch *pbfs, Vertex *pstart, Vertex *ptarget, VertexList *pvtl) int num_nodes = pbfs->pgrp->num_vertices, num_selected = 0; Vertex *pvrtx; int *pleastcost = pbfs->pleastcost; int **distmtrx = pbfs->pgrp->ppdistmtrx; int *pprev = pbfs->pprev; BFS_PROCSS_STATUS *pbfs_proc_stat = pbfs->pbfs_proc_stat; int start_vrtxid, target_vrtxid, cur_vrtxid, vrtxid; int round, minid, mincost; start_vrtxid = pstart->id; target_vrtxid = ptarget->id; /* initialize L(n) = w(start, n) */ for (int i = 0; i < num_nodes; i++) pleastcost[i] = distmtrx[start_vrtxid][i]; pprev[i] = start_vrtxid; pbfs_proc_stat[i] = NOT_SELECTED; pbfs_proc_stat[start_vrtxid] = SELECTED; num_selected = 1; ch12-56

14 /* Graph.cpp (17) */ round = 0; printf("breadth First Search... n"); printdist(pbfs->pgrp->num_vertices, pbfs->pleastcost, round); while (num_selected < num_nodes) round++; //printf("round (%2d) : ", round); // find cur_node with least cost minid = -1; mincost = PLUS_INF; for (int i = 0; i < num_nodes; i++) if ((pleastcost[i] < mincost) & (pbfs_proc_stat[i]!= SELECTED)) minid = i; mincost = pleastcost[i]; if (minid == -1) printf("error in FindShortestPath with bfstraversal() n"); printf(" ==> Target is not connected to the start!! n"); break; else ch12-57

15 /* Graph.cpp (17) */ pbfs_proc_stat[minid] = SELECTED; num_selected++; if (minid == target_vrtxid) // target reached printf(" ==> reached to the target node (%2d) at ", target_vrtxid); printf(" least cost = %d n", mincost); vrtxid = minid; do pvrtx = pbfs->pgrp->vrtxptrarr[vrtxid]; VertexListNode *pvln = (VertexListNode *)malloc(sizeof(vertexlistnode)); pvln->pv = pvrtx; pvln->pnext = pvln->pprev = NULL; if (pvtl->num_vertices == 0) pvtl->pfirst = pvtl->plast = pvln; pvtl->num_vertices++; else pvln->pnext = pvtl->pfirst; pvtl->pfirst->pprev = pvln; pvtl->pfirst = pvln; pvtl->num_vertices++; vrtxid = pprev[vrtxid]; while (vrtxid!= start_vrtxid); ch12-58

16 /* Graph.cpp (17) */ pvrtx = pbfs->pgrp->vrtxptrarr[vrtxid]; // push start node at the front of path VertexListNode *pvln = (VertexListNode *)malloc(sizeof(vertexlistnode)); pvln->pv = pvrtx; pvln->pnext = pvtl->pfirst; pvln->pprev = NULL; pvtl->pfirst = pvln; pvtl->num_vertices++; break; // end if (minid == target_vrtxid) // end if-else int pls, distmtrx_i; for (int i = 0; i < num_nodes; i++) pls = pleastcost[i]; distmtrx_i = distmtrx[minid][i]; if ((pbfs_proc_stat[i]!= SELECTED) & (pleastcost[i] > (pleastcost[minid] + distmtrx[minid][i]))) // update distances with relaxation pprev[i] = minid; pleastcost[i] = pleastcost[minid] + distmtrx[minid][i]; // printout the pleastcost[] for debugging printdist(pbfs->pgrp->num_vertices, pbfs->pleastcost, round); // end while free(pleastcost); free(pprev); ch12-59

17 /* main.cpp (3) */ // Depth First Search printf(" ndepth First Search (DFS)... n"); VertexList vtl_1; initlist(&vtl_1); DepthFirstSearch dfs(&grph); listpushback(&vtl_1, pstart); dfstraversal(&dfs, pstart, ptarget, &vtl_1); printf("dfs::path from start (%2d) to target (%2d): n ", pstart->id, ptarget->id); printlist(&vtl_1); // Breadth First Search printf(" nbreadth First Search (BFS)... n"); VertexList vtl_2; initlist(&vtl_2); BreathFirstSearch bfs(&grph); bfstraversal(&bfs, pstart, ptarget, &vtl_2); printf("shortestpath::path from start (%2d) to target (%2d): n ", pstart->id, ptarget->id); printlist(&vtl_2); ch12-60

18 미로 (Maze) 찾기 Graph representation for Maze vertex: cross point edge: distance between the cross points v0 v1 v2 (start) v3 v4 v5 v6 v7 v8 2 (end) ch12-61

19 ch12-62

20 v0 v1 v2 (start) v3 v4 v5 v6 v7 v8 2 (end) v0 v1 v2 (start) v3 v4 v5 3 2 v6 v7 v8 (end) ch12-63

21 5 x 5 미로 (Maze) 찾기 Find the shortest path from v0 (start) to v20 (end) v0 v1 v2 v3 v4 (start) v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v15 v16 v17 v18 v19 v0 ~ v24: cross points distance(v0, v1): 1 distance(v0, v5): 1 distance(v2, v3): + 4 v20 (end) v21 v22 v23 ch12-64 v24

22 5x5 미로 (Maze) 찾기 Depth First Search example v0 (start) v1 v2 v3 v4 Tracking Back Tracking 1 2 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v0 ~ v24: cross points distance(v0, v1): 1 distance(v0, v5): 1 distance(v2, v3): + 3 v15 v16 v17 v18 v19 4 v20 (end) v21 v22 v23 v24 ch12-65

23 5x5 미로 (Maze) 찾기 Breadth First Search example v0 (start) v1 v2 v3 v4 Tracking 1 2 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v0 ~ v24: cross points distance(v0, v1): 1 distance(v0, v5): 1 distance(v2, v3): + 3 v15 v16 v17 v18 v19 4 v20 (end) v21 v22 v23 v24 ch12-66

24 미로 (Maze) 찾기결과 Sample routes to target (v0 v20) v0 v1 v2 v3 v4 (start) v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 Path by obtained by Depth First Search Path by obtained by Breadth First Search 3 v15 v16 v17 v18 v19 4 v20 v21 v22 v23 v24 (end) ch12-67

25 IP Packet Router 의 Forwarding Table 작성 Input network topology (USA) Seattle San Francisco Los Angels Salt Lake City Phoenix Rapid city Denver Dallas Minneapolis 9 Houston 7 Memphis 454 ch St. Louis Chicago New Orleans Detroit Atlanta 17 Washington D.C Miami Boston New York 237

26 Depth First Search example Find a path from Seattle to Miami Seattle Tracking Back Tracking San Francisco Los Angels Salt Lake City Phoenix Rapid city Denver Dallas Minneapolis 9 Houston 7 Memphis 454 ch St. Louis Chicago New Orleans Detroit Atlanta 17 Washington D.C Miami Boston New York 237

27 Breadth First Search example Find the shortest path from Seattle to Miami Seattle San Francisco Los Angels Salt Lake City Phoenix Rapid city Denver Dallas Minneapolis 9 Houston 7 Memphis 454 ch St. Louis Chicago New Orleans Detroit Atlanta 17 Washington D.C Miami Boston New York 237

28 경로찾기 Path (0 15) produced by Depth First Search (DFS) Path by obtained by Depth First Search Path by obtained by Breadth First Search ch12-71

29 Homework 미로찾기 (1) 다음과같은미로에서임의의시작점 ( 예 : v0) 에서임의의종단점 ( 예 : v24) 까지의경로를찾기위한 Graph 프로그램을작성하고, printgraph() 함수를사용하여, 그래프정보를출력하라. (2) 시작점 (v0) 에서종단점 (v24) 까지의경로를 DFS (Depth First Search) 알고리즘으로찾는프로그램을작성하고, 결과경로를출력하라. (3) 시작점 (v0) 에서종단점 (v24) 까지의경로를 BFS (Breadth First Search) 알고리즘으로찾는프로그램을작성하고, 결과경로를출력하라 v0 (start) v1 v2 v3 v4 1 2 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14 v0 ~ v24: cross points distance(v0, v1): 1 distance(v0, v5): 1 distance(v2, v3): + 3 v15 v16 v17 v18 v19 v20 v21 v22 v23 v24 4 (end) ch12-72

30 12.2 Forwarding Table 구성 (1) 다음과같은네트워크에서 Graph BFS 탐색알고리즘을실행할수있도록 Graph 프로그램을작성하라. (2) 이 Graph 프로그램에서임의의노드로부터다른모든노드로최소비용경로를통하여갈수있는경로들을 BFS 알고리즘을찾는프로그램을작성하라. (3) 임의의지정된노드로부터, 다른모든노드로의최소비용경로를산출한후, 해당목적지로전달되어야하는패킷의 next hop을나타내는 forwarding table을출력하는프로그램을작성하라. ch12-73

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

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

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

More information

11장.그래프

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

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

슬라이드 1

슬라이드 1 CHAP 10 : 그래프 yicho@gachon.ac.kr 1 그래프역사 1800 년대오일러에의하여창안 오일러문제 모든다리를한번만건너서처음출발했던장소로돌아오는문제 A,B,C,D 지역의연결관계표현 위치 : 정점 (node) 다리 : 간선 (edge) 오일러정리 모든정점에연결된간선의수가짝수이면오일러경로존재함 따라서그래프 (b) 에는오일러경로가존재하지않음 2 그래프정의

More information

1장. 리스트

1장. 리스트 01. 그래프를소개합니다 02. 그래프를어떻게표현할것인가? 03. 그래프순회 : 그래프를따라산책하기 04. 최소신장트리 05. 최단경로탐색 06. 위상정렬 라인하르트오일러가 쾨니히스베르크의 7 개의다리문제 를풀기위해고안해낸수학적도구. 7 개의다리를간선 (Edge) 로, 4 개의육지를정점 (Vertex) 로표현. A A Pregel River B C B C D

More information

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

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 CHAP 10 : 그래프 그래프 (graph) 연결되어있는객체간의관계를표현하는자료구조 가장일반적인자료구조형태 우리가배운트리 (tree) 도그래프의특수한경우임 전기회로의소자간연결상태 운영체제의프로세스와자원관계 큰프로젝트에서작은프로젝트간의우선순위 지도에서도시들의연결상태 그래프역사 1800 년대오일러에의하여창안 오일러문제 모든다리를한번만건너서처음출발했던장소로돌아오는문제

More information

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

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

More information

슬라이드 1

슬라이드 1 CHAP 10 : 그래프 그래프 (graph) 연결되어있는객체간의관계를표현하는자료구조 가장일반적인자료구조형태 우리가배운트리 (tree) 도그래프의특수한경우임 전기회로의소자간연결상태 운영체제의프로세스와자원관계 큰프로젝트에서작은프로젝트간의우선순위 지도에서도시들의연결상태 그래프역사 1800 년대오일러에의하여창안 오일러문제 모든다리를한번만건너서처음출발했던장소로돌아오는문제

More information

Chap 6: Graphs

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

More 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

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

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

5장 스택

5장 스택 강의내용 오늘강의내용 ( 월 7 일 ) 중갂고사문제풀이 9. 그래프의숚회. 최소비용신장트리 ( 가중치그래프 ) 예습 ( 월 일 ) : 장가중치그래프 ( 계속 ) 숙제 : 연습문제 (9 장 ) :,,,,,7,8, 번풀어보기 마감일 : 9 년 월 일 ( 화 ) 9. 그래프숚회 그래프숚회 주어진어떤정점을출발하여체계적으로그래프의모든정점들을방문하는것 그래프숚회의종류

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

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

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

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

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

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

7장

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

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

이번장에서학습할내용 동적메모리란? 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

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

More information

쉽게배우는알고리즘 9장. 그래프알고리즘

쉽게배우는알고리즘 9장. 그래프알고리즘 쉽게배우는알고리즘 장. 그래프알고리즘 http://academy.hanb.co.kr 장. 그래프알고리즘 수학은패턴의과학이다. 음악역시패턴들이다. 컴퓨터과학은추상화와패턴의형성에깊은관련이있다. 컴퓨터과학이다른분야들에비해특징적인것은지속적으로차원이 급상승한다는점이다. 미시적관점에서 거시적관점으로도약하는것이다. - 도널드크누스 - - 한빛미디어 학습목표 그래프의표현법을익힌다.

More information

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

쉽게 배우는 알고리즘 강의노트 쉽게배우는알고리즘 ( 한빛미디어 ) 2 장. 상태공간트리의탐색 State-Space Tree State-space tree ( 상태공간트리 ) 문제해결과정의중간상태를각각한노드로나타낸트리 이장에서배우는세가지상태공간탐색기법 Backtracking Branch-and-bound A * algorithm - 2 - 한빛미디어 Travelling Salesman Problem

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

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

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

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

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

Chapter11OSPF

Chapter11OSPF OSPF 111 OSPF Link state Interior Gateway Protocol OSPF 1988 IETF OSPF workgroup OSPF RFC 2383 version 2 Chapter OSPF Version 2 OSPFIGP AS 1 1111 Convergence Traffic Distance Vector Link state OSPF (Flooding),

More information

슬라이드 1

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

More information

1 장 C 언어복습 표준입출력배열포인터배열과포인터함수 const와포인터구조체컴파일러사용방법 C++ 프로그래밍입문

1 장 C 언어복습 표준입출력배열포인터배열과포인터함수 const와포인터구조체컴파일러사용방법 C++ 프로그래밍입문 1 장 C 언어복습 표준입출력배열포인터배열과포인터함수 const와포인터구조체컴파일러사용방법 C++ 프로그래밍입문 1. 표준입출력 표준입출력 입력 : 키보드, scanf 함수 출력 : 모니터, printf 함수문제 : 정수값 2개를입력받고두값사이의값들을더하여출력하라. #include int main(void) int Num1, Num2; int

More information

PowerPoint 프레젠테이션

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

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

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

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

<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

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

서강대학교공과대학컴퓨터공학과 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

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

제 1 장 기본 개념

제 1 장 기본 개념 이진트리순회와트리반복자 트리순회 (tree traversal) 트리에있는모든노드를한번씩만방문 순회방법 : LVR, LRV, VLR, VRL, RVL, RLV L : 왼쪽이동, V : 노드방문, R : 오른쪽이동 왼쪽을오른쪽보다먼저방문 (LR) LVR : 중위 (inorder) 순회 VLR : 전위 (preorder) 순회 LRV : 후위 (postorder)

More information

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

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

More information

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

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

More information

슬라이드 1

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

More information

슬라이드 1

슬라이드 1 CHAP 7: 트리 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 리스트, 스택, 큐등은선형구조 트리는부모 - 자식관계의노드들로이루어진다. 응용분야 : 계층적인조직표현 컴퓨터디스크의디렉토리구조 인공지능에서의결정트리 (decision tree) 회사의조직 파일디렉토리구조 결정트리 ( 예 ) 골프에대한결정트리 트리의용어 노드 (node): 트리의구성요소

More information

08장.트리

08장.트리 ---------------- T STRUTURES USING ---------------- HPTER 트리 /29 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 트리는부모-자식관계의노드들로이루어짐 응용분야 : 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀 생산 팀 생산 2 팀 (a) 회사의조직도 내문서 동영상음악사진 영화예능드라마 여행 (b) 컴퓨터의폴더구조

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

슬라이드 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

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

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

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

슬라이드 1

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

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

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

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CBED0C3E0C7C1B7CEB1D7B7A55C4C656D70656C2D5A69762E637070>

<443A5C4C C4B48555C B3E25C32C7D0B1E25CBCB3B0E8C7C1B7CEC1A7C6AE425CBED0C3E0C7C1B7CEB1D7B7A55C4C656D70656C2D5A69762E637070> /* */ /* LZWIN.C : Lempel-Ziv compression using Sliding Window */ /* */ #include "stdafx.h" #include "Lempel-Ziv.h" 1 /* 큐를초기화 */ void LZ::init_queue(void) front = rear = 0; /* 큐가꽉찼으면 1 을되돌림 */ int LZ::queue_full(void)

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

<C3CA3520B0FAC7D0B1B3BBE7BFEB202E687770>

<C3CA3520B0FAC7D0B1B3BBE7BFEB202E687770> 1. 만화경 만들기 59 2. 물 속에서의 마술 71 3. 비누 탐험 84 4. 꽃보다 아름다운 결정 97 5. 거꾸로 올라가는 물 110 6. 내가 만든 기압계 123 7. 저녁 노을은 맑은 날씨? 136 8. 못생겨도 나는 꽃! 150 9. 단풍잎 색깔 추리 162 10. 고마워요! 지렁이 174 1. 날아라 열기구 188 2. 나 누구게? 198 3.

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

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

슬라이드 제목 없음

슬라이드 제목 없음 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

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

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

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

BGP AS AS BGP AS BGP AS 65250

BGP AS AS BGP AS BGP AS 65250 BGP AS 65000 AS 64500 BGP AS 65500 BGP AS 65250 0 7 15 23 31 BGP Message 16byte Marker 2byte Length, 1byte Type. Marker : BGP Message, BGP Peer.Message Type Open Marker 1.. Length : BGP Message,

More information

Microsoft PowerPoint - 자료구조2008Chap06

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

More information

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

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

More information

Microsoft PowerPoint - ch14 - Hash Map

Microsoft PowerPoint - ch14 - Hash Map 2015-1 14. Hash Map 2015 년 6 월 1 일 교수김영탁 영남대학교공과대학정보통신공학과 (Tel : +82-53-810-2497; Fax : +82-53-810-4742 http://antl.yu.ac.kr/; E-mail : ytkim@yu.ac.kr) Outline Hashing 이란? 사전 (dictionary), map, table과해싱

More information

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

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

More information

슬라이드 1

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

More information

슬라이드 1

슬라이드 1 마이크로컨트롤러 2 (MicroController2) 2 강 ATmega128 의 external interrupt 이귀형교수님 학습목표 interrupt 란무엇인가? 기본개념을알아본다. interrupt 중에서가장사용하기쉬운 external interrupt 의사용방법을학습한다. 1. Interrupt 는왜필요할까? 함수동작을추가하여실행시키려면? //***

More information

int main(void) int a; int b; a=3; b=a+5; printf("a : %d \n", a); printf("b : %d \n", b); a b 3 a a+5 b &a(12ff60) &b(12ff54) 3 a 8 b printf(" a : %x \

int main(void) int a; int b; a=3; b=a+5; printf(a : %d \n, a); printf(b : %d \n, b); a b 3 a a+5 b &a(12ff60) &b(12ff54) 3 a 8 b printf( a : %x \ ? 1 int main(void) int a; int b; a=3; b=a+5; printf("a : %d \n", a); printf("b : %d \n", b); a b 3 a a+5 b &a(12ff60) &b(12ff54) 3 a 8 b printf(" a : %x \n", &a); printf(" b : %x \n", &b); * : 12ff60,

More information

chap x: G입력

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

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

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

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

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

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

ABC 10장

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

More information

슬라이드 1

슬라이드 1 CHAP 8: 우선순위큐 yicho@gachon.ac.kr 1 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다. 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터

More information

04장.큐

04장.큐 ---------------- DATA STRUCTURES USING C ---------------- CHAPTER 큐 1/33 큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 A B C 전단 ( front) 후단 ( rea r) 2/33 큐 ADT 삽입과삭제는 FIFO

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

슬라이드 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

슬라이드 1

슬라이드 1 Data Structure Chapter 8. 우선순위큐 Dong Kyue Kim Hanyang University dqkim@hanyang.ac.kr 우선순위큐추상데이터타입 우선순위큐 우선순위큐 (priority queue) 정의 : 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게됨 스택이나 FIFO 큐를우선순위큐로구현할수있음

More information

歯김병철.PDF

歯김병철.PDF 3G IETF byckim@mission.cnu.ac.kr kckim@konkuk.ac.kr Mobile IP WG Seamoby WG ROHC WG 3G IETF 3G IETF Mobile IP WG 3GIP Seamoby WG ROHC WG MIP WG / NAI Mobile IP / AAA IPv4 / MIP WG RFC2002bis MIPv6 INRIA

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

슬라이드 1

슬라이드 1 CHAP 7: 트리 yicho@gachon.ac.kr 1 트리 (TREE) 트리 : 계층적인구조를나타내는자료구조 리스트, 스택, 큐등은선형구조 트리는부모 - 자식관계의노드들로이루어진다. 응용분야 : 계층적인조직표현 컴퓨터디스크의디렉토리구조 인공지능에서의결정트리 (decision tree) 2 2 회사의조직 대표이사 총무부 영업부 생산부 전산팀구매팀경리팀생산

More information

Algorithms

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

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

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