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

Size: px
Start display at page:

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

Transcription

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

2 장. 그래프알고리즘 수학은패턴의과학이다. 음악역시패턴들이다. 컴퓨터과학은추상화와패턴의형성에깊은관련이있다. 컴퓨터과학이다른분야들에비해특징적인것은지속적으로차원이 급상승한다는점이다. 미시적관점에서 거시적관점으로도약하는것이다. - 도널드크누스 - - 한빛미디어

3 학습목표 그래프의표현법을익힌다. 너비우선탐색과깊이우선탐색의원리를충분히이해하도록한다. 신장트리의의미와최소신장트리를구하는두가지알고리즘을이해한다. 그래프의특성에따라가장적합한최단경로알고리즘을선택할수있도록한다. 위상정렬을이해하고 DAG 의경우에위상정렬을이용해최단경로를구하는방법을이해한다. 강연결요소를구하는알고리즘을이해하고이알고리즘의정당성을확신할수있도록한다. 본문에서소개하는각알고리즘의수행시간을분석할수있도록한다. - - 한빛미디어

4 Graph 현상이나사물을정점 vertex 과간선 edge 으로표현한것 Graph G = (V, E) V: 정점집합 E: 간선집합 두정점이간선으로연결되어있으면인접하다고한다 인접 = adjacent 간선은두정점의관계를나타낸다 - - 한빛미디어

5 그래프의예 철수 영희 준호 승우 동건 재상 사람들간의친분관계를나타낸그래프 - - 한빛미디어

6 영희 철수 준호 승우 동건 재상 친밀도를가중치로나타낸친분관계그래프 - - 한빛미디어

7 철수 유향그래프 directed graph=digraph 영희 준호 승우 동건 재상 방향을고려한친분관계그래프 - - 한빛미디어

8 영희 철수 준호 승우 동건 재상 가중치를가진유향그래프 - - 한빛미디어

9 Graph 의표현 : Adjacency Matrix Adjacency matrix N: 정점의총수 NⅩN 행렬로표현 원소 (i, j) = : 정점 i 와정점 j 사이에간선이있음 원소 (i, j) = 0 : 정점 i 와정점 j 사이에간선이없음 유향그래프의경우 원소 (i, j) 는정점 i 로부터정점 j 로연결되는간선이있는지를나타냄 가중치있는그래프의경우 원소 (i, j) 는 대신에가중치를가짐 - - 한빛미디어

10 철수 0 0 영희 동건 준호 재상 승우 무향그래프의예 한빛미디어

11 영희 동건 철수 준호 재상 승우 가중치있는무향그래프의예 - - 한빛미디어

12 철수 0 0 영희 동건 준호 재상 승우 유향그래프의예 - - 한빛미디어

13 영희 동건 철수 준호 재상 승우 가중치있는유향그래프의예 - - 한빛미디어

14 유향그래프의다른예 - - 한빛미디어

15 가중치있는그래프의다른예 - - 한빛미디어

16 Graph 의표현 : Adjacency List Adjacency list N 개의연결리스트로표현 i 번째리스트는정점 i 에인접한정점들을리스트로연결해 놓음 가중치있는그래프의경우 리스트는가중치도보관한다 - - 한빛미디어

17 철수 영희 준호 승우 동건 재상 무향그래프의예 - - 한빛미디어

18 영희 철수 준호 승우 동건 재상 가중치있는그래프의예 - - 한빛미디어

19 Graph Traversal 대표적두가지방법 BFS (Breadth-First Search) DFS (Depth-First Search) 너무나중요함 그래프알고리즘의기본 DFS/BFS 는간단해보이지만제대로아는사람은매우드물다 DFS/BFS 는뼛속깊이이해해야좋은그래프알고리즘을만들수있음 - - 한빛미디어

20 DFS(G) { DFS 깊이우선탐색 for each v V visited[v] NO; for each v V if (visited[v] = NO) then adfs(v); } adfs (v) { visited[v] YES; for each x L(v) } L(v) : 정점 v의인접리스트 if (visited[x] = NO) then adfs(u); ü 수행시간 : Θ( V + E ) 한빛미디어

21 BFS 너비우선탐색 BFS(G, v) { for each v V visited[v] NO; visited[s] YES; enqueue(q, s); while (Q Ф) { u dequeue(q); for each v L(u) if (visited[v] = NO) then visited[u] YES; enqueue(q, v); } } } ü 수행시간 : Θ( V + E ) - - 한빛미디어

22 동일한 Tree 를각각 DFS/BFS 로방문하기 DFS BFS - - 한빛미디어

23 BFS 의작동예 (a) (b) (c) (e) (d) - - 한빛미디어

24 DFS 의작동예 (a) (b) (c) (e) (d) - - 한빛미디어

25 DFS 의작동예 ( 계속 ) (f) (g) (i) (h) - - 한빛미디어

26 Minimum Spanning Trees 조건 무향연결그래프 연결그래프 connected graph : 모든정점간에경로가존재하는그래프 트리 싸이클이없는연결그래프 n 개의정점을가진트리는항상 n- 개의간선을갖는다 그래프 G 의신장트리 G 의정점들과간선들로만구성된트리 G 의최소신장트리 G 의신장트리들중간선의합이최소인신장트리 - - 한빛미디어

27 Prim Algorithm Prim (G, r) { S Ф ; 정점 r 을방문되었다고표시하고, 집합 S 에포함시킨다 ; while (S V) { S 에서 V-S 를연결하는간선들중최소길이의간선 (x,y) 를찾는다 ; (x S, y V-S) 정점 y 를방문되었다고표시하고, 집합 S 에포함시킨다 ; } } ü Prim 알고리즘은그리디 greedy 알고리즘의일종 ü 그리디알고리즘으로최적해를보장하는드문예 ü 수행시간 : O( E log V ) 힙이용 - - 한빛미디어

28 Prim Algorithm 의작동예 S (a) S 0 0 r 0 0 (d) 0 (b) 0 0 S 0 (c) 0 : 방금 S 에포함된정점 : 방금이완이일어난정점 - - 한빛미디어

29 (e) (f) S 0 S 0 (g) 0 0 (i) (h) S S - - 한빛미디어

30 Kruskal Algorithm Kruskal (G, r) { T Ф ; T : 신장트리단하나의정점만으로이루어진 n 개의집합을초기화한다 ; 모든간선을가중치가작은순으로정렬한다 ; while (T의간선수 < n-) { 최소비용간선 (u, v) 를제거한다 ; 정점 u와정점 v가서로다른집합에속하면 { 두집합을하나로합친다 ; T T {u, v)}; } } } ü 수행시간 : O( E log V ) 한빛미디어

31 Kruskal Algorithm 의작동예 (a) 0 (b) 0 (e) 0 (d) 0 (c) 0 : 방금고려한간선 : 성공적으로더해진간선 - - 한빛미디어

32 (f) 0 (g) 0 (i) (h) - - 한빛미디어

33 Topological Sorting 조건 싸이클이없는유향그래프 Topological Sorting 위상정렬 모든정점을일렬로나열하되 정점 x 에서정점 y 로가는간선이있으면 x 는반드시 y 보다앞에위치한다 일반적으로임의의유향그래프에대해복수의위상순서가존재한다 - - 한빛미디어

34 이그래프에대한위상정렬의예 개 - - 한빛미디어

35 위상정렬알고리즘 topologicalsort(g) { for to n { 진입간선이없는정점 u 를선택한다 ; A[i] u; 정점 u 와, u 의진출간선을모두제거한다 ; } 이시점에배열 A[ n] 에는정점들을위상정렬되어있다 } ü 수행시간 : Θ( V + E ) - - 한빛미디어

36 위상정렬알고리즘 의작동예 점화 점화 남비에물붓기 라면넣기 계란풀어넣기 남비에물붓기 라면넣기 계란풀어넣기 라면봉지뜯기 수프넣기 (a) 라면봉지뜯기 수프넣기 (b) 점화 점화 남비에물붓기 라면넣기 계란풀어넣기 남비에물붓기 라면넣기 계란풀어넣기 라면봉지뜯기 수프넣기 (d) 라면봉지수프넣기뜯기 (c) - - 한빛미디어

37 점화 점화 남비에물붓기 라면넣기 계란풀어넣기 남비에물붓기 라면넣기 계란풀어넣기 라면봉지뜯기 수프넣기 (e) 라면봉지뜯기 수프넣기 (f) 점화 남비에물붓기 라면넣기 계란풀어넣기 라면봉지뜯기 수프넣기 (g) - - 한빛미디어

38 위상정렬알고리즘 topologicalsort(g) { for each v V visited[v] NO; for each v V 정점의순서는아무순서나무관 if (visited[v] = NO) then DFS-TS(v) ; } DFS-TS(v) { visited[v] YES; } for each x L(v) L(v): v 의인접리스트 if (visited[x] = NO) then DFS-TS(x) ; 연결리스트 R 의맨앞에정점 v 를삽입한다 ; ü 수행시간 : Θ( V + E ) ü알고리즘이끝나고나면연결리스트 R에는정점들이위상정렬된순서로매달려있다. - - 한빛미디어

39 위상정렬알고리즘 의작동예 점화 점화 냄비에물붓기 라면넣기 계란풀어넣기 냄비에물붓기 라면넣기 계란풀어넣기 라면봉지뜯기 수프넣기 (a) 라면봉지뜯기 수프넣기 (b) 점화 점화 냄비에물붓기 라면넣기 계란풀어넣기 냄비에물붓기 라면넣기 계란풀어넣기 라면봉지뜯기 수프넣기 (d) 라면봉지뜯기 수프넣기 (c) - - 한빛미디어

40 - 0 - 한빛미디어 냄비에물붓기점화라면넣기라면봉지뜯기계란풀어넣기수프넣기냄비에물붓기점화라면넣기라면봉지뜯기계란풀어넣기수프넣기냄비에물붓기점화라면넣기라면봉지뜯기계란풀어넣기수프넣기 (e) (f) (g) 냄비에물붓기점화라면넣기라면봉지뜯기계란풀어넣기수프넣기 (h)

41 점화 점화 냄비에물붓기 라면넣기 계란풀어넣기 냄비에물붓기 라면넣기 계란풀어넣기 라면봉지뜯기 수프넣기 (i) 라면봉지뜯기 수프넣기 (j) - - 한빛미디어

42 Shortest Paths 조건 간선가중치가있는유향그래프 무향그래프는각간선에대해양쪽으로유향간선이있는유향그래프로생각할수있다 즉, 무향간선 (u,v) 는유향간선 (u,v) 와 (v,u) 를의미한다고가정하면된다 두정점사이의최단경로 두정점사이의경로들중간선의가중치합이최소인경로 간선가중치의합이음인싸이클이있으면문제가정의되지않는다 - - 한빛미디어

43 단일시작점최단경로 단일시작점으로부터각정점에이르는최단경로를구한다 Ø 다익스트라알고리즘 음의가중치를허용하지않는최단경로 Ø 벨만 - 포드알고리즘 음의가중치를허용하는최단경로 Ø 싸이클이없는그래프의최단경로 모든쌍최단경로 모든정점쌍사이의최단경로를모두구한다 Ø 플로이드 - 워샬알고리즘 - - 한빛미디어

44 Dijkstra Algorithm Dijkstra(G, r) G=(V, E): 주어진그래프 r: 시작으로삼을정점 { S Ф ; S : 정점집합 for each u V d u ; d r 0 ; while (S V){ n회순환된다 u extractmin(v-s, d) ; S S {u}; for each v L(u) L(u) : u로부터연결된정점들의집합 if (v V-S and d v <d u +w u,v ) then d v d u +w u,v ; } } extractmin(q, d) { 집합 Q에서 d값이가장작은정점 u를리턴한다 ; } 모든간선의가중치는음이아니어야함 이완 (relaxation) ü 수행시간 : O( E log V ) 힙이용 - - 한빛미디어

45 Dijkstra Algorithm 의작동예 한빛미디어

46 한빛미디어 0 0

47 Bellman-Ford Algorithm 음의가중치를허용한다 BellmanFord(G, r) { for each u V d u ; d r 0; for i to V - for each (u, v) E if (d u + w u,v < d v ) then d v d u + w u,v ; } 이완 (relaxation) ü 수행시간 : Θ( E V ) - - 한빛미디어

48 Bellman-Ford Algorithm 의작동예 (a) 0 (b) i = (e) i = 0 (d) i = (c) i = 한빛미디어

49 (f) i = - 0 (g) i = (i) (h) i = 한빛미디어

50 DP 로본 Bellman-Ford 알고리즘 d tk : 중간에최대 k 개의간선을거쳐정점 r로부터정점 t에이르는최단거리 목표 : d n- t ü 재귀적관계 d vk = min {d u k- + w u, v }, k > 0 for 모든간선 (u, v) d 0 r = 0 d 0 t =, t r 한빛미디어

51 Floyd-Warshall Algorithm 모든정점들간의상호최단거리구하기 응용예 Road Atlas 네비게이션시스템 네트웍커뮤니케이션 - - 한빛미디어

52 Floyd-Warshall Algorithm FloydWarshall(G) { for i to n for j to n d 0 ij w ij ; for k to n 중간정점집합 {,,, k} for i to n i : 시작정점 for j to n j : 마지막정점 d k ij min {d k- ij, d k- ik + d k- kj}; } ü d k ij : 중간정점으로정점집합 {,,, k} 만을사용하여정점 i 에서정점 j 에이르는최단경로 ü 수행시간 : Θ( V ) - - 한빛미디어

53 d k ij 관련 k i j 중간정점들이모두 {,,, k} 에속함 - - 한빛미디어

54 싸이클이없는 Graph 의 Shortest Path 싸이클이없는유향그래프를 DAG 라한다 DAG: Directed Acyclic Graph DAG 에서의최단경로는선형시간에간단히구할수있다 - - 한빛미디어

55 DAG-ShortestPath(G, r) { for each u V d u ; d r 0; G 의정점들을위상정렬한다 ; for each u V ( 위상정렬순서로 ) for each v L(u) L(u) : 정점 u 로부터연결된정점들의집합 if (d u + w u,v < d v ) then d v d u + w u,v ; } ü 수행시간 : Θ( V + E ) - - 한빛미디어

56 DAG-ShortestPath 의작동예 (a) - - (b) - - (c) r 한빛미디어

57 (d) (e) (f) 한빛미디어

58 (g) (h) (i) 한빛미디어

59 Strongly Connected Components 강하게연결됨 그래프의모든정점쌍에대해서양방향으로경로가존재하면강하게연결되었다고한다 강하게연결된부분그래프를강연결요소 Strongly connected component 라한다 임의의그래프에서강연결요소들을찾는다 - - 한빛미디어

60 SCC 구하기알고리즘 stronglyconnectedcomponent(g) {. 그래프에대해 DFS 를수행하여각정점 v 의완료시간 f v 를계산한다 ;. G R 을만든다 ;. DFS 를수행하되시작점은 에서구한 f v 가가장큰정점으로잡는다 ;. 에서만들어진분리된트리들각각을강연결요소로리턴한다 ; } ü 수행시간 : Θ( V + E ) 한빛미디어

61 stronglyconnectedcomponent 의작동예 G (a) G G (b) 0 (c) 0 G R 0 (d) - - 한빛미디어

62 0 G R 0 G R 0 G R (e) (f) (g) G R G R 0 0 (i) (h) - - 한빛미디어

63 Thank you - - 한빛미디어

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

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

More information

슬라이드 1

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

More information

5장 스택

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

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

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

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

More information

슬라이드 1

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

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

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

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

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

More information

Microsoft PowerPoint - slide05.pptx

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

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

쉽게배우는알고리즘 8장. 동적프로그래밍 프로그래밍 Dynamic Programming (DP)

쉽게배우는알고리즘 8장. 동적프로그래밍 프로그래밍 Dynamic Programming (DP) 쉽게배우는알고리즘 8장. 동적프로그래밍 프로그래밍 Dynamic Programming (DP) http://academy.hanb.co.kr IT COOKBOOK 8장. 동적프로그래밍 Dynamic Programming (DP) 계시란바깥어딘가에서우리한테갑자기주어지는객관적지식이아니다. 만물의근원에대한본질적인귀속감, 우리가거기에아주밀접하게닿아있다는관계성을스스로가발견해내는것이계시다.

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

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

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

쉽게 배우는 알고리즘 강의노트 쉽게배우는알고리즘 장. 정렬 Sorting http://www.hanbit.co.kr 장. 정렬 Sorting 은유, 그것은정신적상호연관성의피륙을짜는방법이다. 은유는살아있다는것의바탕이다. - 그레고리베이트슨 - 2 - 학습목표 기본정렬알고리즘을이해한다. 정렬을귀납적관점에서볼수있도록한다. 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

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

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

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

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

쉽게배우는알고리즘 6장. 해시테이블 테이블 Hash Table

쉽게배우는알고리즘 6장. 해시테이블 테이블 Hash Table 쉽게배우는알고리즘 6장. 해시테이블 테이블 Hash Table http://academy.hanb.co.kr 6장. 해시테이블 테이블 Hash Table 사실을많이아는것보다는이론적틀이중요하고, 기억력보다는생각하는법이더중요하다. - 제임스왓슨 - 2 - 학습목표 해시테이블의발생동기를이해한다. 해시테이블의원리를이해한다. 해시함수설계원리를이해한다. 충돌해결방법들과이들의장단점을이해한다.

More information

PowerPoint 프레젠테이션

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

More information

PowerPoint 프레젠테이션

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

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

최소비용흐름문제의선형계획모형 최소비용흐름문제는선형계획문제로표현할수있다. 예 4.1 의최소비용흐름문제는다음과같은선형계획문제가된다. min z = 5x 12 +4x 13 +7x 14 +2x x 34 +8x 35 +5x 45 sub.to x 12 +x 13 +x

최소비용흐름문제의선형계획모형 최소비용흐름문제는선형계획문제로표현할수있다. 예 4.1 의최소비용흐름문제는다음과같은선형계획문제가된다. min z = 5x 12 +4x 13 +7x 14 +2x x 34 +8x 35 +5x 45 sub.to x 12 +x 13 +x 최소비용흐름문제의선형계획모형 최소비용흐름문제는선형계획문제로표현할수있다. 예. 의최소비용흐름문제는다음과같은선형계획문제가된다. min z = 5x 2 +x +7x +2x 25 +0x +8x 5 +5x 5 sub.to x 2 +x +x = 0, x 2 +x 25 =, x +x +x 5 = -, x x +x 5 = -, x 25 x 5 x 5 = -7, x 2 apple,

More information

DBPIA-NURIMEDIA

DBPIA-NURIMEDIA SPFA 를기반으로개선된벨만 - 포드알고리듬 SPFA 를기반으로개선된벨만 - 포드알고리듬 진호 * 서희종 ** An improved Bellman-Ford algorithm based on SPFA Hao Chen * Hee-Jong Suh ** 요약 이논문에서 SPFA(shortest path faster algorithm) 을사용해서기존의벨만-포드 (Bellman-Ford)

More information

CH06)자료구조.hwp

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

More information

<FEFF11121162110211611106116E002D1107116911B71112116900330036002E0069006E0064006400000000000093782FC816B427590034001CBDFC1B558B202E6559E830EB00000000937C28D9>

<FEFF11121162110211611106116E002D1107116911B71112116900330036002E0069006E0064006400000000000093782FC816B427590034001CBDFC1B558B202E6559E830EB00000000937C28D9> 02 04 06 14 16 19 24 26 27 28 31 3 4 5 세상과 (소통)하다!! 세상과 (소통)하다!! 세상과 (소통)하다!! 6 7 건강지원 프로그램으로 굳어져가는 몸과 마음을 풀어보아요~ 8 9 새해 복 많이 받으세요~ 10 11 12 13 14 15 14 14 14 14 15 15 16 17 18 19 20 21 방과 후 교실(해나무 주간보호센터

More information

-09- 학습목표 기본정렬알고리즘을이해한다. 정렬을귀납적관점에서볼수있도록한다. 1 장과 2 장에서배운기법을사용해각정렬의수행시간을분석할수있도록한다. 비교정렬의한계를이해하고, 선형시간정렬이가능한조건과선형시간정렬알고리즘을이해한다. - - 한빛미디어 Sortng Algorth

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

More information

쉽게배우는알고리즘 10장. 문자열매칭

쉽게배우는알고리즘 10장. 문자열매칭 쉽게배우는알고리즘 1장. 문자열매칭 http://academy.hanb.co.kr 1장. 문자열매칭 전혀새로운아이디어를갑자기착상하는일이자주있다. 하지만그것을착상하기까지줄곧오랜동안문제를생각하고있다. 오랜동안생각한끝에갑자기답을착상하게되는것이다. - 라이너스폴링 - 2 - 한빛미디어 학습목표 원시적인매칭방법에깃든비효율성을감지할수있도록한다. 오토마타를이용한매칭방법을이해한다.

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

쿠폰형_상품소개서

쿠폰형_상품소개서 브랜드이모티콘 쿠폰형 상품 소개서 카카오톡 브랜드이모티콘 잘 만든 브랜드이모티콘 하나, 열 마케팅 부럽지 않다! 카카오톡 브랜드이모티콘은 2012년 출시 이후 강력한 마케팅 도구로 꾸준히 사랑 받고 있습니다. 브랜드 아이덴티티를 잘 반영하여 카카오톡 사용자의 적극적인 호응과 브랜딩 지표 향상을 얻고 있는 강력한 브랜드 아이템입니다. Open

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

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

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

Microsoft PowerPoint - 08_Dynamic_Prog_01.pptx

Microsoft PowerPoint - 08_Dynamic_Prog_01.pptx CSW3010 (Introduction to Computer Algorithms) 담당교수 : 임종석서강대학교컴퓨터공학과 Dynamic Programming ( 동적계획알고리즘 ) Optimization Problem 을해결하기위한알고리즘. Bottom-up Approach : 주어진 instance 에대하여 1. 크기가가장작은모든 sub-instance 들에대해해를각각구하여저장한다.

More information

sna-node-ties

sna-node-ties Node Centrality in Social Networks Nov. 2015 Youn-Hee Han http://link.koreatech.ac.kr Importance of Nodes ² Question: which nodes are important among a large number of connected nodes? Centrality analysis

More information

와플-4년-2호-본문-15.ps

와플-4년-2호-본문-15.ps 1 2 1+2 + = = 1 1 1 +2 =(1+2)+& + *=+ = + 8 2 + = = =1 6 6 6 6 6 2 2 1 1 1 + =(1+)+& + *=+ =+1 = 2 6 1 21 1 + = + = = 1 1 1 + 1-1 1 1 + 6 6 0 1 + 1 + = = + 7 7 2 1 2 1 + =(+ )+& + *= + = 2-1 2 +2 9 9 2

More information

(Hyunoo Shim) 1 / 24 (Discrete-time Markov Chain) * 그림 이산시간이다연쇄 (chain) 이다왜 Markov? (See below) ➀ 이산시간연쇄 (Discrete-time chain): : Y Y 의상태공간 = {0, 1, 2,..., n} Y n Y 의 n 시점상태 {Y n = j} Y 가 n 시점에상태 j 에있는사건

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

1 1 장. 함수와극한 1.1 함수를표현하는네가지방법 1.2 수학적모형 : 필수함수의목록 1.3 기존함수로부터새로운함수구하기 1.4 접선문제와속도문제 1.5 함수의극한 1.6 극한법칙을이용한극한계산 1.7 극한의엄밀한정의 1.8 연속

1 1 장. 함수와극한 1.1 함수를표현하는네가지방법 1.2 수학적모형 : 필수함수의목록 1.3 기존함수로부터새로운함수구하기 1.4 접선문제와속도문제 1.5 함수의극한 1.6 극한법칙을이용한극한계산 1.7 극한의엄밀한정의 1.8 연속 1 1 장. 함수와극한 1.1 함수를표현하는네가지방법 1.2 수학적모형 : 필수함수의목록 1.3 기존함수로부터새로운함수구하기 1.4 접선문제와속도문제 1.5 함수의극한 1.6 극한법칙을이용한극한계산 1.7 극한의엄밀한정의 1.8 연속 2 1.1 함수를표현하는네가지방법 함수 f : D E 는집합 D 의각원소 x 에집합 E 에속하는단하나의원소 f(x) 를 대응시키는규칙이다.

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

3.2 함수의정의 Theorem 6 함수 f : X Y 와 Y W 인집합 W 에대하여 f : X W 는함수이다. Proof. f : X Y 가함수이므로 f X Y 이고, Y W 이므로 f X W 이므로 F0이만족된다. 함수의정의 F1, F2은 f : X Y 가함수이므로

3.2 함수의정의 Theorem 6 함수 f : X Y 와 Y W 인집합 W 에대하여 f : X W 는함수이다. Proof. f : X Y 가함수이므로 f X Y 이고, Y W 이므로 f X W 이므로 F0이만족된다. 함수의정의 F1, F2은 f : X Y 가함수이므로 3.2 함수의정의 Theorem 6 함수 f : X Y 와 Y W 인집합 W 에대하여 f : X W 는함수이다. Proof. f : X Y 가함수이므로 f X Y 이고, Y W 이므로 f X W 이므로 F0이만족된다. 함수의정의 F1, F2은 f : X Y 가함수이므로성립한다. Theorem 7 두함수 f : X Y 와 g : X Y 에대하여, f = g f(x)

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

Algorithms

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

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

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

review050829.hwp

review050829.hwp 한국무역협회 무역연구소 서울시 강남구 삼성동 무역센터 트레이드타워 4801호 Tel: 6000-5174~9 Fax: 6000-6198 홈페이지 : http://tri.kita.net - 1 - 5 4 (% ) 경상수지(G DP 대 비) 추 이 일본 독일 3 네덜란드 2 1 아일랜드 0-1 -2 [1만불 - 2 만불 달성기간 ] -일본(80-88) -독일(79-90)

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

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

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

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

More information

쉽게배우는알고리즘 6 장. 해시테이블 Hash Table IT COOKBOOK 6 장. 해시테이블 Hash Table 그에게서배운것이아니라이미내속에있었던것이그와공명을한것이다. - 제임스왓슨 한

쉽게배우는알고리즘 6 장. 해시테이블 Hash Table   IT COOKBOOK 6 장. 해시테이블 Hash Table 그에게서배운것이아니라이미내속에있었던것이그와공명을한것이다. - 제임스왓슨 한 쉽게배우는알고리즘 6 장. 해시테이블 Hash Table http://academy.hanb.co.kr 6 장. 해시테이블 Hash Table 그에게서배운것이아니라이미내속에있었던것이그와공명을한것이다. - 제임스왓슨 - 2 - 한빛미디어 학습목표 해시테이블의발생동기를이해한다. 해시테이블의원리를이해한다. 해시함수설계원리를이해한다. 충돌해결방법들과이들의장단점을이해한다.

More information

chap x: G입력

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

More information

Microsoft PowerPoint - Chap6 [호환 모드]

Microsoft PowerPoint - Chap6 [호환 모드] Data Structure (Chapter 6: Graphs) Sprig, 2 Sookmyug Womeʼs Uiv. Departmet of Multimedia Sciece Prof. Youg-Ho Park Graph 관련주요용어 ( 참고 ) Complete graph : a graph i which there is a edge betwee every pair

More information

Vector Differential: 벡터 미분 Yonghee Lee October 17, 벡터미분의 표기 스칼라미분 벡터미분(Vector diffrential) 또는 행렬미분(Matrix differential)은 벡터와 행렬의 미분식에 대 한 표

Vector Differential: 벡터 미분 Yonghee Lee October 17, 벡터미분의 표기 스칼라미분 벡터미분(Vector diffrential) 또는 행렬미분(Matrix differential)은 벡터와 행렬의 미분식에 대 한 표 Vector Differential: 벡터 미분 Yonhee Lee October 7, 08 벡터미분의 표기 스칼라미분 벡터미분(Vector diffrential) 또는 행렬미분(Matrix differential)은 벡터와 행렬의 미분식에 대 한 표기법을 정의하는 방법이다 보통 스칼라(scalar)에 대한 미분은 일분수 함수 f : < < 또는 다변수 함수(function

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

Sequences with Low Correlation

Sequences with Low Correlation 레일리페이딩채널에서의 DPC 부호의성능분석 * 김준성, * 신민호, * 송홍엽 00 년 7 월 1 일 * 연세대학교전기전자공학과부호및정보이론연구실 발표순서 서론 복호화방법 R-BP 알고리즘 UMP-BP 알고리즘 Normalied-BP 알고리즘 무상관레일리페이딩채널에서의표준화인수 모의실험결과및고찰 결론 Codig ad Iformatio Theory ab /15

More information

<4D F736F F F696E74202D20C0DAB7E1B1B8C1B65FC3E2BCAEBCF6BEF7>

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

More information

중간고사

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

More information

Microsoft PowerPoint - 04알고리즘

Microsoft PowerPoint - 04알고리즘 이산수학 Discrete Mathematics 알고리즘 (Algorithm) 인천대학교컴퓨터공학과공학시인이숙이철호교수 Jullio@chol.com zullio@inu.ac.kr 010 3957 6683 모바일컴퓨팅연구실 07 401 호 상어가바다의절대제왕이된이유 출처 : 조영탁의행복한경영이야기 상어는물고기중유일하게부레가없다. 부레없는물고기는물속에서생존이불가능하다.

More information

카이스트전산학과대학원입시기출문제모음

카이스트전산학과대학원입시기출문제모음 카이스트전산학과대학원입시기출문제모음 2014.5 1. Programming Language / Compiler 자바에서 public, protected, private 키워드가있는데아무것도안쓸경우 default로적용되는범위는? Static typing과 dynamic typing의차이점은? C++/JAVA은어떤 typing을사용하는가? C++ 에서서로다른타입의오브젝트를가리키는포인터를사용할수있나?

More information

Microsoft PowerPoint - 제8장-트리.pptx

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

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 11 곡선과곡면 01 Spline 곡선 02 Spline 곡면 03 Subdivision 곡면 C n 연속성 C 0 연속성 C 1 연속성 2 C 2 연속성 01 Spline 곡선 1. Cardinal Spline Curve 2. Hermite Spline Curve 3. Bezier Spline Curve 4. Catmull-Rom Spline Curve 5.

More information

슬라이드 1

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

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 박종혁교수 ( 컴퓨터공학과 ) jhpark1@seoultech.ac.kr http://www.parkjonghyuk.net 2017-2 학기 학습개요 7장데이터구성 1. 이름 2. 리스트 (List) 3. 그래프 4. 계층 조별과제 다음주강의시간발표 1 학습목표 적절하게이름짓는것의중요성을이해한다. 컴퓨터시스템의메모리안에어떻게데이터가구성하는지를이해한다. 리스트,

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

Microsoft PowerPoint - 05알고리즘.pptx

Microsoft PowerPoint - 05알고리즘.pptx 이산수학 Discrete Mathematics 알고리즘 (Algorithm) 인천대학교컴퓨터공학과공학시인이숙이철호교수 Jullio@chol.com zullio@inu.ac.kr 010 3957 6683 모바일컴퓨팅연구실 07 401 호 꿈의중독자가되라 출처 : 조영탁의행복한경영이야기나는여러분이 꿈중독자 가되었으면합니다. 꿈이크고꿈이선명하면남이하지말라고해도스스로열심히노력하게될것입니다.

More information

Introduction to Deep learning

Introduction to Deep learning Introduction to Deep learning Youngpyo Ryu 동국대학교수학과대학원응용수학석사재학 youngpyoryu@dongguk.edu 2018 년 6 월 30 일 Youngpyo Ryu (Dongguk Univ) 2018 Daegu University Bigdata Camp 2018 년 6 월 30 일 1 / 66 Overview 1 Neuron

More information

02(007-014) CPL12-16.hwp

02(007-014) CPL12-16.hwp 국내 웹 그래프의 링크 구조 분석 7 국내 웹 그래프의 링크 구조 분석 (Link Structure Analysis of Korean Web Graph) 서 정 주 김 진 일 김 은 상 김 영 호 (Jungjoo Seo) (Jinil Kim) (Eunsang Kim) (Daniel Kim) 정 하 웅 김 성 렬 박 근 수 (Hawoong Jeong) (Sung-Ryul

More information

ºñ»óÀå±â¾÷ ¿ì¸®»çÁÖÁ¦µµ °³¼±¹æ¾È.hwp

ºñ»óÀå±â¾÷ ¿ì¸®»çÁÖÁ¦µµ °³¼±¹æ¾È.hwp V a lu e n C F = t 1 (1 r ) t t = + n : 평 가 자 산 의 수 명 C F t : t 기 의 현 금 흐 름 r: 할 인 율 또 는 자 본 환 원 율 은 행 1. 대 부 금 5. 대 부 금 상 환 E S O P 2. 주 식 매 입 3. 주 식 4. E S O P 기 여 금 기 업 주인으로 쌍방향의 투명

More information

sort(arr, arr + n); int a, b; a = b = -1; for(i = n - 2; i >= 0; i--) if(!chk[i + 1] && arr[i] == arr[i + 1]) if(a == -1) a = arr[i]; else b = arr[i];

sort(arr, arr + n); int a, b; a = b = -1; for(i = n - 2; i >= 0; i--) if(!chk[i + 1] && arr[i] == arr[i + 1]) if(a == -1) a = arr[i]; else b = arr[i]; Run@KAIST 2주차 연습 20160021 Hanpil Kang Mar 11 Mar 17, 2018 1 A to Z 쉬운 문제입니다. 가장 왼쪽에 있는 A와 가장 오른쪽에 있는 Z를 잡아서 부분문자열을 만들면 됩니다. #include int N; char s[202020]; cin >> s; N = strlen(s); int a,z;

More information

집합 집합 오른쪽 l 3. (1) 집합 X 의각원소에대응하는집합 Y 의원소가단하나만인대응을 라할때, 이대응 를 X 에서 Y 로의라고하고이것을기호로 X Y 와같이나타낸다. (2) 정의역과공역정의역 : X Y 에서집합 X, 공역 : X Y 에서집합 Y (3) 의개수 X Y

집합 집합 오른쪽 l 3. (1) 집합 X 의각원소에대응하는집합 Y 의원소가단하나만인대응을 라할때, 이대응 를 X 에서 Y 로의라고하고이것을기호로 X Y 와같이나타낸다. (2) 정의역과공역정의역 : X Y 에서집합 X, 공역 : X Y 에서집합 Y (3) 의개수 X Y 어떤 다음 X 대응 1. 대응 (1) 어떤주어진관계에의하여집합 X 의원소에집합 Y 의원소를짝지어주는것을집합 X 에서집합 Y 로의대응이라고한다. l (2) 집합 X 의원소 에집합 Y 의원소 가짝지어지면 에 가대응한다고하며이것을기호로 와같이나타낸다. 2. 일대일대응 (1) 집합 A 의모든원소와집합 B 의모든원소가하나도빠짐없이꼭한개씩서로대응되는것을집합 A 에서집합

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

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 경영학을 위한 수학 Final Exam 2015/12/12(토) 13:00-15:00 풀이과정을 모두 명시하시오. 정리를 사용할 경우 명시하시오. 1. (각 6점) 다음 적분을 구하시오 Z 1 4 Z 1 (x + 1) dx (a) 1 (x 1)4 dx 1 Solut

1 경영학을 위한 수학 Final Exam 2015/12/12(토) 13:00-15:00 풀이과정을 모두 명시하시오. 정리를 사용할 경우 명시하시오. 1. (각 6점) 다음 적분을 구하시오 Z 1 4 Z 1 (x + 1) dx (a) 1 (x 1)4 dx 1 Solut 경영학을 위한 수학 Fial Eam 5//(토) :-5: 풀이과정을 모두 명시하시오. 정리를 사용할 경우 명시하시오.. (각 6점) 다음 적분을 구하시오 4 ( ) (a) ( )4 8 8 (b) d이 성립한다. d C C log log (c) 이다. 양변에 적분을 취하면 log C (d) 라 하자. 그러면 d 4이다. 9 9 4 / si (e) cos si

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

<3230303420B0B3C0CEC1A4BAB8BAD0C0EFC1B6C1A4BBE7B7CAC1FD2E687770>

<3230303420B0B3C0CEC1A4BAB8BAD0C0EFC1B6C1A4BBE7B7CAC1FD2E687770> 인터넷 전화/팩스/이메일 방문 접수통보 분쟁조정 신청 및 접수 Case Screening 불만의 해소, 타기관 이첩 등 증거수집, 전문가 자문 등 사실조사 조정전 합의권고 YES 합의 NO 조정결정 NO 민사소송 또는 포기 YES 종료 200 180 190 180 160 163 140 120 100 80 60 40 20 116 100 57 93

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

REP - networkx - 019, JULY 2010 2 어 있고 Windows 계열도 지원하지만, Winodws OS의 경우 많은 버그를 가지고 있기 때문에 현재 Windows 운영 체제와 정상적으로 호환되는 패키지는 NetworkX 이다. 각 패키지의 종류와 각

REP - networkx - 019, JULY 2010 2 어 있고 Windows 계열도 지원하지만, Winodws OS의 경우 많은 버그를 가지고 있기 때문에 현재 Windows 운영 체제와 정상적으로 호환되는 패키지는 NetworkX 이다. 각 패키지의 종류와 각 REP - networkx - 019, JULY 2010 1 NetworkX를 이용한 Python 그래프 가시화 Graph Visualization from Python Using NetworkX 부산대학교 컴퓨터공학과 김선영 E-mail : s.y.kim@pusan.ac.kr Revised on 2010.07.27 ABSTRACT Python은 사용하기 쉬운

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

Run 봄 연습 Mar 18 Mar 24, 2018, Week 3 문제 1. 초코바 입력 파일: 출력 파일: 시간 제한: 메모리 제한: standard input standard output 1 seconds 128 megabytes H W 격자 모양의 초콜릿이 있다.

Run 봄 연습 Mar 18 Mar 24, 2018, Week 3 문제 1. 초코바 입력 파일: 출력 파일: 시간 제한: 메모리 제한: standard input standard output 1 seconds 128 megabytes H W 격자 모양의 초콜릿이 있다. 문제. 초코바 H W 격자 모양의 초콜릿이 있다. 이 초콜릿을 개의 직사각형으로 격자를 따라서 잘라서, 최대 넓이의 초콜릿과 최소 넓이의 초콜릿의 넓이 차이를 최소화 하고 싶다. 이 차이의 최솟값을 구하여라. 첫째 줄에 H와 W 가 공백으로 구분되어 주어진다. 초콜릿을 개의 직사각형으로 자를 때, 최대 넓이의 초콜릿과 최소 넓이의 초콜릿의 넓이 차이의 최솟값을

More information

LIDAR와 영상 Data Fusion에 의한 건물 자동추출

LIDAR와 영상 Data Fusion에 의한 건물 자동추출 i ii iii iv v vi vii 1 2 3 4 Image Processing Image Pyramid Edge Detection Epipolar Image Image Matching LIDAR + Photo Cross correlation Least Squares Epipolar Line Matching Low Level High Level Space

More information

슬라이드 1

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

More information

Microsoft Word - FunctionCall

Microsoft Word - FunctionCall Function all Mechanism /* Simple Program */ #define get_int() IN KEYOARD #define put_int(val) LD A val \ OUT MONITOR int add_two(int a, int b) { int tmp; tmp = a+b; return tmp; } local auto variable stack

More information

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

REP - NETWORKX - 019, JULY NetworkX 를이용한 Python 그래프가시화 Graph Visualization from Python Using NetworkX 김선영 Kim SeonYeong 부산대학교컴퓨터공학과

REP - NETWORKX - 019, JULY NetworkX 를이용한 Python 그래프가시화 Graph Visualization from Python Using NetworkX 김선영 Kim SeonYeong 부산대학교컴퓨터공학과 REP - NETWORKX - 019, JULY 2010 1 NetworkX 를이용한 Python 그래프가시화 Graph Visualization from Python Using NetworkX 김선영 Kim SeonYeong 부산대학교컴퓨터공학과 s.y.kim@pusan.ac.kr ABSTRACT Python 은사용하기쉬운오픈소스프로그래밍언어로, 그사용자가늘어나고있는추세이다.

More information

PowerPoint 프레젠테이션

PowerPoint 프레젠테이션 Lec. 2 : Introduction to R Part 2 Big Data Analytics Short Course 17. 07. 04 R 의데이터구조 : Factor factor() : factor 생성하기 > region = c("a","a","b","c","d") > region [1] "A" "A" "B" "C" "D" > class(region)

More information