본문 바로가기

알고리즘17

16-3강. 최단경로 알고리즘 (Shortest Path Algorithm) (3) 이전 강좌 첨부,, 16-3강. 최단경로 알고리즘 (Shortest Path Algorithm) (3) 이전 강좌,,, Bellman-Ford Algo- 나 Dijkstra Algo-는 one-to-all 알고리즘이었다. 이번 강좌에서는 all-to-all 알고리즘에 대해 공부한다. all-to-all 알고리즘의 하나가 Floyd Algorithm 혹은 Floyd-Warshall Algorithm이다. Floyd-Warshall 알고리즘 - 가중치 방향 그래프 G=(V, E), V={1, 2, ..., n} (노드들에는 1번부터 n번까지 번호가 붙어 있다..) - 모든 노드 쌍들 간의 최단경로의 길이를 구함 - d의 k승[i, j] ㄴ 중간에 노드집합 {1, 2, ..., k}에 속한 노드들만 거쳐서 노.. 2021. 1. 10.

16-1강. 최단경로 (Shortest Path Problem) (1) 아이패드 굿노트를 사용해서 적은 필기 2021. 1. 6.

15-4. 최소비용신장트리( Minimum Spanning Tree) Prim의 알고리즘 - 임의의 노드를 출발노드로 선택 - 출발 노드를 포함하는 트리를 점점 키워 감 (크러스칼은 에지들의 가중치가 작은 순서대로 접근하는 방법이었다면, 프림은 출발노드부터 연결 연결된 노드들을 탐색하여 트리를 키운다) - 매 단계에서 이미 트리에 포함된 노드와 포함되지 않은 노드를 연결하는 에지들 중 가장 가중치가 작은 에지를 선택 위의 그래프에서 출발 노드가 초록색 노드라고 하면, 출발 노드에 인접한 노드들을 A라 하면, 그 부분트리에 포함된 노드들의 집합은 V of A(빨간 노드들)라 하자. (a) : 출발노드 a 에서 인접한 노드 b와 노드 k 가 있다. 가중치가 작은 에지는 4이므로 노드 b를 선택한다. (b) : 이제 노드 a 와 노드 b는 V of A의 부분집합이 되었다. (c.. 2020. 12. 17.

15-2강. 최소비용신장트리 (Minimum Spanning Tree) (2) 최소비용신장트리 (Minimum Spanning Tree) Kruskal의 알고리즘 - 에지들을 가중치의 오름차순으로 정렬한다. - 에지들을 그 순서대로 하나씩 선택해 간다. 단, 이미 선택된 에지들과 사이클(cycle)을 형성하면 선택하지 않는다. - n-1개의 에지가 선택되면 종료한다. 위의 그래프에서, 모른 에지들을 작은 것부터 큰 것 순으로 정렬해 두었다고 가정하자. (a) : 가장 가중치(weight)가 작은 에지(1)를 선택한다. => 내가 선택한 에지들은 cycle을 형성하지 않는다. (왜? 에지가 하나밖에 선택되지 않았으니까) (b) : 그 다음으로 가중치(weight)가 작은 에지(2)를 선택한다. => cycle을 형성하지 않는다. (c) : 그 다음으로 가중치(weight)가 작은 에.. 2020. 12. 13.

15-1강. 최소비용신장트리(Minimum spanning tree) 최소비용신장트리 (Minimum Spanning Tree) - 입력 : n 개의 도시, 도시와 도시를 연결하는 도로 비용 - 문제 : 최소의 비용으로 모든 도시들이 서로 연결되게 한다. 해가 유일하지는 않다.. 예) (b, c) 대신에 (a, h)가 되어도 된다. -> 비용이 같고, 다 연결되기 때문이다. * 최소비용신장트리의 답은 항상 트리가 된다. 왜? (트리 : 싸이클이 없는 연결된(connected) 무방향 그래프) : cycle이 있다는 말은 이쪽 방향으로 가도 저쪽 방향으로 가도 되는데, 이 경우 한 쪽의 길이 끊어져도 반대 방향으로 갈 수 있게 된다. 따라서 우리는 최소비용을 원하므로 cycle이 있는 그래프는 이 경우에서 제외한다. - 어떤 MST(Minimun Spanning Tree)의.. 2020. 12. 11.

14-4강. DAG와 위상순서 DAG (Directed Acyclic Graph) : 방향 사이클(directed cycle)이 없는 방향 그래프. (자기 자신으로 돌아오지 않는 방향그래프..) 예) 작업들의 우선순위 위의 그래프에서 b가 되기 위해서는 a가 반드시 선행되어야 한다! 위상정렬 (topological ordering) - DAG에서 노드들의 순서화(sorting) .. v1, v2, ..., vn. 단 모든 에지(vi, vj)에 대해서 i < j가 되도록! 위의 그래프에서 위상정렬을 했을 때, 왼쪽에서 오른쪽 방향으로 정렬했을 때, a-g-... 또는 a-b-... 인데, 역방향으로 가면 안 된다. (오른쪽에서 왼쪽으로 가면 절대 안 된다.) 어떤 노드에 대해서 들어오는 노드의 갯수를 in-degree, 나가는 노드의 .. 2020. 12. 8.

14-3강. 그래프에서의 DFS DFS(Depth-First Search) 깊이 우선 탐색 level order traversal (BFS) inorder traversal (DFS) pre-order traversal (DFS) post-order traversal (DFS) 1. 출발점 s에서 시작한다. 2. 현재 노드를 visited로 mark하고, 인접한 노드들 중 unvisited 노드가 존재하면 그 노드로 간다. 3. 2번을 계속 반복한다. 4. 만약 unvisited인 이웃노드가 존재하지 않는 동안 계속해서 직전 노드로 되돌아 간다. 5. 다시 2번을 반복한다. 6. 시작노드 s로 돌아오고, 더이상 갈 곳이 없으면 종료한다. 이 그래프에서는 1-3-7-8-7-3-5-2-4-2-5-6 순서로 간다.. (하지만 순서는 바뀔 수.. 2020. 12. 6.

14-1강. 그래프(Graph) 개념과 표현 (무방향) 그래프. G = (V, E) - V : 노드(node) 혹은 정점(vertex) - E : 노드 쌍을 연결하는 에지(edge) 혹은 링크(link) - 개체(object)들 간의 이진관계를 표현 - n = |V|, m = |E| 방향그래프(Directetd Graph). G=(V, E) - 에지(u, v)는 u로부터 v로의 방향을 가짐 가중치 (weighted) 그래프 - 에지마다 가중치(weight)가 지정 그래프의 표현 - 인접행렬 (adjacency matrix) - 인접리스트 (adjacency list) 위의 그림에서 m은 엣지의 갯수를 나타낸다.. n(:노드의 갯수) + 2m(:노드 갯수) 이어서 저장공간은 O(n+m)이다. 방향그래프를 표현하는 방법 가중치 그래프의 인접행렬 표현 .. 2020. 12. 1.

13-3. 해슁 3 좋은 해쉬 함수란? - 현실에서는 키들이 랜덤하지 않음 - 만약 키들의 통계적 분포에 대해 알고 있다면 이를 이용해서 해쉬 함수를 고안하는 것이 가능하겠지만 현실적으로 어려움 - 키들이 어떤 특정한 (가시적인) 패턴을 가지더라도 해쉬함수값이 불규칙적이 되도록 하는 게 바람직 - 해쉬함수 값이 키의 특정 부분에 의해서만 결정되지 않아야.. Division 기법 - h(k) = k mod m - 예 : m = 20 and k = 91 -> h(k) = 11 - 장점 : 한 번의 mod 연산으로 계산. 따라서 빠름. - 단점 : 어떤 m값에 대해서는 해쉬 함수값이 키값의 특정 부분에 의해서 결정되는 경우가 있음. 가령 m = 2^p이면 키의 하위 p비트가 해쉬함수 값이 됨. Multiplication 기법 -.. 2020. 11. 29.

이전 1 2 다음

티스토리툴바