Dijkstra algorithm 다익스트라 알고리즘은 그래프에서 꼭짓점 간의 최단 경로를 찾는 알고리즘 위의 예제를 통해 알아보자 각 정점은 인접한 정점에 대한 정보만 가짐. 인접하지 않는 정점까지의 비용은 무한대로 초기화함 먼저 집합N'에 A를 넣으면 A의 정보로 다음과 같은 테이블을 만듬 A B C D E F A 0 10 30 15 무한대 무한대 집합N' A 다음비용이 가장 작은 B를 N'에 넣음 A B C D E F A 0 10 30 15 30 무한대 집합N' A,B B의 정보로 인해서 A->E까지의 경로가 업데이트 됨 다음단계에서는 비용이 가장 작은 D를 집합에 넣음 A B C D E F A 0 10 20 15 30 35 집합N' A, B, D D를 추가하면서 A->C의 경로보다 A->D->C의..

Floyd-Warshall Algorithm i -> j까지의 최소비용경로가 존재할 때, 정점k를 발견했다고 가정 k를 통해서 가는 경로와 통하지 않는 경로를 비교하여 비용이 작은 쪽을 선택하는 알고리즘 k를 통해서 가는것이 더 좋다면 간선완화를 함

Prim-Jarnik 1단계. 임의의 정점을 선택하고 트리에 넣음 (0을 선택했다고 가정) 그리고 인접 edge를 제외하고 모두 없다고 생각 2단계. 양쪽의 edge의 가중치를 확인한 후 정점1을 트리에 포함시킴 3단계. 정점1에서 인접한 edge중에서 가장 작은 가중치의 edge를 고름. 그리고 정점6을 트리에 포함시킴 4단계. 원래 1->4의 가중치가 5였는데 1->6의 edge가 생겼으므로 1->4의 edge를 없애고 4->6을 연결함(가중치 1) 5단계. 정점 6에서 인접한 edge중에서 가장 작은 가중치를 택함 정점을 추가할 때마다 cycle여부를 확인하지 않아도됨. 왜냐하면 트리내부의 정점을 택하는것이 아니라 외부의 정점을 택하기 때문임. 수행 성능 [파이썬 자료구조] Partition or ..

이전 포스팅에서 Kruskal 알고리즘에 대해서 알아보았음. [파이썬 자료구조] Kruskal 알고리즘 [파이썬 자료구조] 그래프(Graph) 그래프(G)는 정점(V)과 간선(E)으로 이루어져 있음 그래프의 종류 -무방향 그래프: 간선에 방향성이 없음 -방향성 그래프: 간선에 방향성이 있음 -가중치그래프: 간� ohaengsa.tistory.com Kruskal 알고리즘에서 cycle 여부를 확인하는 과정임. 정점X와 정점Y를 직접 연결하려할 때 정점X에서 Y로 가는 경로가 이미 존재하는지 확인하는 방법 만약 X,Y가 Z를 통해 연결되어있다면 X,Y를 직접 연결하는 edge를 버림 자기 자신을 가르키는 하나의 원소로 이루어짐 5개의 집합있다고 가정함. {0}과 {1}을 합치면 1은 0을 가르킨다. 왼쪽 ..

[파이썬 자료구조] 그래프(Graph) 그래프(G)는 정점(V)과 간선(E)으로 이루어져 있음 그래프의 종류 -무방향 그래프: 간선에 방향성이 없음 -방향성 그래프: 간선에 방향성이 있음 -가중치그래프: 간선에 가중치가 부여된 그래프 병 ohaengsa.tistory.com 최소신장트리(MST)는 edge의 가중치의 합이 최소인 신장트리임 신장트리란? 모든 정점을 연결하는 트리라고 생각하면됨. Kruskal 알고리즘 가중치의 크기순서대로 간선을 추가하며, 싸이클이 만들지 않는 알고리즘임 최소신장트리(MST)를 만드는 알고리즘 예제를 보면 7개의 정점과 12개의 edge가 있음. 각각의 edge에는 가중치가 있음. 0단계. edge를 가중치에 따라 정렬을 함 1단계. 정렬순서대로 (4,6)을 연결하는 ed..

그래프(G)는 정점(V)과 간선(E)으로 이루어져 있음 그래프의 종류 -무방향 그래프: 간선에 방향성이 없음 -방향성 그래프: 간선에 방향성이 있음 -가중치그래프: 간선에 가중치가 부여된 그래프 병렬 간선: X -> Z의 간선이 h,i 두개가 복수로 존개가능함 루프: 출발지 정점과 목적지 정점이 같은경우 ex) edge j 그래프G에서 점선을 다 지우면 G'인 그림임 부분 그래프: G'은 그래프G의 일부분임 V-V'을 잇는 E는 존재할 수없다. 신장부분그래프: 그래프 G'은 그래프G의 일부분인데 G의 모든 정점을 가지있음 연결 그래프: 모든 정점 간에 경로가 존재 트리는 연결그래프이고 Forest는 연결되지 않은 그래프임 파이썬으로 그래프 구현 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ..

[파이썬 자료구조] 깊이 우선 탐색 (DFS, depth first traversal) 그래프 순회는 그래프의 모든 정점을 방문하는 방법임 순회방법으로는 깊이 우선 탐색과 너비 우선 탐색이 있음. 먼저 깊이 우선 탐색에 대해 알아보자 unexplored vertex는 방문하지않은 정점이고 v ohaengsa.tistory.com 방향그래프는 기존의 그래프와 달리 정점과 간선 사이에 방향성을 추가한 그래프임 1단계. 임의의 점을 선택함 예제에서는 A를 선택했다고 가정함 2단계 A는 C, D, B로 갈 수 있음. B, D, E 순서로 방문하였다고 가정함 3단계. E는 A를 제외하고 갈 수 있는 곳이 없음. 하지만 A는 이미 방문함. E -> A를 Backedge(노란색)으로 표시함 4단계. 뒤로 돌아가서 B..

[파이썬 자료구조] 깊이 우선 탐색 (DFS, depth first traversal) 그래프 순회는 그래프의 모든 정점을 방문하는 방법임 순회방법으로는 깊이 우선 탐색과 너비 우선 탐색이 있음. 먼저 깊이 우선 탐색에 대해 알아보자 unexplored vertex는 방문하지않은 정점이고 v ohaengsa.tistory.com 너비 우선 탐색(Breadth-first search, BFS)은 맹목적탐색 방법의 하나로 시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법이다. 더 이상 방문하지 않은 정점이 없을 때까지 방문하지 않은 모든 정점들에 대해서도 너비 우선 검색을 적용한다. cross edge는 재방문을 막기위한 표시임 1단계. 임의의 점하나를 선택함(예제에서는 A를 선택..

정렬 중에서 퀵정렬에 대해서 알아보겠습니다. 2가지의 방식이 있습니다. 방법1. 1단계. 입력된 임의의 원소를 피벗으로 선택합니다. 피벗은 기준이 되는 원소입니다. 2단계. 피벗을 기준으로 작은 원소들, 피벗과 같은 원소들, 피벗보다 큰 원소들로 나눕니다. 3단계. 재귀적으로 정렬하고 크기순으로 놓으면 끝 파이썬으로 간단히 구현해보면 1 2 3 4 5 6 7 8 def quick_sort(S): if len(S) = b: return pivot_idx = random.randint(a, b) S[pivot_idx], S[a] = S[a], S[pivot_idx] pivot = S[a] left = a+1 right = b while left

선택정렬(Selection sort): 배열에서 아직 정렬되지 않은 부분의 원소들 중에서 최솟값을 선택하여 정렬된 부분의 바로 오른쪽 원소와 교환하는 정렬 알고리즘 1단계. 전체길이가 m일때 인덱스 0 ~ m-1 중에서 가장 작은 값을 찾아서 인덱스0의 값과 교환 2단계. 인덱스 1~m-1 중에서 가장 작은 값과 인덱스 1의 값을 교환 3단계. 이과정을 계속 반복하면 정렬된 리스트를 얻을 수 있다. 오름차순,내림차순 둘다 가능 선택정렬 파이썬 코드 1 2 3 4 5 6 7 def selection_sort(L): for i in range(0, len(L)): min_index = i for j in range(i, len(L)): if L[min_index] > L[j]: min_index = j L[..