728x90 알고리즘42 최소비용신장트리-1 Minimun Spanning Tree(MST) - 입력 : n개의 도시, 도시와 도시를 연결하는 비용 - 문제 : 최소의 비용으로 모든 도시들이 서로 연결되게 한다. - 무방향 가중치 그래프 G=(V,E) - 각 에지 (u,v)∈E에 대해서 가중치 w(u,v) - 문제 : 다음과 같은 조건을 만족하는 에지들의 부분집합 T⊆E를 찾아라 1. T에 속한 에지들에 의해 그래프의 모든 정점들이 서로 연결된다. 2. 가중치의 합이 최소가 된다. ** 왜 트리라고 부를까? - 싸이클이 없는 연결된 무방향 그래프를 트리라고 부른다. - MST는 항상 트리가 된다. 서로 연결이 되면서 최소 비용이 되기 위해서는 순환할 필요가 없다. 따라서 노드가 n개가 된다면 에지는 n-1개가 되기 때문이다. Generic MST .. 2021. 3. 23. 그래프 알고리즘 - 4 DAG(Direct Acyclic Graph) - DAG는 방향 사이클이 없는 방향 그래프 - 예 : 작업들의 우선순위 - DAG에서 노드들의 순서화 v1,v2,v3,....vn, 단, 모든 에지(vi,vj)에 대해서 i indegree = 0 : 들어오는 개수가 없다. 위상정렬 알고리즘 1 문제 - indegree가 0인 노드를 찾기 위해서 모든 노드의 indegree를 알아야 한다. - 진출간선을 제거했을 때 어떤 방법으로 구현할 것인지 어려움 위상정렬 알고리즘2 - dfs-ts는 보통의 깊이 우선탐색이랑 같지만 마지막 줄이 추가됨 - 처음에 마지막으로 도달한 노드는 outdegree가 없다 - 위상정렬 1에서는 가장 먼저 나오는 노드를 찾는 알고리즘이라면 - 위상정렬 2에서는 가장 마지막에 나오는 .. 2021. 3. 17. 그래프 알고리즘 - 3 깊이우선순회(DFS) 1. 출발점 s에서 시작 2. 현재 노드를 visited로 mark하고 인접한 노드들 중 unvisited노드가 존재하면 그 노드로 간다 3. 2번을 반복 4. 만약 unvisited인 이웃 노드가 존재하지 않는 동안 계속해서 직전 노드로 되돌아간다. 5. 다시 2번을 반복한다. 6. 시작노드 s로 돌아오고 더 이상 갈 곳이 없으면 종료한다. 수도코드 - 그래프가 disconnected이거나 혹은 방향 그래프라면 dfs에 의해서 모든 노드가 방문되지 않을 수도 있음 - DFS를 반복하여 모든 노드 방문 시간복잡도 : O(n+m) * 위의 그림들은 "영리한 프로그래밍을 위한 알고리즘" 강좌에서 가져왔습니다. 2021. 3. 17. 그래프 알고리즘 - 2 그래프 순회(Graph Traversal) - 순회 : 그래프의 모든 노드들을 방문하는 일 - 대표적 두 가지 방법 BFS (Breadth-First search, 너비우선순회) DFS ( Depth-First Search, 깊이우선순회) 너비우선순회(BFS) - BFS 알고리즘은 다음 순서로 노드들을 방문 L0 = {s}, 여기서 s는 출발 노드 L1 = L0의 모든 이웃 노드들 L2 = L1의 이웃들 중 L0에 속하지 않는 노드들 ..... Li = Li-1의 이웃들 중 Li-2에 속하지 않는 노드들 큐를 이용한 너비우선순회 -큐가 빌때까지 반복 - 탐색이 된 노드는 큐에서 제거 - 그 이웃한 노드들 큐에 삽입 후 방문했다고 체크 - 큐에 1을 넣는다 | 1 - 1을 제거하면서 큐에 인접한 2,3을 .. 2021. 3. 16. 그래프 알고리즘 - 1 그래프 - (무방향) 그래프 G=(V,E) - V : 노드(node) 혹은 정점(vertex) - E : 노드쌍을 연결하는 에지(edge) 혹은 링크(link) - 개체(object)들 간의 이진관계를 표현 - n=|v|, m=|E| - 방향 그래프(Directed Graph) G=(V,E) - 에지 (u,v)는 u로부터 v로의 방향을 가짐 - 가중치 그래프 : 에지마다 가중치가 지정 인접행렬 - n*n행렬 A = (aij) 연결되면 1, 안되면 0 연결리스트 - 정점 집합을 표현하는 하나의 배열과 - 각 정점마다 인접한 정점들의 연결 리스트 방향그래프 - 인접행렬은 비대칭 - 인접 리스트는 m개의 노드를 가짐 가중치 그래프의 인접행렬 표현 - 에지의 존재를 나타내는 값으로 1대신 에지의 가중치를 저장 .. 2021. 3. 16. hashing - 마지막 좋은 해쉬 함수란? - 현실에서는 키들이 랜덤하지 않음 - 만약 키들의 통계적 분포에 대해 알고 있다면 이를 이용해서 해쉬 함수를 고안하는 것이 가능하겠지만 현실적으로 어려움 - 키들이 어떤 특정한 (가시적인)패턴을 가지더라도 해쉬함수값이 불규칙적이 되도록 하는게 바람직 * 해쉬함수값이 키의 특정 부분에 의해서만 결정되지 않아야 함 Division 기법 h(k) = k mod m 예 : m = 20 and k = 91 => h(k) = 11 장점 : 한번의 mod연산으로 계산. 따라서 빠름 단점 : 어떤 m값에 대해서는 해쉬 함수값이 키값의 특정 부분에 의해서 결정되는 경우가 있음. 가령 m = 2^p이면 키의 하위 p비트가 해쉬 함수값이 됨. Multiplication 기법 0에서 1사이의 상수 A를 .. 2021. 3. 11. 이전 1 2 3 4 5 6 7 다음 728x90
