딥러닝 공부방

프림 알고리즘(Prim Algorithm) 오늘은 프림 알고리즘에 대해 공부했습니다. 프림 알고리즘은 주어진 무방향 그래프내에서 MST를 찾는 알고리즘입니다. 프림 알고리즘은 다익스트라 알고리즘과 거의 유사하다고 생각합니다. 차이점은 프림 알고리즘은 인접 간선을 추출하여 우선순위 큐에 삽입할 때, 순환이 발생하면 안되므로 방문한 노드인지 확인을 하고 우선순위 큐에 삽입을 합니다. 파이썬 코드 import heapq import collections import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline n, m = map(int,input().split()) # 노드 수, 간선 수 graph = collections.defaultdict(l..

크루스컬 알고리즘(Kruskal Algorithm) 가중치가 있는 무방향 그래프를 최소 신장 트리로 만드는 알고리즘입니다. 최소 신장 트리는 가중치가 최소인 순환이 없는 무방향 그래프 입니다. 순환이 없으므로 간선 수는 정점 수 - 1이 됩니다. 크루스컬 알고리즘은 Greedy Algorithm에 속하며, 매 번 순환이 되지 않도록 가중치가 가장 적은 다음 간선을 선택합니다. 시잔복잡도 O(ElogN) 작동 원리 (1) 간선을 가중치를 기준으로 정렬합니다. (2) 가장 가중치가 작은 간선(u, v)을 선택합니다. (3) union find 알고리즘을 통해 u와 v를 병합합니다. (4) union find 알고리즘은 각 정점을 분리 집합으로 만들고 서로 다른 집합에 속해있는 정점을 하나의 집합으로 병합합니..

Union-Find 알고리즘 union-find 알고리즘은 무방향 그래프를 순환이 없는 그래프로 만들기 위해 사용합니다. find 함수로 해당 노드의 루트 노드를 찾습니다. union 함수로 두 노드의 루트 노드가 다르다면, 두 노드가 포함되어 있는 집합을 하나로 결합합니다. 만약, 루트 노드가 동일하다면 두 노드가 동일한 집합에 있는 것으로 판단하여 union 연산을 수행하지 않습니다. 파이썬 코드 # union-find 알고리즘은 무방향 그래프를 순환이 없는 그래프로 만들기 위해 사용합니다. # find 함수로 해당 노드의 루트 노드를 찾습니다. # union 함수로 두 노드의 루트 노드가 다르다면, 두 노드가 포함되어 있는 집합을 하나로 결합합니다. # 만약, 루트 노드가 동일하다면 두 노드가 동일..

벨만-포드 알고리즘(Bellman-Ford Algorithm) 최단 거리를 찾는 알고리즘 시간복잡도 O(VE) V: 정점 수, E: 간선 수 방향 그래프에서 음의 가중치를 지닌 간선이 존재할 때 사용 음의 순환이 있는 경우에는 최단 거리를 찾지 못함 작동 원리 시작 노드에 대해서 거리를 0으로 초기화, 나머지 노드는 거리를 무한으로 설정 정점 수(n) -1 만큼 다음 과정을 반복 매 반복 마다 모든 간선 확인 현재 간선을 거쳐서 다른 노드로 이동하는 거리가 더 짧은 경우, 거리 정보 갱신 n-1번 반복 이후, n번째 반복에서도 거리 값이 갱신된다면 음수 순환이 존재 다익스트라와의 차이점은 매 반복마다 모든 간선을 확인한다는 것입니다. 다익스트라는 방문하지 않는 노드 중에서 최단 거리가 가장 가까운 노드만..

다익스트라 알고리즘(Dijkstra Algorithm) 간선 길이가 양의 정수인 그래프에서 최단 거리를 계산 간선 길이를 고려하여 노드에 순위를 매기고자, 일반적인 큐 대신에 우선순위 큐를 사용하는 것을 말고는 BFS와 동일 시간 복잡도는 우선 순위 큐 구현 방법에 달려있다. 이진 히프 O((V+E)logV), 삽입과 삭제 O(logV), 최소값 추출 O(logV) 다익스트라 알고리즘은 시작점s부터 가장 가까운 노드u를 포함하여 그래프를 생성하고, 해당 노드u로 이동합니다. 그래프 밖에 있는 s와 가장 가까운 노드v를 그래프에 포함합니다. 이 과정을 반복합니다. 파이썬 코드 # 다익스트라 알고리즘 # 간선 길이가 양의 정수인 그래프에서 최단 거리를 계산 # 간선 길이를 고려하여 노드에 순위를 매기고자 일..

무방향 그래프에서 사이클 찾기 dfs를 수행하면서, 방문한 정점을 기록합니다. 방문한 정점을 또 방문하면 사이클이 존재합니다. 파이썬 코드 # 2) 무향 그래프에서 순환 판별 # 방문한 정점을 기록하면서, 방문한 정점을 또 방문하면 사이클이 존재 V, E = map(int,input().split()) visited = [0] * (V+1) # 방문한 정점 정보를 담을 stack 생성 graph = [[] for i in range(V+1)] # 빈 인접 리스트 그래프 생성 # 그래프 생성 for i in range(E): a, b = map(int,input().split()) # 간선 정보 받아오기 graph[a].append(b) graph[b].append(a) # dfs 탐색 함수 생성 def ..

유향 그래프에서 순환(cyclic) 판별 유향 그래프 내에 back edge가 존재하면, 순환이 존재합니다. dfs와 stack 2개를 활용하여 유향 그래프내에 순환 그래프가 존재하는지 확인할 수 있습니다. 작동 원리 (1) 2개의 stack을 생성합니다. (2) traced 스택에 dfs를 수행하면서 탐색한 경로 노드 를 저장합니다. (3) visited 스택에 방문한 노드들을 저장합니다. visited 스택은 가지치기가 목적입니다.(소요시간 감소). visited 내에 존재하는 노드는 탐색을 진행하지 않기 때문입니다. (4) 탐색을 마친 노드는 traced에서 제거합니다. (5) 만약, traced에 존재하는 노드를 또 방문하면 순환이 존재합니다. 파이썬 코드 stack 대신에 set 자료구조를 사용..

이분 그래프 판별(bipartite graph distinction) 무방향 그래프의 이분 그래프를 판별하는 방법은 1) dfs, 2) bfs 두 가지 방법이 존재합니다. dfs 작동 원리 (1) 정점을 방문하면서 각 정점으 1, -1 두 그룹으로 번갈아 지정합니다. (2) 이미 방문했던 정점을 발견할 시에, 현재 정점과의 그룹을 비교하여 동일한 그룹인 경우 False를 반환합니다. bfs 작동 원리 (1) 동일한 level에 존재하는 정점을 같은 그룹으로 지정합니다. (2) 이미 방문한 정점인 경우, 현재 정점과의 그룹과 비교하여 동일한 그룹이면 False를 반환합니다. dfs 코드 # bipartite graph distinction # 1) dfs # 정점을 방문하면서 각 정점을 1, -1 그룹으로..

코사라주 알고리즘(kosaraju's algorithm) dfs를 활용하여 그래프 내의 ssc를 찾는 알고리즘 시간 복잡도 O(V+E) 정방향 그래프에서 dfs를 실행하여 post가 높은 정점이 sCc의 source가 되고, 역방향 그래프에서 dfs를 실행하여 post가 높은 정점이 scc의 sink가 된다. 찾은 source와 sink를 묶어 scc를 생성한다. 작동 원리 (1) 방향 그래프 내에서 dfs를 실행하여, dfs 탐색을 마친 정점을 stack에 삽입한다. (2) 역방향 그래프를 생성한다. (3) stack에서 정점을 추출하여, 역방향 그래프에서 dfs를 실행한다. (4) 방문하는 정점을 scc 에 삽입한다. (5) 탐색이 종료되면, scc (6) stack에서 방문하지 않은 정점을 추출하여..

위상 정렬 순환이 없는 유향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는것 알고리즘 동작 원리 1. 진입 차수가 0인 노드를 queue에 삽입. 2. 큐에서 노드를 하나씩 꺼내면서 아래의 과정을 진행 꺼낸 노드의 간선을 그래프에서 제거 진입 차수가 0인 새로운 노드를 queue에 삽입 파이썬 코드 from collections import deque # 노드의 개수와 간선의 개수를 입력 받기 v, e = map(int, input().split()) # 진입차수 0으로 초기화 in_degree = [0] * (v+1) # 빈 인접리스트 그래프 생성 graph = [[] for i in range(v+1)] # 방향 그래프의 간선 정보 입력 받기 for i in range(e): a, ..