Algorithm Lecture Notes 2023.05.04 PDF

ALGORITHM 2023.05.04 Hyun-Jun Kim Software Department @Chung-ang University • Algorithms – Design and Analysis • Divide and Conquer • Sorting • Selection Algorithm • Search Tree • Hash Table • Lists • Mid-Term Examination • Dynamic Programming • Graph Algorithm 1 • Graph Algorithm 2 • Greedy Alg...

ALGORITHM 2023.05.04 Hyun-Jun Kim Software Department @Chung-ang University • Algorithms – Design and Analysis • Divide and Conquer • Sorting • Selection Algorithm • Search Tree • Hash Table • Lists • Mid-Term Examination • Dynamic Programming • Graph Algorithm 1 • Graph Algorithm 2 • Greedy Algorithm • The Theory of NP • Shortest Path • Advanced Topic • Final Examination 학습목표 • 그래프의 표현법을 익힌다. • 너비 우선 탐색과 깊이 우선 탐색의 원리를 충분히 이해하도록 한다. • 신장 트리의 의미와 최소 신장 트리를 구하는 두 가지 알고리즘을 이해한다. • 그래프의 특성에 따라 가장 적합한 최단 경로 알고리즘을 선택할 수 있도록 한다. • 위상 정렬을 알고, DAG의 경우에 위상 정렬을 이용해 최단 경로를 구하는 방법을 이해한다. • 강연결 요소를 구하는 알고리즘을 이해하고 이 알고리즘의 정당성을 확신할 수 있도록 한다. • 본문에서 소개하는 각 알고리즘의 수행 시간을 분석할 수 있도록 한다. 그래프 • 현상이나 사물을 정점vertex과 간선edge으로 표현한 것 • Graph G = (V, E) – V: 정점 집합 – E: 간선 집합 • 두 정점이 간선으로 연결되어 있으면 인접adjacent하다고 한다 – 간선은 두 정점의 관계를 나타낸다 그래프의 예 철수 영희 준호 동건 재상 사람들간의 친분 관계를 나타낸 그래프 승우 그래프의 예 철수 9 영희 6 5 준호 7 9 동건 5 1 5 재상 친밀도를 가중치로 나타낸 친분관계 그래프 승우 그래프의 예 유향 그래프directed graph=digraph 철수 영희 준호 동건 재상 방향을 고려한 친분관계 그래프 승우 그래프의 예 철수 9 8 5 영희 7 8 5 준호 승우 2 9 6 동건 6 5 1 재상 가중치를 가진 유향 그래프 그래프의 표현 1: 인접행렬 • 인접행렬 N: 정점의 총 수 – NⅹN 행렬로 표현 • 원소 (i, j) = 1 : 정점 i 와 정점 j 사이에 간선이 있음 • 원소 (i, j) = 0 : 정점 i 와 정점 j 사이에 간선이 없음 – 유향 그래프의 경우 • 원소 (i, j)는 정점 i 로부터 정점 j 로 연결되는 간선이 있는지를 나타냄 – 가중치 있는 그래프의 경우 • 원소 (i, j)는 1 대신에 가중치를 가짐 그래프의 표현 1: 인접행렬 1 철수 2 영희 4 준호 6 승우 1 2 3 4 5 6 1 0 1 1 1 0 1 2 1 0 1 0 0 0 1 1 0 0 1 0 1 0 0 0 0 1 0 0 1 0 0 1 1 0 0 1 1 0 3 3 동건 5 재상 4 5 6 무향 그래프의 예 그래프의 표현 1: 인접행렬 1 철수 9 5 2 영희 6 4 준호 7 동건 6 승우 2 3 4 5 6 1 0 9 7 5 0 6 2 9 0 9 0 0 0 7 9 0 0 5 0 5 0 0 0 0 5 0 0 5 0 0 1 6 0 0 5 1 0 3 9 3 5 1 1 5 5 재상 4 5 6 가중치 있는 무향 그래프의 예 그래프의 표현 1: 인접행렬 1 철수 2 영희 4 준호 6 승우 1 2 3 4 5 6 1 0 1 1 1 0 1 2 1 0 1 0 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 1 0 3 3 동건 5 재상 4 5 6 유향 그래프의 예 그래프의 표현 1: 인접행렬 1 철수 9 2 8 5 영희 7 6 8 4 준호 2 9 6 3 동건 5 5 재상 6 5 승우 1 2 3 4 5 6 1 0 8 7 5 0 6 2 9 0 6 0 0 0 0 9 0 0 5 0 8 0 0 0 0 5 0 0 0 0 0 2 0 0 0 0 1 0 3 1 4 5 6 가중치 있는 유향 그래프의 예 그래프의 표현 1: 인접행렬 유향 그래프의 다른 예 그래프의 표현 1: 인접행렬 가중치 있는 그래프의 다른 예 그래프의 표현 2: 인접리스트 •인접 리스트 – N 개의 연결 리스트로 표현 – i 번째 리스트는 정점 i 에 인접한 정점들을 리스트로 연결해 놓음 – 가중치 있는 그래프의 경우 • 리스트에 가중치도 보관한다 그래프의 표현 2: 인접리스트 1 철수 2 영희 3 동건 4 준호 5 재상 무향 그래프의 예 6 승우 1 2 3 2 1 3 3 1 2 4 1 6 5 3 6 6 1 4 4 5 5 6 그래프의 표현 2: 인접리스트 1 철수 9 5 2 영희 6 4 준호 7 9 5 6 승우 가중치 있는 그래프의 예 1 3 동건 5 5 재상 1 2 9 3 7 2 1 9 3 9 3 1 7 2 9 4 1 5 6 5 5 3 5 6 1 6 1 6 4 5 4 5 5 5 5 1 6 6 그래프의 표현 3: 인접배열 •인접 배열 • N 개의 연결 배열로 표현 – i 번째 배열은 정점 i 에 인접한 정점들을 집합 – 가중치 있는 그래프의 경우 • 리스트에 가중치도 보관한다 그래프의 표현 3: 인접배열 1 각 정점에 인접한 정점 수 철수 2 영희 3 동건 4 준호 5 재상 6 승우 1 4 2 3 2 2 1 3 3 3 1 2 4 2 1 6 5 2 3 6 6 3 1 4 4 5 5 6 그래프의 표현 3: 인접배열 1 철수 2 영희 3 동건 배열에서 각 정점에 인접한 정점 목록의 끝자리 4 준호 5 재상 6 승우 1 4 2 3 2 6 1 3 3 9 1 2 4 11 1 6 5 13 3 6 6 16 1 4 4 5 5 6 각 표현들의 장단점 • 인접행렬 • Edge의 개수가 많을 때 유리 • 인접리스트 • Edge의 개수가 적을 때 유리 • 인접배열 • Edge를 자주 Check할 때 유리 • 포인터 관리 없음 • 인접해시테이블 • 그래프의 크기가 매우 클 때 • 인접정도를 따라가면서 계산할 때 불리 그래프에서 모든 정점 방문하기 • 대표적 두 가지 방법 – 너비우선탐색BFS (Breadth-First Search) – 깊이우선탐색DFS (Depth-First Search) • 너무나 중요함 – 그래프 알고리즘의 기본 – DFS/BFS는 다 아는 듯이 보이지만 이해의 수준은 큰 차이가 난다 – DFS/BFS는 뼛속 깊이 이해해야 좋은 그래프 알고리즘을 만들 수 있음 DFS/BFS로 동일한 트리 방문하기 DFS BFS BFS의 작동 예 2 1 1 3 2 4 (a) 5 1 (b) 3 6 4 2 2 5 1 8 6 4 7 5 1 3 8 3 6 4 (e) 7 7 (d) (c) BFS 너비 우선 탐색 BFS(G, v) { 리스트 for each v ∈ V –{s} visited[v] ← NO; visited[s] ← YES; enqueue(Q, s); while (Q ≠ ϕ) { u ← dequeue(Q); for each v ∈ L(u) ▷ s: 시작 정점 ▷ Q: 큐 ▷ L(u): 정점 u의 인접 if (visited[v] = NO) then visited[u] ← YES; enqueue(Q, v); } } } ü수행 시간: Θ(|V|+|E|) DFS의 작동 예 1 1 2 1 (b) (a) 2 1 3 1 4 5 2 3 4 2 (e) 3 (d) (c) DFS의 작동 예 (계속) 1 7 1 4 6 5 2 3 3 (f) 7 1 4 6 5 3 (g) 8 7 2 5 2 8 1 4 6 5 2 (i) 4 6 3 (h) DFS 깊이 우선 탐색 DFS(G) { } aDFS (v) { } for each v ∈ V visited[v] ← NO; for each v ∈ V if (visited[v] = NO) then aDFS(v); visited[v] ← YES; for each x ∈ L(v) ▷ L(v) : 정점 v의 인접 리스트 if (visited[x] = NO) then aDFS(x); ü수행 시간: Θ(|V|+|E|) 최소신장 트리 Minimum Spanning Trees의 작동 예 • 조건 – 무향 연결 그래프 • 연결 그래프connected graph : 모든 정점 간에 경로가 존재하는 그래프 • 트리 – 싸이클이 없는 연결 그래프 – n 개의 정점을 가진 트리는 항상 n-1개의 간선을 갖는다 • 그래프 G의 신장트리 – G의 정점들과 간선들로만 구성된 트리 • G의 최소신장트리 – G의 신장트리들 중 간선의 합이 최소인 신장트리 프림 Prim 알고리즘 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|) 힙 이용 프림 Prim 알고리즘의 작동 예 (a) ∞ 8 r 9 ∞ 13 11 12 9 5 12 ∞ 11 8 ∞ 8 8 7 (c) 8 0 11 13 7 (d) S 10 ∞ 9 ∞ ∞ 8 0 5 ∞ 8 8 S ∞ 0 11 (b) 10 S 9 5 12 ∞ 7 10 9 11 12 11 8 0 5 9 13 10 10 13 9 5 12 ∞ 11 8 ∞ 7 : 방금 S에 포함된 정점 : 방금 이완이 일어난 정점 (f) (e) 8 0 8 S 9 11 ∞ 9 12 8 8 (h) 7 8 0 8 5 9 5 9 7 11 8 8 S 12 7 11 0 9 7 (g) S 5 11 12 11 S 7 8 0 5 11 12 11 8 0 12 13 (i) 5 5 7 8 8 7 프림 Prim 알고리즘 Prim(G, r) ▷ G=(V, E): 주어진 그래프 ▷ r: 시작으로 삼을 정점 { S←Ф; ▷ S : 정점 집합 for each u∈V du ← ∞ ; dr ← 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 wuv< dv) then dv ← wuv ; } } 이완(relaxation) ü수행시간: O(|E|log|V|) extractMin(Q, d) { 집합 Q에서 d값이 가장 작은 정점 u를 리턴한다 ; } 힙 이용 크루스칼 Kruskal 알고리즘 Kruskal (G, r) { 1. T ← Ф ; ▷ T : 신장트리 2. 단 하나의 정점만으로 이루어진 n 개의 집합을 초기화한다; 3. 간선 집합 Q(=E)를 가중치가 작은 순으로 정렬한다; 4. while (T의 간선수 < n-1) { Q에서 최소비용 간선 (u, v)를 제거한다; 정점 u와 정점 v가 서로 다른 집합에 속하면 { 두 집합을 하나로 합친다; T ← T∪{(u, v)}; } } } ü수행시간: O(ElogV) 크루스칼 Kruscal 알고리즘의 작동 예 (b) (a) 11 8 14 8 14 9 13 5 12 9 13 12 11 8 8 8 14 9 13 12 7 8 7 8 (c) 11 (d) (e) 8 14 9 11 13 12 8 14 11 9 13 8 12 8 8 : 방금 고려한 간선 : 성공적으로 더해진 간선 (g) (f) 14 14 11 (i) 11 9 13 12 8 13 12 (h) 8 9 11 14 5 7 11 13 12 크루스칼 알고리즘의 수행시간 Step 2: Θ(V) Step 3: O(ElogE) = O(ElogV) Loop 4: O(Elog*V) by an efficient set handling Totally O(ElogV) 프림과 크루스칼 알고리즘의 이론적 근거 [안정성 정리] Let (S,V-S) an arbitrary partition of vertices. Let {u,v} be the min-weight edge among those crossing S and V-S. Then there exists at least a min. spanning tree containing {u,v}. <Proof> 본문 참조. 위상정렬 Topological Sorting • 조건 – 싸이클이 없는 유향 그래프 • 위상정렬 – 모든 정점을 일렬로 나열하되 – 정점 x에서 정점 y로 가는 간선이 있으면 x는 반드시 y보다 앞에 위치한다 – 일반적으로 임의의 유향 그래프에 대해 복수의 위상 순서가 존재한다 그래프에 대한 위상정렬의 예 (2개) 위상정렬 알고리즘1 topologicalSort1(G, v) { for ← 1 to n { 진입간선이 없는 정점 u를 선택한다; A[i] ← u; 정점 u와, u의 진출간선을 모두 제거한다; } ▷ 이 시점에 배열 A[1…n]에는 정점들이 위상정렬되어 있다 } ü수행 시간: Θ(|V|+|E|) 위상정렬 알고리즘1의 작동 예 점화 점화 남비에 물붓기 라면넣기 라면봉지 뜯기 수프넣기 계란 풀어넣기 (a) 남비에 물붓기 라면넣기 계란 풀어넣기 라면봉지 뜯기 수프넣기 (b) 남비에 물붓기 라면넣기 계란 풀어넣기 라면봉지 뜯기 수프넣기 점화 점화 남비에 물붓기 라면넣기 라면봉지 뜯기 수프넣기 계란 풀어넣기 (d) (c) 점화 점화 남비에 물붓기 라면넣기 라면봉지 뜯기 수프넣기 계란 풀어넣기 (e) 남비에 물붓기 라면넣기 라면봉지 뜯기 수프넣기 계란 풀어넣기 (f) 점화 남비에 물붓기 라면넣기 계란 풀어넣기 라면봉지 뜯기 수프넣기 (g)