슬라이드 1

Size: px
Start display at page:

Download "슬라이드 1"

Transcription

1 CHAP 10 : 그래프

2 그래프 (graph) 연결되어있는객체간의관계를표현하는자료구조 가장일반적인자료구조형태 우리가배운트리 (tree) 도그래프의특수한경우임 전기회로의소자간연결상태 운영체제의프로세스와자원관계 큰프로젝트에서작은프로젝트간의우선순위 지도에서도시들의연결상태

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

4 그래프정의 그래프 G는 (V, E) 로표시 정점 (vertices) 여러가지특성을가질수있는객체의미 V(G) : 그래프 G의정점들의집합 노드 (node) 라고도불림 간선 (edge) 정점들간의관계의미 E(G) : 그래프 G의간선들의집합 링크 (link) 라고도불림

5 그래프의종류 무방향그래프 (undirected graph) 무방향간선 (undirected edge) 만사용 간선을통해서양방향으로갈수있음 도로의왕복통행길 (A, B) 와같이정점의쌍으로표현 (A, B) = (B, A) A B 방향그래프 (directed graph) 방향간선 (undirected edge) 만사용 간선을통해서한쪽방향으로만갈수있음 도로의일방통행길 <A, B> 와같이정점의쌍으로표현 <A, B> <B, A> A B

6 가중치그래프 가중치그래프 (weighted graph) 는네트워크 (network) 라고도함 간선에비용 (cost) 이나가중치 (weight) 가할당된그래프 A 1200 B 가중치그래프예 정점 : 각도시를의미 간선 : 도시를연결하는도로의미 가중치 : 도로의길이

7 그래프표현의예 V(G1)= {0, 1, 2, 3, E(G1)= {(0, 1), (0, 2), (0, 3), (1, 2), (2, 3) V(G2)= {0, 1, 2, 3, E(G3)= {(0, 1), (0, 2)) V(G2)= {0, 1, 2, E(G2)= {<0, 1>, <1, 0>, <1, 2>

8 부분그래프 (subgraph) 정점집합 V(G) 와간선집합 E(G) 의부분집합으로이루어진그래프 그래프 G1 의부분그래프들

9 인접정점 (adjacent vertex) 그래프 하나의정점에서간선에의해직접연결된정점 G1에서정점 0의인접정점 : 정점 1, 정점 2, 정점 3 무방향그래프의차수 (degree) 하나의정점에연결된다른정점의수 G1에서정점 0의차수 : 3 무방향그래프의모든차수의합은간선수의 2배 G1의차수의합 : 10 G1의간선의합 : 5

10 방향그래프의차수 (degree) 그래프 진입차수 (in-degree) : 외부에서오는간선의수 진출차수 (out-degree) : 외부로향하는간선의수 G3에서정점 1의차수 : 내차수 1, 외차수 2 방향그래프의모든진입 ( 진출 ) 차수의합은간선의수 G3의진입차수의합 : 3 G3의진입차수의합 : 3 G3의간선합 : 3

11 그래프의경로 (path) 무방향그래프의정점 s 로부터정점 e 까지의경로 정점의나열 s, v1, v2,..., vk, e 나열된정점들간에반드시간선 (s, v1), (v1, v2),..., (vk, e) 존재 방향그래프의정점 s 로부터정점 e 까지의경로 정점의나열 s, v1, v2,..., vk, e 나열된정점들간에반드시간선 <s, v1>, <v1, v2>,...,<vk, e> 존재 경로의길이 (length) 경로를구성하는데사용된간선의수 단순경로 (simple path) 경로중에서반복되는간선이없는경로 사이클 (cycle) 단순경로의시작정점과종료정점이동일한경로

12 그래프의경로 (path) G1의 0, 1, 2,3은경로지만 0, 1, 3, 2는경로아님 G1의1, 0, 2, 3은단순경로이지만 1, 0, 2, 0은단순경로아님 G1의 0, 1, 2, 0과 G3의 0, 1, 0은사이클

13 그래프의연결정도 연결그래프 (connected graph) 무방향그래프 G에있는모든정점쌍에대하여항상경로존재 G2는비연결그래프임 트리 (tree) 그래프의특수한형태로서사이클을가지지않는연결그래프 트리의예

14 그래프의연결정도 완전그래프 (complete graph) 모든정점이연결되어있는그래프 n개의정점을가진무방향완전그래프의간선의수 : n (n-1)/2 n=4, 간선의수 = (4 3)/2 = 6

15 그래프 ADT 객체 : 정점의집합과간선의집합 연산 : create_graph() ::= 그래프를생성한다. init(g) ::= 그래프 g 를초기화한다. insert_vertex(g,v) ::= 그래프 g 에정점 v 를삽입한다. insert_edge(g,u,v) ::= 그래프 g 에간선 (u,v) 를삽입한다. delete_vertex(g,v) ::= 그래프 g 의정점 v 를삭제한다. delete_edge(g,u,v) ::= 그래프 g 의간선 (u,v) 를삭제한다. is_empty(g) ::= 그래프 g 가공백상태인지확인한다. adjacent(v) ::= 정점 v 에인접한정점들의리스트를반환한다. destroy_graph(g) ::= 그래프 g 를제거한다. 그래프에정점을추가하려면 insert_vertex 연산사용 그래프에간선을추가하려면 insert_edge 연산사용

16 그래프표현방법 인접행렬 (adjacent matrix) 방법 if( 간선 (i, j) 가그래프에존재 ) M[i][j] = 1, 그렇지않으면 M[i][j] = 0. 인접행렬의대각선성분은모두 0( 자체간선불허 ) 무방향그래프의인접행렬은대칭

17 그래프표현방법 (cont.) 인접리스트 (adjacency list) 방법 각정점에인접한정점들을연결리스트로표현

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

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

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

21 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 에서 DFS 새로시작

22 너비우선탐색 (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 를큐에삽입 ; u 를방문되었다고표시 ;

23

24 BFS 프로그램 ( 인접행렬 ) void bfs_mat(graphtype *g, int v) { int w; QueueType q; init(&q); visited[v] = TRUE; printf("%d ", v); enqueue(&q, v); while(!is_empty(&q)){ // 큐초기화 // 정점 v 방문표시 // 정점출력 // 시작정점을큐에저장 v = dequeue(&q); // 큐에정점추출 for(w=0; w<g->n; w++) // 인접정점탐색 if(g->adj_mat[v][w] &&!visited[w]){ visited[w] = TRUE; printf("%d ", w); enqueue(&q, w); // 방문표시 // 정점출력 // 방문한정점을큐에저장

25 BFS 프로그램 ( 인접리스트 ) void bfs_list(graphtype *g, int v) { GraphNode *w; QueueType q; init(&q); visited[v] = TRUE; printf("%d ", v); enqueue(&q, v); while(!is_empty(&q)){ // 큐초기화 // 정점 v 방문표시 // 정점 v 출력 // 시작정점을큐에저장 v = dequeue(&q); // 큐에서정점추출 for(w=g->adj_list[v]; w; w = w->link) // 인접정점탐색 if(!visited[w->vertex]){ // 미방문정점탐색 visited[w->vertex] = TRUE; // 방문표시 printf("%d ", w->vertex); // 정점출력 enqueue(&q, w->vertex); // 방문한정점을큐에삽입

26 연결성분 최대로연결된부분그래프들 DFS 또는 BFS 반복이용 DFS 또는 BFS 탐색프로그램의 visited[v]=true; 를 visited[v]=count; 로교체 void find_connected_component(graphtype *g) { int i; count = 0; for(i=0; i<g->n; i++) if(!visited[i]){ // 방문되지않았으면 count++; dfs_mat(g, i);

27 신장트리 (spanning tree) 그래프내의모든정점을포함하는트리 모든정점들이연결되어있어야하고사이클을포함해서는안됨 n개의정점을가지는그래프의신장트리는 n-1개의간선을가짐 최소의링크를사용하는네트워크구축시사용 : 통신망, 도로망, 유통망등 신장트리알고리즘 depth_first_search(v) v를방문되었다고표시 ; for all u (v에인접한정점 ) do if (u가아직방문되지않았으면 ) then (v,u) 를신장트리간선이라고표시 ; depth_first_search(u);

28 신장트리

29 최소비용신장트리 (MST: minimum spanning tree) 네트워크에있는모든정점들을가장적은수의간선과비용으로연결 MST의응용 도로건설 - 도시들을모두연결하면서도로의길이를최소가되도록하는문제 전기회로 - 단자들을모두연결하면서전선의길이를가장최소로하는문제 통신 - 전화선의길이가최소가되도록전화케이블망을구성하는문제 배관 - 파이프를모두연결하면서파이프의총길이를최소로하는문제

30 Kruskal 의 MST 알고리즘 탐욕적인방법 (greedy method) 주요알고리즘설계기법 각단계에서최선의답을선택하는과정을반복함으로써최종적인해답에도달 탐욕적인방법은항상최적의해답을주는지검증필요 Kruskal MST 알고리즘은최적의해답임이증명됨

31 Kruskal 의 MST 알고리즘 MST 는최소비용의간선으로구성됨과동시에사이클을포함하지않아야함 각단계에서사이클을이루지않는최소비용간선선택 그래프의간선들을가중치의오름차순으로정렬 정렬된간선중에서사이클을형성하지않는간선을현재의 MST 집합에추가 만약사이클을형성하면그간선은제외

32

33 Kruskal 의 MST 알고리즘 union-find 알고리즘 두집합들의합집합만듬 원소가어떤집합에속하는지알아냄 Kruskal의 MST 알고리즘에서사이클검사에사용 a 와 b 가같은집합에속함 a 와 b 가다른집합에속함

34 union-find 프로그램 int parent[max_vertices]; int num[max_vertices]; void set_init(int n) {int i; for(i=0;i<n;i++){ parent[i] = -1; num[i] = 1; int set_find(int vertex) {int p, s, i=-1; for(i=vertex;(p=parent[i])>=0;i=p) ; s = i; for(i=vertex;(p=parent[i])>=0;i=p) parent[i] = s; return s; // 부모노드 // 각집합의크기 // 초기화 // vertex가속하는집합반환 // 루트노드까지반복 // 집합의대표원소 // 집합의모든원소들의부모를 s로설정 void set_union(int s1, int s2) if( num[s1] < num[s2] ){ parent[s1] = s2; num[s2] += num[s1]; else { parent[s2] = s1; num[s1] += num[s2]; // 두개의원소가속한집합을합함

35 Kruskal 의 MST 프로그램 #include <stdio.h> #define MAX_VERTICES 100 #define INF 1000 // 프로그램 10.7의 union-find 프로그램삽입 //... // 히프의요소타입정의 typedef struct { int key; int u; // 정점 1 int v; // 정점 2 // 간선의가중치 element; // 프로그램 8.5 중에서최소히프프로그램삽입 //... // 정점 u와정점 v를연결하는가중치가 weight인간선을히프에삽입 void insert_heap_edge(heaptype *h, int u, int v, int weight) { element e; e.u = u; e.v = v; e.key = weight; insert_min_heap(h, e); // 인접행렬이나인접리스트에서간선들을읽어서최소히프에삽입 // 현재는예제그래프의간선들을삽입한다. void insert_all_edges(heaptype *h){ insert_heap_edge(h,0,1,29); insert_heap_edge(h,1,2,16); insert_heap_edge(h,2,3,12); insert_heap_edge(h,3,4,22); insert_heap_edge(h,4,5,27); insert_heap_edge(h,5,0,10); insert_heap_edge(h,6,1,15); insert_heap_edge(h,6,3,18); insert_heap_edge(h,6,4,25); C 로쉽게풀어쓴자료구조 생능출판사 2011

36 Kruskal 의 MST 프로그램 (cont.) // kruskal의최소비용신장트리프로그램 void kruskal(int n) { int edge_accepted=0; // 현재까지선택된간선의수 HeapType h; // 최소히프 int uset, vset; // 정점 u와정점 v의집합번호 element e; // 히프요소 init(&h); // 히프초기화 insert_all_edges(&h); // 히프에간선들을삽입 set_init(n); // 집합초기화 while( edge_accepted < (n-1) ) // 간선의수 < (n-1) { e = delete_min_heap(&h); // main() { kruskal(7); uset = set_find(e.u); vset = set_find(e.v); if( uset!= vset ){ // 최소히프에서삭제 // 정점 u의집합번호 // 정점 v의집합번호 // 서로속한집합이다르면 printf("(%d,%d) %d \n",e.u, e.v, e.key); edge_accepted++; set_union(uset, vset); // 두개의집합을합친다.

37 Kruskal 의 MST 알고리즘복잡도 Kruskal 알고리즘은대부분간선들을정렬하는시간에좌우됨 사이클테스트등의작업은정렬에비해매우신속하게수행됨 네트워크의간선 e 개를퀵정렬과같은효율적인알고리즘으로정렬한다면 Kruskal 알고리즘의시간복잡도는 O(e*log(e)) 가된다

38 Prim 의 MST 알고리즘 시작정점에서부터출발하여신장트리집합을단계적으로확장해나감 시작단계에서는시작정점만이신장트리집합에포함됨 신장트리집합에인접한정점중에서최저간선으로연결된정점선택하여신장트리집합에추가함 이과정은신장트리집합이 n-1 개의간선을가질때까지반복 간선 (a, b)=29 간선 (f, e)=27 간선 (f, e) 선택 정점 e 가신장트 리집합에추가됨

39 Prim 의 MST 알고리즘

40

41 Prim 의 MST 프로그램 #include <stdio.h> #define TRUE 1 #define FALSE 0 #define MAX_VERTICES 7 #define INF 1000L int weight[max_vertices][max_vertices]={ { 0, 29, INF, INF, INF, 10, INF, { 29, 0, 16, INF, INF, INF, 15, { INF, 16, 0, 12, INF, INF, INF, { INF, INF, 12, 0, 22, INF, 18, { INF, INF, INF, 22, 0, 27, 25, { 10, INF, INF, INF, 27, 0, INF, { INF, 15, INF, 18, 25, INF, 0 ; int selected[max_vertices]; int dist[max_vertices]; // 최소 dist[v] 값을갖는정점을반환 int get_min_vertex(int n) { int v,i; for (i = 0; i <n; i++) if (!selected[i]) { v = i; break; for (i = 0; i < n; i++) if (!selected[i] && (dist[i] < dist[v])) v = i; return (v);

42 Prim 의 MST 프로그램 (cont.) void prim(int s, int n) { int i, u, v; for(u=0;u<n;u++) dist[u]=inf; dist[s]=0; for(i=0;i<n;i++){ u = get_min_vertex(n); selected[u]=true; if( dist[u] == INF ) return; printf("%d ", u); for( v=0; v<n; v++) if( weight[u][v]!= INF) if(!selected[v] && weight[u][v]< dist[v] ) dist[v] = weight[u][v]; // main() { prim(0, MAX_VERTICES);

43 Prim 의 MST 알고리즘복잡도 주반복문이정점의수 n 만큼반복하고, 내부반복문이 n 번반복하므로 Prim 의알고리즘은 O(n2) 의복잡도를가진다. 희박한그래프 O(e*log(e)) 인 Kruskal 의알고리즘이유리 밀집한그래프 O(n 2 ) 인 Prim 의알고리즘이유리

44 최단경로 (shortest path) 네트워크에서정점 u 와정점 v 를연결하는경로중에서간선들의가중치합이최소가되는경로 간선의가중치는비용, 거리, 시간등 정점 0 에서정점 3 으로가는최단경로문제 인접행렬에서간선이없는노드쌍의가중치는 임 0,4,1,2,3 이최단경로 최단경로길이는 =11

45 Dijkstra 의최단경로알고리즘 하나의시작정점으로부터모든다른정점까지의최단경로찾음 집합 S 시작정점 v 로부터의최단경로가이미발견된정점들의집합 distance 배열 최단경로가알려진정점들만을이용한다른정점들까지의최단경로길이 distance 배열의초기값 ( 시작정점 v) distance[v] = 0 다른정점에대한 distance 값은시작정점과해당정점간의가중치값 매단계에서가장 distance 값이작은정점을 S 에추가

46 Dijkstra 의최단경로알고리즘 distance 값이가장작은정점을 u 라고하자. 그러면시작정점 v 에서정점 u 까지의최단거리는경로 1 이된다. 정점 w 를거쳐서정점 u 로가는가상적인더짧은경로가있다고가정해보자. 그러면정점 v 에서정점 u 까지의거리는정점 v 에서정점 w 까지의거리 2 와정점 w 에서정점 u 로가는거리 3 을합한값이된다. 그러나경로 2 는경로 1 보다항상길수밖에없다. 왜냐하면현재 distance 값이가장작은정점은 u 이기때문이다. 따라서매단계에서 distance 값이가장작은정점들을추가해나가면시작정점에서모든정점까지의최단거리를구할수있다.

47 Dijkstra 의최단경로알고리즘 새로운정점이 S 에추가되면 distance 값갱신

48 Dijkstra 의최단경로알고리즘 // 입력 : 가중치그래프 G, 가중치는음수가아님. // 출력 : distance 배열, distance[u] 는 v 에서 u 까지의최단거리이다. shortest_path(g, v) S {v for 각정점 w G do distance[w] weight[v][w]; while 모든정점이 S에포함되지않으면 do u 집합 S에속하지않는정점중에서최소 distance 정점 ; S S {u for u에인접하고 S에있는각정점 z do if distance[u]+weight[u][z] < distance[z] then distance[z] distance[u]+weight[u][z];

49 Dijkstra 의최단경로알고리즘

50 Dijkstra 의최단경로알고리즘

51 Dijkstra 의최단경로프로그램 #include <stdio.h> #include <limits.h> #define TRUE 1 #define FALSE 0 #define MAX_VERTICES 7 // 정점의수 #define INF 1000 // 무한대 ( 연결이없는경우 ) int weight[max_vertices][max_vertices]={ // 네트워크의인접행렬 { 0, 7, INF, INF, 3, 10, INF, { 7, 0, 4, 10, 2, 6, INF, { INF, 4, 0, 2, INF, INF, INF, { INF, 10, 2, 0, 11, 9, 4, { 3, 2, INF, 11, 0, INF, 5, { 10, 6, INF, 9, INF, 0, INF, { INF, INF, INF, 4, 5, INF, 0 ; int distance[max_vertices]; // 시작정점으로부터의최단경로거리 int found[max_vertices]; // 방문한정점표시 // int choose(int distance[], int n, int found[]) { int i, min, minpos; min = INT_MAX; minpos = -1; for(i=0;i<n;i++) if( distance[i]< min &&! found[i] ){ min = distance[i]; minpos=i; return minpos;

52 Dijkstra 의최단경로프로그램 (cont.) void shortest_path(int start, int n) { int i, u, w; for(i=0; i<n; i++) // 초기화 {distance[i] = weight[start][i]; found[i] = FALSE; found[start] = TRUE; // 시작정점방문표시 distance[start] = 0; for(i=0; i<n-2; i++){ u = choose(distance, n, found); found[u] = TRUE; for(w=0;w<n; w++) if(!found[w]) if( distance[u]+weight[u][w]<distance[w] ) distance[w] = distance[u]+weight[u][w]; // void main() { shortest_path(0, MAX_VERTICES);

53 Dijkstra 의최단경로알고리즘복잡도 네트워크에 n 개의정점이있다면, Dijkstra 의최단경로알고리즘은주반복문을 n 번반복하고내부반복문을 2n 번반복하므로 O(n 2 ) 의복잡도를가진다.

54 Floyd 의최단경로알고리즘 모든정점사이의최단경로를찾음 2차원배열 A를이용하여 3중반복을하는루프로구성 인접행렬 weight 구성 i==j이면, weight[i][j]=0 두개의정점 i,j 사이에간선이존재하지않으면, weight[i][j]= 정점 i,j 사이에간선이존재하면, weight[i][j] 는간선 (i, j) 의가중치 배열 A의초기값은인접행렬 weight임 floyd(g) for k 0 to n - 1 for i 0 to n - 1 for j 0 to n - 1 A[i][j] = min(a[i][j], A[i][k] + A[k][j])

55 Floyd 의최단경로알고리즘 A k [i][j] 0 부터 k 까지의정점만을이용한정점 i 에서 j 까지의최단경로길이 A -1 A 0 A 1 A n-1 순으로최단경로구해감 A k-1 까지구해진상태에서 k 번째정점이추가로고려되는상황을생각하자 0 부터 k 까지의정점만을사용하여정점 i 에서정점 j 로가는최단경로는다음의 2 가지의경우로나뉘어진다. 정점 k 를거치지않는경우 : A k [i][j] 는 k 보다큰정점은통과하지않으므로최단거리는여전히 A k-1 [i][j]] 임 정점 k 를거치는경우 : i 에서 k 까지의최단거리 A k-1 [i][k] 에 k 에서 j 까지의최단거리 A k-1 [k][j] 를더한값

56 Floyd 의최단경로프로그램 int A[MAX_VERTICES][MAX_VERTICES]; void floyd(int n) { int i, j, k; for(i=0; i<n; i++) for(j=0; j<n; j++) A[i][j]=weight[i][j]; for(k=0; k<n; k++) for(i=0; i<n; i++) for(j=0; j<n; j++) if (A[i][k]+A[k][j] < A[i][j]) A[i][j] = A[i][k]+A[k][j];

57 Floyd 의최단경로알고리즘복잡도 네트워크에 n 개의정점이있다면, Floyd 의최단경로알고리즘은 3 중반복문을실행되므로시간복잡도는 O(n 3 ) 이된다 모든정점쌍의최단경로를구하려면 Dijkstra 의알고리즘 O(n 2 ) 을 n 번반복해도되며, 이경우전체복잡도는 O(n 3 ) 이된다 모든정점쌍의최단경로를구하는데있어두알고리즘모두동일한 O(n 3 ) 의복잡도를가지지만 Floyd 의알고리즘은매우간결한반복구문을사용하므로 Dijkstra 의알고리즘보다효율적이다

58 위상정렬 (topological sort) 방향그래프에서간선 <u, v> 가있다면정점 u 는정점 v 를선행함 방향그래프정점들의선행순서를위배하지않으면서모든정점을나열 선수과목은과목들의선행관계표현함 과목번호 과목명 선수과목 0 전산학개론 없음 1 이산수학 없음 2 자료구조 1 3 알고리즘분석 0, 1, 2 4 운영체제 1 5 인공지능 2, 3, 4 위상순서 (topological order) (0,1,2,3,4,5), (1,0,2,3,4,5) (2,0,1,3,4,5) 는위상순서가아님 왜냐하면 2 번정점이 0 번정점앞에오기때문

59 위상정렬알고리즘 Input: 그래프 G=(V,E) Output: 위상정렬순서 topo_sort(g) for i 0 to do if( 모든정점이선행정점을가지면 ) then 사이클이존재하고위상정렬불가 ; 선행정점을가지지않는정점 v 선택 ; v 를출력 ; v 와 v 에서나온모든간선들을그래프에서삭제 ;

60 위상정렬의예

61 위상정렬프로그램 void topo_sort(graphtype *g) { int i; StackType s; GraphNode *node; // 모든정점의진입차수를계산 int *in_degree = (int *)malloc(g->n* sizeof(int)); for(i = 0; i < g->n; i++) // 초기화 in_degree[i] = 0; for(i = 0; i < g->n; i++){ GraphNode *node = g->adj_list[i]; while ( node!= NULL ) { In_degree[node->vertex]++; node = node->link; // 정점 i 에서나오는간선들

62 위상정렬프로그램 (cont.) // 진입차수가 0인정점을스택에삽입 init(&s); for(i = 0; i < g->n; i++){ if( in_degree[i] == 0 ) push(&s, i); // 위상순서를생성 while(!is_empty(&s)){ int w; w = pop(&s); printf("%d", w); node = g->adj_list[w]; while (node!= NULL) { int u = node->vertex; in_degree[u]--; if(in_degree[u] == 0) push(&s, u); node = node->link; free(in_degree); return; // 반환값이 1 이면성공, 0 이면실패 // 각정점의진입차수를변경 // 진입차수를감소 // 다음정점

슬라이드 1

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

More information

슬라이드 1

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

More information

슬라이드 1

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

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

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

11장.그래프

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

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

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

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

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

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

More information

5장 스택

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

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

제 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

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

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

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

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

chap 5: Trees

chap 5: Trees 5. Threaded Binary Tree 기본개념 n 개의노드를갖는이진트리에는 2n 개의링크가존재 2n 개의링크중에 n + 1 개의링크값은 null Null 링크를다른노드에대한포인터로대체 Threads Thread 의이용 ptr left_child = NULL 일경우, ptr left_child 를 ptr 의 inorder predecessor 를가리키도록변경

More information

슬라이드 1

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

More information

슬라이드 1

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

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

More information

슬라이드 1

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

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

슬라이드 1

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

More information

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

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

More information

슬라이드 1

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

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

7장

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

More information

06장.리스트

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

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

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

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

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

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

More information

슬라이드 1

슬라이드 1 CHAP 8: 우선순위큐 우선순위큐 우선순위큐 (priority queue): 우선순위를가진항목들을저장하는큐 FIFO 순서가아니라우선순위가높은데이터가먼저나가게된다. 가장일반적인큐 : 스택이나 FIFO 큐를우선순위큐로구현할수있다. 자료구조스택큐우선순위큐 삭제되는요소가장최근에들어온데이터가장먼저들어온데이터가장우선순위가높은데이터 응용분야 : 시뮬레이션시스템 ( 여기서의우선순위는대개사건의시각이다.)

More information

11장 포인터

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

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

슬라이드 1

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

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

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

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

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

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

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

슬라이드 1

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

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

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

슬라이드 1

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

More information

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

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

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

More information

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

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

More information

Microsoft PowerPoint Greedy Method.ppt

Microsoft PowerPoint Greedy Method.ppt 알고리즘 (Algorithm) ( 탐욕적방법 ) 문양세 ( 컴퓨터과학전공, IT 특성화대학, 강원대학교 ) 강의순서 탐욕적알고리즘개요최소비용신장트리 (Minimum Spanning Tree) Dijkstra s Algorithm for the Short Path Problem 배낭채우기문제 (The Knapsack Problem) Page 2 1 탐욕적알고리즘개요

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 - slide05.pptx

Microsoft PowerPoint - slide05.pptx Im4u 봄방학캠프 DAY 5; Elementary Graph Theory 구종만 jongman@gmail.com 그래프 (Graphs) 가장중요한 (?) 자료형인그래프의소개 그래프문제의큰두가지벽 모델링 : 현실세계의개념을그래프로나타낸다 알고리즘: 그래프로나타낸문제를해결한다 대개의문제에서는한가지벽만있다 모델링 : 문제를풀면서공부 알고리즘 : 비교적배우기쉽다

More information

슬라이드 1

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

More information

슬라이드 1

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

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

chap x: G입력

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

More information

슬라이드 1

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

More information

Microsoft PowerPoint - 제3장-배열.pptx

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

More information

Infinity(∞) Strategy

Infinity(∞) Strategy 반복제어 표월성 passwd74@cherub.sungkyul.edu 개요 for() 문 break문과 continue문 while문 do-while문 for() 문 for() 문형식 for( 표현식1; 표현식2; 표현식3) 여러문장들 ; 표현식 1 : 초기화 (1 번만수행 ) 표현식 2 : 반복문수행조건 ( 없으면무한반복 ) 표현식 3 : 반복문수행횟수 for()

More information

슬라이드 1

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

More information

완벽한개념정립 _ 행렬의참, 거짓 수학전문가 NAMU 선생 1. 행렬의참, 거짓개념정리 1. 교환법칙과관련한내용, 는항상성립하지만 는항상성립하지는않는다. < 참인명제 > (1),, (2) ( ) 인경우에는 가성립한다.,,, (3) 다음과같은관계식을만족하는두행렬 A,B에

완벽한개념정립 _ 행렬의참, 거짓 수학전문가 NAMU 선생 1. 행렬의참, 거짓개념정리 1. 교환법칙과관련한내용, 는항상성립하지만 는항상성립하지는않는다. < 참인명제 > (1),, (2) ( ) 인경우에는 가성립한다.,,, (3) 다음과같은관계식을만족하는두행렬 A,B에 1. 행렬의참, 거짓개념정리 1. 교환법칙과관련한내용, 는항상성립하지만 는항상성립하지는않는다. < 참인명제 > (1),, (2) ( ) 인경우에는 가성립한다.,,, (3) 다음과같은관계식을만족하는두행렬 A,B에대하여 AB=BA 1 가성립한다 2 3 (4) 이면 1 곱셈공식및변형공식성립 ± ± ( 복호동순 ), 2 지수법칙성립 (은자연수 ) < 거짓인명제 >

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

슬라이드 1

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

More information

학습목차 2.1 다차원배열이란 차원배열의주소와값의참조

학습목차 2.1 다차원배열이란 차원배열의주소와값의참조 - Part2- 제 2 장다차원배열이란무엇인가 학습목차 2.1 다차원배열이란 2. 2 2 차원배열의주소와값의참조 2.1 다차원배열이란 2.1 다차원배열이란 (1/14) 다차원배열 : 2 차원이상의배열을의미 1 차원배열과다차원배열의비교 1 차원배열 int array [12] 행 2 차원배열 int array [4][3] 행 열 3 차원배열 int array [2][2][3]

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

<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

PowerPoint 프레젠테이션

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

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 Chapter 06 반복문 01 반복문의필요성 02 for문 03 while문 04 do~while문 05 기타제어문 반복문의의미와필요성을이해한다. 대표적인반복문인 for 문, while 문, do~while 문의작성법을 알아본다. 1.1 반복문의필요성 반복문 동일한내용을반복하거나일정한규칙으로반복하는일을수행할때사용 프로그램을좀더간결하고실제적으로작성할수있음.

More information

<4D F736F F F696E74202D20C0DAB7E1B1B8C1B65FC3E2BCAEBCF6BEF7>

<4D F736F F F696E74202D20C0DAB7E1B1B8C1B65FC3E2BCAEBCF6BEF7> 한국방송통신대학교컴퓨터과학과 2 학년자료구조 제 1 장기본개념 자료와정보 3 알고리즘 4 자료 data : 현실세계에서관찰이나측정을통해수집된값 value 이나사실 fact 특정한일을수행하는명령어들의유한집합 정보 information : 자료를처리 / 추출 process 해서얻어진유용한결과 입 출 력 : 외부에서제공되는자료가있을수있다력 : 적어도한가지결과를생성한다

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

Microsoft PowerPoint Branch-and-Bound.ppt

Microsoft PowerPoint Branch-and-Bound.ppt 알고리즘 (Algorithm) ( 분기한정 ) 문양세 ( 컴퓨터과학전공, IT 특성화대학, 강원대학교 ) 강의순서 개념 0-1 Knapsack Problem Depth-First Search (Backtracking) Breadth-First Search Best-First Search Traveling Salesman Problem Dynamic Programming

More information

Algorithms

Algorithms 자료구조 & 알고리즘 정렬과탐색알고리즘 Seo, Doo-okok clickseo@gmail.com http://www.clickseo.com 목 차 기초적인정렬알고리즘 고급정렬알고리즘 탐색알고리즘 2 정 렬 (Sort) 정렬 (sort) 의개념 순서없이배열되어있는자료들을재배열하는것 정렬의대상 : 레코드 정렬의기준 : 정렬키 (sort key) 필드 정렬방법의분류

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

중간고사 (자료 구조)

중간고사 (자료 구조) 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 - chap11-포인터의활용.pptx

Microsoft PowerPoint - chap11-포인터의활용.pptx #include int main(void) int num; printf( Please enter an integer: "); scanf("%d", &num); if ( num < 0 ) printf("is negative.\n"); printf("num = %d\n", num); return 0; 1 학습목표 포인터를 사용하는 다양한 방법에

More information

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

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

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 순환알고리즘 C 로쉽게풀어쓴자료구조 순환 (recursion) 수행이끝나기전에자기자신을다시호출하여문제해결 - 직접순환, 간접순환 문제정의가순환적으로되어있는경우에적합한방법 ( 예제 ) 팩토리얼 피보나치수열 n! 1 n * ( n 1)! n n 0 fib( n) 1 fib ( n 2) fib( n 1) 1 ` 2 if if n 0 n 1 otherwise 이항계수

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

슬라이드 1

슬라이드 1 CHAP 9: 정렬 정렬이란? 정렬은물건을크기순으로오름차순이나내림차순으로나열하는것 정렬은컴퓨터공학분야에서가장기본적이고중요한알고리즘중의하나 정렬은자료탐색에있어서필수 ( 예 ) 만약사전에서단어들이정렬이안되어있다면? 정렬의단위 레코드 정렬의대상 학생들의레코드 이름학번주소연락처 레코드 필드필드필드필드 키 (key) 정렬알고리즘의개요 많은정렬알고리즘존재 단순하지만비효율적인방법

More information

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

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

More information

Microsoft PowerPoint - chap-11.pptx

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

More information

02장.배열과 클래스

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

More information

중간고사

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

More information

Microsoft PowerPoint - ch07 - 포인터 pm0415

Microsoft PowerPoint - ch07 - 포인터 pm0415 2015-1 프로그래밍언어 7. 포인터 (Pointer), 동적메모리할당 2015 년 4 월 4 일 교수김영탁 영남대학교공과대학정보통신공학과 (Tel : +82-53-810-2497; Fax : +82-53-810-4742 http://antl.yu.ac.kr/; E-mail : ytkim@yu.ac.kr) Outline 포인터 (pointer) 란? 간접참조연산자

More information

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

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

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

08장.트리

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

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

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

슬라이드 1

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

More information

Microsoft PowerPoint - 제11장 포인터

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

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

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

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

목차 포인터의개요 배열과포인터 포인터의구조 실무응용예제 C 2

목차 포인터의개요 배열과포인터 포인터의구조 실무응용예제 C 2 제 8 장. 포인터 목차 포인터의개요 배열과포인터 포인터의구조 실무응용예제 C 2 포인터의개요 포인터란? 주소를변수로다루기위한주소변수 메모리의기억공간을변수로써사용하는것 포인터변수란데이터변수가저장되는주소의값을 변수로취급하기위한변수 C 3 포인터의개요 포인터변수및초기화 * 변수데이터의데이터형과같은데이터형을포인터 변수의데이터형으로선언 일반변수와포인터변수를구별하기위해

More information