-
벨만 포드 알고리즘Algorithms in Python/notes 2021. 2. 15. 17:42
벨만 포드(Bellman Ford) 알고리즘 특정 노드에서 나머지 노드까지의 최단 거리를 찾아주는 알고리즘 • 다익스트라 알고리즘과 비슷하지만 음의 간선이 포함된 상황에서 사용할 수 있다. • 음수 간선의 순환을 감지할 수 있다. • 기본 시간 복잡도는 O(VE)로 다익스트라 알고리즘에 비해 느리다. 다음의 모든 상황에 적용 가능하다. • 모든 간선이 양수 인 경우 • 음수 간선이 있는 경우 - 음수 간선 순환은 없는 경우 - 음수 간선 순환이 있는 경우 벨만 포드 알고리즘 1. 출발 노드를 설정한다. 2. 최단 거리 테이블을 초기화 한다. 3. 다음의 과정을 N -1 번 반복한다. - 전체 간선 E개를 하나씩 확인한다. - 각 간선을 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다...
-
플로이드 워셜 알고리즘Algorithms in Python/notes 2021. 2. 14. 16:06
플로이드 워셜(Floyd-Warshall) 알고리즘 모든 지점에서 다른 모든 지점까지의 최단 경로를 모두 구해야 하는 경우 사용할 수 있는 알고리즘 • 노드의 개수를 N이라고 할 때, N번 만큼의 단계를 반복하며 '점화식에 맞게' 2차원 리스트를 갱신한다. • 각 단계에서는 해당 노드를 거쳐가는 경우를 고려한다. ex) 1번노드를 확인할 때는 1번 노드를 중간에 거쳐 지나가는 모든 경우를 고려한다. - A -> 1번 노드 -> B 의 비용 확인 후 최단거리 갱신 => 현재 확인하고 있는 노드를 제외하고, N - 1개의 노드 중에서 서로 다른 노드 (A, B) 쌍을 선택한다. 이후에 A -> 1번 노드 -> B로 가는 비용을 확인한 후에 최단 거리를 갱신한다. 다시말해 N-1P2개의 쌍을 단계마다 반복해서..
-
다익스트라 최단 경로 알고리즘Algorithms in Python/notes 2021. 2. 10. 20:12
다익스트라(Dijkstra) 최단 경로 알고리즘 그래프에서 여러 개의 노드가 있을 때, 특정 노드에서 출발하여 다른 노드로 가는 각각의 최단 경로를 구해주는 알고리즘 다익스트라 최단 경로 알고리즘 1. 출발 노드를 설정한다. 2. 최단 거리 테이블을 초기화한다. 3. 방문하지 않은 노드 중에서 최단 거리가 가장 짧은 노드를 선택한다. 4. 해당 노드를 거쳐 다른 노드로 가는 비용을 계산하여 최단 거리 테이블을 갱신한다. 5. 위 과정에서 3번과 4번을 반복한다. * 매번 가장 비용이 적은 노드를 선택해서 임의의 과정을 반복하기 때문에 그리디 알고리즘이다. * 각 노드에 대한 현재까지의 최단 거리 정보를 1차원 리스트에 저장하며 계속 갱신해나간다. * 한 단계당 하나의 노드에 대한 최단 거리를 확실히 찾는..
-
위상 정렬Algorithms in Python/notes 2021. 2. 7. 08:40
위상 정렬(Topology Sort) 위상 정렬은 순서가 정해져 잇는 일련의 작업을 차례때로 수행해야 할 때 사용할 수 있는 알고리즘이다. 방향 그래프의 모든 노드를 '방향성에 거스르지 않도록 순서대로 나열하는 것이다. 위상 정렬 알고리즘 1. 진입차수가 0인 노드를 큐에 넣는다 2. 큐가 빌 때까지 다음의 과정을 반복한다. - 큐에서 원소를 꺼내 해당 노드에서 출발하는 간선을 그래프에서 제거한다. - 새롭게 진입차수가 0이 된 노드를 큐에 넣는다. * 진입차수가 0인 것이 없으면(큐가 빈 경우) 사이클을 포함한 것으로 해가 존재하지 않는다. * 한 특정 지접에서 2개 이상의 노드가 큐에 한꺼번에 들어갈 때는, 정렬 결과가 여러가지라는 의미이다. • 위상 정렬 소스코드 from collections im..
-
크루스칼 알고리즘Algorithms in Python/notes 2021. 2. 7. 08:35
크루스칼(Kruskal) 알고리즘 Spanning Tree 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프 MST (Minimum Spanning Tree) 최소 스패닝 트리 가중치 그래프의 스패닝 트리들 중에서 에지들의 가중치의 합이 최소인 스패닝 트리 '임의의 두 집에 대하여 가로등이 켜진 도로만으로도 오갈 수 있도록' '임의의 두 집 사이에 경로가 항상 존재하면서 길의 유지비의 합을 최소로' 크루스칼 알고리즘 1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다. 2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다. - 사이클이 발생하지 않는 경우 최소 스패닝 트리에 포함시킨다. - 사이클이 발생하는 경우 최소 스패닝 트리에 포함시키지 않는다..
-
Union-Find 알고리즘Algorithms in Python/notes 2021. 2. 7. 08:30
Union-Find (서로소 집합) 자료구조 서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 • union(합집합) 연산 : 2개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 • find(찾기) 연산 : 특정한 원소가 속한 집합이 어떤 집합인지 알려주는 연산 Union-Find 알고리즘 1. union(합집합) 연산을 확인하여, 서로 연결된 두 노드 A, B를 확인한다. - A와 B의 루트 노드 A', B'를 각각 찾는다. - A'를 B'의 부모 노드로 설정한다. (B'가 A'를 가리키도록 한다.) 2. 모든 union(합집합) 연산을 처리할 때까지 1번 과정을 반복한다. * 일반적으로 더 번호가 작은 원소가 부모 노드(작은 원소를 가르킴)가 되도록 구현하는 경우가 많다. ..
-
DFS / BFSAlgorithms in Python/notes 2021. 1. 29. 15:46
DFS (Depth-First-Search: 깊이 우선 탐색) 알고리즘 스택을 이용한 DFS 동작 방식 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다. 2의 과정을 더 이상 수행할 수 없을 때까지 반복한다. * 스택 대신 재귀 함수를 이용해서 구현할 수 있다. • 인접 리스트로 표현된 그래프에 대한 dfs 소스코드 # 인접 리스트로 표현된 그래프에 대한 dfs # V: 정점 개수, E: 간선 개수 def dfs(v): # 현재 노드를 방문 처리 visited[v] = True print(v, end=' ') # 현재 노드와 연결된 ..
-
이진 탐색, bisect 라이브러리Algorithms in Python/notes 2021. 1. 21. 23:25
이진 탐색 (Binary Search) 데이터가 정렬되어있을 때, 탐색 범위를 반으로 줄여가며 데이터를 빠르게 탐색하는 방법이다. - 시작점, 끝점, 중간점을 이용한다. - 중간점을 이용해서 탐색 범위를 줄여나간다. • 재귀 함수로 구현한 이진 탐색 소스코드 def binary_search(arr, target, start, end): if start > end: return None mid = (start + end) // 2 # 찾은 경우 인덱스 반환 if arr[mid] == target: return mid # 중간값보다 target이 작은 경우 왼쪽 부분 확인 elif arr[mid] > target: return binary_search(arr, target, start, mid - 1) # ..