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

Size: px
Start display at page:

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

Transcription

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

2 그래프 (graph) 그래프 연결되어있는객체간의관계를표현하는자료구조 예 : 전기회로, 프로젝트관리, 지도에서도시들의연결 다양한모델에적용할수있는유연성있는자료구조 연결되어있는객체간의관계를표현하는자료구조 꼭지점 (vertex) 와변 (edge) 으로구성 물리적인모델링이나추상적인모델모두에쉽게적용. kkman@sangji.ac.kr -2-

3 그래프역사 오일러문제 1800 년대오일러에의하여창안 모든다리를한번만건너서처음출발했던장소로돌아오는문제 문제의핵심만을표현 위치 : 정점 (node) 다리 : 간선 (edge) 오일러경로 정점에연결된간선의개수가짝수이면존재 kkman@sangji.ac.kr -3-

4

5 그래프용어 그래프는 (V, E) 로표시 V 는정점 (vertices) 들의집합 E 는간선 (edge) 들의집합 정점과간선은모두관련되는데이터를저장 ( 예 ) 예제그래프 정점은각도시를의미 간선은도시를연결하는도로를의미 간선에는도로의길이등의데이터가저장될수있음 kkman@sangji.ac.kr -5-

6 인접 (adjacency) 두꼭지점이하나의변으로연결되어있는경우 A 와 B, B 와 C, B 와 E, D 와 E 는인접. 경로 (path) 두꼭지점을연결하는변들의연결 경로에서는꼭지점과변이교대로나타나지만연결된꼭지점의나열로표기. A 와 D 사이의경로는 ABED kkman@sangji.ac.kr -6-

7 그래프의종류 무방향그래프 (undirected graph) 연결된그래프 (connected graph) 무방향간선 간선을통해서양방향으로갈수있음을표현 (A, B) 와같이정점의쌍으로표현 (A, B) = (B, A) A B kkman@sangji.ac.kr -7-

8 그래프 (directed graph) 로구분 방향간선 방향성이존재하는간선으로도로의일방통행길과마찬가지로한쪽방향으로만갈수있음을표시 A, B> 로표시, <A, B> <B, A> A B kkman@sangji.ac.kr -8-

9 가중치그래프 (weighted graph) 간선에비용이나가중치가할당된그래프 A 1200 B kkman@sangji.ac.kr -9-

10 그래프표현의예 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>} -10-

11 그래프용어 인접정점 (adjacent vertex) 간선에의해연결된정점 정점 0 와정점 1 차수 (degree) 정점에연결된다른정점의개수 정점 0 의차수는 3 경로 (path) 정점의나열로표현 단순경로 : 0, 1, 2, 3 사이클 (cycle): 0, 1, 2, 0 kkman@sangji.ac.kr -11-

12 경로의길이 경로를구성하는데사용된간선의수 완전그래프 모든정점이연결되어있는그래프 -12-

13 그래프 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 를제거 kkman@sangji.ac.kr -13-

14 그래프표현방법 그래프표현방법 인접행렬 (adjacent matrix) 2 차원배열사용표현 인접리스트 (adjacency list) 연결리스트를사용표현 kkman@sangji.ac.kr -14-

15 인접행렬 간선 (i, j) 가그래프에존재, M[i][j] = 1 간선 (i, j) 가그래프에존재하지않음, M[i][j] = 0. kkman@sangji.ac.kr -15-

16 인접리스트 각정점에인접한정점들을연결리스트로표현 각꼭지점은자신의연결리스트를하나씩유지 자신의연결리스트에자신이연결된꼭지점을항목으로추가 -16-

17 -17-

18 그래프탐색 탐색 전체그래프를검색하기위하여한꼭지점에서시작하여주변꼭지점들을순서에맞추어방문하는과정 하나의정점으로부터시작하여차례대로모든정점들을한번씩방문 종류 깊이우선탐색 (Depth First Search; DFS) 너비우선탐색 (Breadth First Search; BFS) -18-

19 깊이우선탐색 (DFS) 특징 미로를탐색할때한방향으로갈수있을때까지계속가다가더이상갈수없게되면다시가장가까운갈림길로돌아와서이곳으로부터다른방향으로다시탐색을진행하는방법과유사 시작꼭지점에서멀어지는방향으로탐색. 스택을이용하여구현 -19-

20 단계 1 스택에서꼭지점 pop. 스택에아무것도없으면탐색을종료 단계 2 꺼내온꼭지점으로이동하고방문표시 단계 3 현재꼭지점에연결된다른꼭지점들을찾아서해당꼭지점에방문한적이없으면스택에 push 단계 4 현재의꼭지점에연결되어있고방문하지않은꼭지점들을모두스택에넣고나면단계 1로돌아간다. kkman@sangji.ac.kr -20-

21 스텝 스택 탐색한꼭지점 1 A 2 B, F, G A 3 B, F, H A, G 4 B, F A, G, H 5 B A, G, H, F 6 C, D A, G, H, F, B 7 C, E A, G, H, F, B, D 8 C A, G, H, F, B, D, E 9 A, G, H, F, B, D, E, C kkman@sangji.ac.kr -21-

22 -22-

23 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 새로시작 } kkman@sangji.ac.kr -23-

24 너비우선탐색 (BFS) 특징 시작꼭지점에서먼순서대로탐색진행 시작정점으로부터가까운정점을먼저방문하고멀리떨어져있는정점을나중에방문하는순회방법 시작꼭지점에서같은거리에있는꼭지점들부터선택 큐를이용하여구현 -24-

25 단계 1 큐에서꼭지점을하나꺼내온다. 큐에아무것도없으면탐색을종료 단계 2 꺼내온꼭지점으로이동하고방문표시 단계 3 현재꼭지점에연결된다른꼭지점들을찾아서해당꼭지점에방문한적이없으면 ( 방문표시가없으면 ) 큐에집어넣는다. 단계 4 현재의꼭지점에연결되어있고방문하지않은꼭지점들을모두스택에넣고나면단계 1 로돌아간다. kkman@sangji.ac.kr -25-

26 1 A 스텝큐탐색한꼭지점 1 A 5 2 C B D 3 6 F G 4 7 H 2 B, F, G A 3 F, G, C, D A, B 4 G, C, D A, B, F 5 C, D, H A, B, F, G 6 D, H A, B, F, G, C 7 H, E A, B, F, G, C, D 8 E 8 E A, B, F, G, C, D,H 9 A, B, F, G, C, D,H, E kkman@sangji.ac.kr -26-

27 -27-

28 BFS 알고리즘 void bfs_mat(graphtype *g, int v) { int w; QueueType q; init(&q); // 큐초기화 visited[v] = TRUE; // 정점 v 방문표시 printf("%d ", v); enqueue(&q, v); // 시작정점을큐에저장 while(!is_empty(&q)){ 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); // 방문한정점을큐에저장 } } } kkman@sangji.ac.kr -28-

29 연결성분 연결성분 (connected component) 최대로연결된부분그래프들을찾는것 그래프탐색으로찾을수있다. visited[i]=count; -29-

30 위상정렬 위상정렬 (topological sorting) 그래프를이용한정렬방법 방향그래프에서꼭지점을연결하는변들의방향이용 방향그래프 그래프의변이방향을가지고있어서, 방향에따라두꼭지점의연결여부가결정 인접행렬과인접리스트가모두사용 -30-

31 방향그래프 방향그래프에서의인접행렬과인접리스트 C B A C B A C B A C B A A B C A B C E D E D C B A E D C B A C E A E

32 방향그래프순환과연결 방향그래프의순환 방향그래프에서도연결된꼭지점에따라경로설정 순환 (cycle) 경로의시작과끝이연결된그래프 Directed Acyclic Graph, DAG 순환을가지지않는방향그래프 위상정렬수행 A E B D C kkman@sangji.ac.kr -32-

33 방향그래프의연결 한꼭지점에서연결될수있는꼭지점의집합 이렇게찾은꼭지점의집합의역은성립되지않음 Warshall 알고리즘이용. -33-

34 위상정렬 방향그래프에의해정해진순서를따라정렬하는방법 DAG 를기반 선수과목체계 조건을만족하는여러가지결과가가능 방향그래프에서간선 <u, v> 정점 u 는정점 v 를선행 방향그래프에존재하는각정점들의선행순서를위배하지않으면서모든정점을나열하는것 kkman@sangji.ac.kr -34-

35 정렬결과 1: 컴퓨터공학기초 -> 프로그래밍기초 -> C 프로그래밍 -> 객체지향기초 -> Java 프로그래밍 -> Python 프로그래밍 -> Perl 프로그래밍 정렬결과 2: 프로그래밍기초 -> 컴퓨터공학기초 -> 객체지향기초 -> C 프로그래밍 -> Java 프로그래밍 -> Perl 프로그래밍 -> Python 프로그래밍

36 위상정렬수행단계 단계 1. 자신을가리키는변이없는꼭지점을찾는다. 단계 2. 찾은꼭지점을출력하고찾은꼭지점과그꼭지점에서출발하는변들을그래프에서지운다. 단계 3. 아직그래프에꼭지점이남아있으면단계 1 로돌아가고, 남아있지않으면위상정렬을종료. kkman@sangji.ac.kr -36-

37 과목번호 과목명 선수과목 0 전산학개론 없음 1 이산수학 없음 2 자료구조 1 3 알고리즘분석 0, 1, 2 4 운영체제 1 5 인공지능 2, 3, 4 n 위상정렬 : (0,1,2,3,4,5), (1,0,2,3,4,5) n (2,0,1,3,4,5) 는위상정렬 n 2 번정점이 0 번정점앞에오기때문이다. 간선 <0, 2> 이존재하기때문에 0 번정점이끝나야만이 2 번정점을시작할수있다. kkman@sangji.ac.kr -37-

38 -38-

39 가중치그래프 가중치그래프 (weighted graph) 그래프의변에가중치를부여한그래프 가중치 (weight) ~ 한꼭지점에서다른꼭지점사이를이동하기위해소요되는비용 인접행렬과인접리스트의방법이모두가능 ~ 인접행렬의방법이좀더단순 kkman@sangji.ac.kr -39-

40 인접행렬을이용한방법 꼭지점간연결이 1 에서설정된가중치로표기 kkman@sangji.ac.kr -40-

41 인접리스트를이용한구현 연결정보와함께가중치정보저장 -41-

42 신장트리 신장트리 (spanning tree) 그래프내의모든정점을포함하는트리 모든정점들이연결 사이클을포함할수없음 그래프내의 n개의정점, n-1개의간선으로연결 신장트리검색 깊이우선탐색, 너비우선탐색에사용된간선의집합 -42-

43 신장트리용도 최소의링크를사용하여네트워크를구축하고싶은경우 도로건설 - 도시들을모두연결하면서도로의길이가최소가되도록하는문제 전기회로 - 단자들을모두연결하면서전선의길이가가장최소가되도록하는문제 통신 - 전화선의길이가최소가되도록전화케이블망을구성하는문제 배관 - 파이프를모두연결하면서파이프의총길이가최소가되도록연결하는문제 kkman@sangji.ac.kr -43-

44 -44-

45 최소신장트리 최소신장트리 (minimum spanning tree) 모든꼭지점을연결할수있도록최소한의변만선택한그래프 그래프의부분집합의개념 한그래프에서여러최소신장트리구성가능 E = V -1 ~ E : 최소신장트리에서필요한변의수 ~ V : 그래프에있는모든꼭지점의수 kkman@sangji.ac.kr -45-

46

47 최소신장트리의구현, DFS 이용 DFS 는그래프의연결된변을따라탐색을수행하기때문에적용 하나의꼭지점에서연결된다른꼭지점을찾는과정을반복적으로수행하며모든꼭지점을방문. ~ 지나온변들이최소신장트리를구성 kkman@sangji.ac.kr -47-

48 MST 알고리즘 2 가지의대표적인알고리즘 Kruskal의알고리즘 Prim의알고리즘 kkman@sangji.ac.kr -48-

49 Kruskal 의알고리즘 탐욕적인방법 (greedy method) 알고리즘설계에서있어서중요한기법중의하나 결정을해야할때마다그순간에가장좋다고생각되는것을해답으로선택함으로써최종적인해답에도달 탐욕적인방법은항상최적의해답을주는지를반드시검증해야한다. Kruskal 의알고리즘은최적의해답을주는것으로증명 -49-

50 특징 최소비용신장트리가최소비용의간선으로구성됨과동시에사이클을포함하지않는다는조건 각단계에서사이클을이루지않는최소비용간선을선택 그래프의간선 가중치의오름차순으로정렬 정렬된간선들의리스트중 사이클을형성하지않는간선을찾아서현재의최소비용신장트리의집합에추가 사이클을형성하면그간선은제외 -50-

51 -51-

52 -52-

53 -53-

54 Kruskal 의 MST 알고리즘의구현 union-find 알고리즘 집합들의합집합을구하고집합의원소가어떤집합에속하는지를계산하는알고리즘 여러가지방법으로구현이가능 Kruskal 의 MST 알고리즘에서사이클검사에사용 -54-

55 a 와 b 가같은집합에속함 a 와 b 가다른집합에속함 kkman@sangji.ac.kr -55-

56 Prim 의 MST 알고리즘 특징 시작정점에서부터출발하여신장트리집합을단계적으로확장해나가는방법 시작단계에서는시작정점만이신장트리집합에포함 앞단계에서만들어진신장트리집합에, 인접한정점들중에서최저간선으로연결된정점을선택하여트리를확장 트리가 n-1 개의간선을가질때까지계속. -56-

57 간선 (a, b) 와간선 (f, e) 의가중치를비교해보면 (f, e) 가 27 로서 (a, b) 의 29 보다높다. 따라서 (f, e) 간선이선택되고정점 e 가신장트리집합에포함된다. kkman@sangji.ac.kr -57-

58 Prim 의 MST 알고리즘 -58-

59 Prim 의 MST 알고리즘 -59-

60 Prim 의 MST 알고리즘 -60-

61 최단경로알고리즘 최단경로 (shortest path) 문제 네트워크에서정점 i 와정점 j 를연결하는경로중에서간선들의가중치합이최소가되는경로를찾는문제 간선의가중치는비용, 거리, 시간등 그래프를적용하는가장보편적인경우 가중치와방향을모두가지는그래프를기준으로하여최단경로탐색과정수행 kkman@sangji.ac.kr -61-

62 -62-

63 Dijkstra 의최단경로알고리즘 Dijkstra 알고리즘 꼭지점에서시작해서주변꼭지점으로퍼져가며최단경로탐색 단계 단계 1: 현재선택된꼭지점을 고정 으로표시 단계 2: 선택된꼭지점에연결된변들을통하여다른꼭지점들까지연결되는더짧은경로가있는지를확인, 더짧은경로가있다면꼭지점의 거리정보 를갱신 단계 3: 각꼭지점까지의거리를확인하여 고정 으로표시되지않은꼭지점중거리가가장짧은꼭지점을선택 -63-

64 ~ 단계 4: 모든꼭지점이 고정 으로표시되었으면최단경로탐색을중지하고아니면단계 1 로돌아간다. ~ ( 고정 : 해당꼭지점에대한최단경로탐색이완료되었기때문에이를확정하고더이상고려하지않음을의미 ) 집합 S: 시작정점 v 로부터의최단경로가이미발견된정점들의집합 distance 배열 최단경로를알려진정점만을통하여각정점까지가는최단경로의길이 매단계에서가장 distance 값이적은정점을 S 에추가. kkman@sangji.ac.kr -64-

65 -65-

66 매단계에서새로운정점이 S 에추가되면 distance 값을갱신 kkman@sangji.ac.kr -66-

67 -67-

68

69 -69-

70 -70-

71 -71-

72 -72-

73 -73-

74 -74-

75 -75-

76 최단경로탐색결과 각꼭지점이자기의전꼭지점으로가리키고있는꼭지점을거꾸로올라가면최단경로 도시대전강릉대구광주부산 경로서울-대전서울-강릉서울-강릉-대구서울-대전-광주서울-강릉-대구-부산 -76-

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

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

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

More information

11장.그래프

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

More information

슬라이드 1

슬라이드 1 CHAP 10 : 그래프 그래프 (graph) 연결되어있는객체간의관계를표현하는자료구조 가장일반적인자료구조형태 우리가배운트리 (tree) 도그래프의특수한경우임 전기회로의소자간연결상태 운영체제의프로세스와자원관계 큰프로젝트에서작은프로젝트간의우선순위 지도에서도시들의연결상태 그래프역사 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

슬라이드 1

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

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

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

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

More information

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

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

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

선형자료구조 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

제 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

완벽한개념정립 _ 행렬의참, 거짓 수학전문가 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

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

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

Microsoft PowerPoint - slide05.pptx

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

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

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

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

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

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

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

Chapter 4. LISTS

Chapter 4. LISTS 6. 동치관계 (Equivalence Relations) 동치관계 reflexive, symmetric, transitive 성질을만족 "equal to"(=) 관계는동치관계임. x = x x = y 이면 y = x x = y 이고 y = z 이면 x = z 동치관계를이용하여집합 S 를 동치클래스 로분할 동일한클래스내의원소 x, y 에대해서는 x y 관계성립

More information

슬라이드 1

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

More information

2002년 2학기 자료구조

2002년 2학기 자료구조 자료구조 (Data Structures) Chapter 1 Basic Concepts Overview : Data (1) Data vs Information (2) Data Linear list( 선형리스트 ) - Sequential list : - Linked list : Nonlinear list( 비선형리스트 ) - Tree : - Graph : (3)

More information

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

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

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

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

06장.리스트

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

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

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

Microsoft PowerPoint - 08-chap06-Queue.ppt

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

More information

PowerPoint Presentation

PowerPoint Presentation 자바프로그래밍 1 배열 손시운 ssw5176@kangwon.ac.kr 배열이필요한이유 예를들어서학생이 10 명이있고성적의평균을계산한다고가정하자. 학생 이 10 명이므로 10 개의변수가필요하다. int s0, s1, s2, s3, s4, s5, s6, s7, s8, s9; 하지만만약학생이 100 명이라면어떻게해야하는가? int s0, s1, s2, s3, s4,

More information

슬라이드 1

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

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 그래프알고리즘 14 장. 그래프알고리즘 위상정렬, 최소신장트리, 최단경로, 이행폐쇄, 이중연결, 유니언파인드, 네트워크플로우 학습목표 그래프관련용어를이해한다. 그래프를표현하기위한두가지자료구조를이해한다. 신장트리, 최소신장트리알고리즘들을이해한다. 이행폐쇄, 최단경로알고리즘들을이해한다. 이중연결, 유니언파인드, 네트워크플로우알고리즘들을이해한다. 1 그래프 유관한사물

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

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

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

중간고사

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

More information

슬라이드 1

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

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

<4D F736F F F696E74202D20C0DAB7E1B1B8C1B65FC3E2BCAEBCF6BEF7>

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

More information

04 Çмú_±â¼ú±â»ç

04 Çмú_±â¼ú±â»ç 42 s p x f p (x) f (x) VOL. 46 NO. 12 2013. 12 43 p j (x) r j n c f max f min v max, j j c j (x) j f (x) v j (x) f (x) v(x) f d (x) f (x) f (x) v(x) v(x) r f 44 r f X(x) Y (x) (x, y) (x, y) f (x, y) VOL.

More information

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

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

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 그래프알고리즘 14 장. 그래프알고리즘 위상정렬, 최소신장트리, 최단경로, 이행폐쇄, 이중연결, 유니언파인드, 네트워크플로우 학습목표 그래프관련용어를이해한다. 그래프를표현하기위한두가지자료구조를이해한다. 신장트리, 최소신장트리알고리즘들을이해한다. 이행폐쇄, 최단경로알고리즘들을이해한다. 이중연결, 유니언파인드, 네트워크플로우알고리즘들을이해한다. 1 Section

More information

슬라이드 1

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

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 System Software Experiment 1 Lecture 5 - Array Spring 2019 Hwansoo Han (hhan@skku.edu) Advanced Research on Compilers and Systems, ARCS LAB Sungkyunkwan University http://arcs.skku.edu/ 1 배열 (Array) 동일한타입의데이터가여러개저장되어있는저장장소

More information

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

학습목차 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

리스트 (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

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

1장. 리스트

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

More information

11장 포인터

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

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

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

chap x: G입력

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

More information

7장

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

More information

Microsoft PowerPoint - 알고리즘_5주차_1차시.pptx

Microsoft PowerPoint - 알고리즘_5주차_1차시.pptx Basic Idea of External Sorting run 1 run 2 run 3 run 4 run 5 run 6 750 records 750 records 750 records 750 records 750 records 750 records run 1 run 2 run 3 1500 records 1500 records 1500 records run 1

More information

CH06)자료구조.hwp

CH06)자료구조.hwp 자료구조 (Data Structure) ) 자료구조의정의 프로그램에서사용하기위한자료를저장매체에저장하는방법및각자료간의관계, 처리방법을분석하는이론 자료의표현과연산의기초과학이다. 일련의자료들을조직화, 구조화시킨다. 모든자료구조에대하여연산처리가가능하다. 구현된자료구조에따라프로그램실행시간이다르다. 2) 자료구조의목적 ( 이유 ) 실제적으로물리적인저장장치는일정한규칙으로하나의선형형태로존재하기때문에그특성에맞게적절한형태로

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 ( 관계연산자 ) >> 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

설계란 무엇인가?

설계란 무엇인가? 금오공과대학교 C++ 프로그래밍 jhhwang@kumoh.ac.kr 컴퓨터공학과 황준하 6 강. 함수와배열, 포인터, 참조목차 함수와포인터 주소값의매개변수전달 주소의반환 함수와배열 배열의매개변수전달 함수와참조 참조에의한매개변수전달 참조의반환 프로그래밍연습 1 /15 6 강. 함수와배열, 포인터, 참조함수와포인터 C++ 매개변수전달방법 값에의한전달 : 변수값,

More information

Microsoft PowerPoint - ch00 - Introduction to Programming Language Lecture

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

More information

<4D F736F F F696E74202D2031C1D6C2F72D31C2F7BDC32028B0ADC0C7C0DAB7E D20C7C1B7CEB1D7B7A1B9D6BEF0BEEE20B0FAB8F1BCD2B

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

More information

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

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

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

Microsoft PowerPoint - Java7.pptx

Microsoft PowerPoint - Java7.pptx HPC & OT Lab. 1 HPC & OT Lab. 2 실습 7 주차 Jin-Ho, Jang M.S. Hanyang Univ. HPC&OT Lab. jinhoyo@nate.com HPC & OT Lab. 3 Component Structure 객체 (object) 생성개념을이해한다. 외부클래스에대한접근방법을이해한다. 접근제어자 (public & private)

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

정보

정보 정보 Sangwook Lee Deogi High School III 문제해결과프로그래밍 1 추상화 2 알고리즘 3 프로그래밍 2 알고리즘 2-1 알고리즘설계 2-2 알고리즘분석 3 2-1 알고리즘설계 (p.108) 학습목표 순차, 선택, 반복구조의흐름을설명할수있다. 다양한제어구조를활용하여논리적이고효율적인알고리즘을설계할수있다. 4 [1] 알고리즘제어구조 (p.109)

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

gnu-lee-oop-kor-lec11-1-chap15

gnu-lee-oop-kor-lec11-1-chap15 어서와 Java 는처음이지! 제 15 장컬렉션 컬렉션 (collection) 은자바에서자료구조를구현한클래스 자료구조로는리스트 (list), 스택 (stack), 큐 (queue), 집합 (set), 해쉬테이블 (hash table) 등이있다. 자바는컬렉션인터페이스와컬렉션클래스로나누어서제공한다. 자바에서는컬렉션인터페이스를구현한클래스도함께제공하므로이것을간단하게사용할수도있고아니면각자필요에맞추어인터페이스를자신의클래스로구현할수도있다.

More information

Microsoft PowerPoint - chap06-1Array.ppt

Microsoft PowerPoint - chap06-1Array.ppt 2010-1 학기프로그래밍입문 (1) chapter 06-1 참고자료 배열 박종혁 Tel: 970-6702 Email: jhpark1@snut.ac.kr 한빛미디어 출처 : 뇌를자극하는 C프로그래밍, 한빛미디어 -1- 배열의선언과사용 같은형태의자료형이많이필요할때배열을사용하면효과적이다. 배열의선언 배열의사용 배열과반복문 배열의초기화 유연성있게배열다루기 한빛미디어

More information

<4D F736F F F696E74202D20C1A637C0E52DB0EDB1DEBFACB0E1B8AEBDBAC6AE2E >

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

More information

슬라이드 1

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

More information

Microsoft PowerPoint - 제8장-트리.pptx

Microsoft PowerPoint - 제8장-트리.pptx 제 8 강의. 트리 (Tree) 자료구조 1. 트리의개념 2. 이진트리 3. 이진트리의저장 1 트리자료구조필요성연결리스트의삽입삭제시데이터를이동하지않는장점을살리자. 연결리스트의검색시노드의처음부터찾아가야하는단점을보완하자. 데이터를중간부터찾아가는이진검색의장점을이용하자. 연결리스트의포인터를리스트의중간에두는방법? ptr 10 23 34 42 56 검색을중간부터시작하여좌우중하나로분기,

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

<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

<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

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

Ch.8 Procedures and Environments

Ch.8 Procedures and Environments Chapter 9 정렬 (sorting) SANGJI University Kwangman KO (kkman@sangji.ac.kr) 정렬 (sorting) 이란? 정의 물건을크기순으로오름차순이나내림차순으로나열하는것 컴퓨터공학분야에서가장기본적이고중요한알고리즘중의하나 정렬은자료탐색에있어서필수적. ( 예 ) 만약사전에서단어들이정렬이안되어있다면? 정렬알고리즘의개요

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

슬라이드 1

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

More information

Microsoft PowerPoint - chap06-2pointer.ppt

Microsoft PowerPoint - chap06-2pointer.ppt 2010-1 학기프로그래밍입문 (1) chapter 06-2 참고자료 포인터 박종혁 Tel: 970-6702 Email: jhpark1@snut.ac.kr 한빛미디어 출처 : 뇌를자극하는 C프로그래밍, 한빛미디어 -1- 포인터의정의와사용 변수를선언하는것은메모리에기억공간을할당하는것이며할당된이후에는변수명으로그기억공간을사용한다. 할당된기억공간을사용하는방법에는변수명외에메모리의실제주소값을사용하는것이다.

More information

(291)본문7

(291)본문7 2 Chapter 46 47 Chapter 2. 48 49 Chapter 2. 50 51 Chapter 2. 52 53 54 55 Chapter 2. 56 57 Chapter 2. 58 59 Chapter 2. 60 61 62 63 Chapter 2. 64 65 Chapter 2. 66 67 Chapter 2. 68 69 Chapter 2. 70 71 Chapter

More information

¾Ë·¹¸£±âÁöħ¼�1-ÃÖÁ¾

¾Ë·¹¸£±âÁöħ¼�1-ÃÖÁ¾ Chapter 1 Chapter 1 Chapter 1 Chapter 2 Chapter 2 Chapter 2 Chapter 2 Chapter 2 Chapter 3 Chapter 3 Chapter 3 Chapter 3 Chapter 3 Chapter 3 Chapter 3 Chapter 3 Chapter 4 Chapter 4

More information

01....b74........62

01....b74........62 4 5 CHAPTER 1 CHAPTER 2 CHAPTER 3 6 CHAPTER 4 CHAPTER 5 CHAPTER 6 7 1 CHAPTER 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

More information

PowerPoint Presentation

PowerPoint Presentation 객체지향프로그래밍 클래스, 객체, 메소드 ( 실습 ) 손시운 ssw5176@kangwon.ac.kr 예제 1. 필드만있는클래스 텔레비젼 2 예제 1. 필드만있는클래스 3 예제 2. 여러개의객체생성하기 4 5 예제 3. 메소드가추가된클래스 public class Television { int channel; // 채널번호 int volume; // 볼륨 boolean

More information

PowerPoint Presentation

PowerPoint Presentation Package Class 3 Heeseung Jo 목차 section 1 패키지개요와패키지의사용 section 2 java.lang 패키지의개요 section 3 Object 클래스 section 4 포장 (Wrapper) 클래스 section 5 문자열의개요 section 6 String 클래스 section 7 StringBuffer 클래스 section

More information

PowerPoint Presentation

PowerPoint Presentation Dependency Parser 자연언어처리 Probabilistic CFG (PCFG) - CFG - PCFG with saw with saw astronomers ears saw stars telescope astronomers ears saw stars telescope PCFG example Repeated work Parsing PCFG: CKY CKY

More information

4장. 순차자료구조

4장. 순차자료구조 순차자료구조방식 자바로배우는쉬운자료구조 이장에서다룰내용 1 선형리스트 2 선형리스트의구현 3 다항식의순차자료구조표현 4 행렬의순차자료구조표현 2 선형리스트 (1) 리스트 (List) 자료를나열한목록 ( 집합 ) 리스트의예 3 선형리스트 (2) 선형리스트 (Linear List) 순서리스트 (Ordered List) 자료들간에순서를갖는리스트 선형리스트의예 4

More information

Microsoft PowerPoint - slide06.pptx

Microsoft PowerPoint - slide06.pptx Im4u 봄방학캠프 DAY 6; Elementary Graph Theory (II) 구종만 jongman@gmail.com 오늘할이야기 최단거리 (Shortest Path) 교과서알고리즘 : Dijkstra s, Floyd s, Bellman- Ford s 그래프모델링 (modeling) 문제에서어떻게그래프를뽑아낼것인가? 최단거리의변형 : multiplicative,

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