딥러닝 공부방

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

백준 11657번 타임머신 11657번: 타임머신 첫째 줄에 도시의 개수 N (1 ≤ N ≤ 500), 버스 노선의 개수 M (1 ≤ M ≤ 6,000)이 주어진다. 둘째 줄부터 M개의 줄에는 버스 노선의 정보 A, B, C (1 ≤ A, B ≤ N, -10,000 ≤ C ≤ 10,000)가 주어진다. www.acmicpc.net 파이썬 풀이 음의 간선이 존재하는 그래프 내에서 최단 경로를 찾는 문제입니다. 벨만-포드 알고리즘을 이용했습니다. # 최단 거리를 찾는 알고리즘 # 시간복잡도 O(VE) V: 정점 수, E: 간선 수 # 방향 그래프에서 음의 가중치를 지닌 간선이 존재할 때 사용 # 음의 순환이 있는 경우에는 최단 거리를 찾지 못함 # 작동 원리 # 시작 노드에 대해서 거리를 0으로 초기화, 나..

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

1753번 최단경로 www.acmicpc.net/problem/1753 1753번: 최단경로 첫째 줄에 정점의 개수 V와 간선의 개수 E가 주어진다. (1≤V≤20,000, 1≤E≤300,000) 모든 정점에는 1부터 V까지 번호가 매겨져 있다고 가정한다. 둘째 줄에는 시작 정점의 번호 K(1≤K≤V)가 주어진다. www.acmicpc.net 문제 파이썬 풀이 다익스트라 알고리즘을 활용하여 최단 경로를 찾습니다. 다익스트라 알고리즘은 1) 모든 가중치가 양수, 2) 방향 그래프 인 경우 활용할 수 있습니다. 가중치가 음수인 경우는 벨만포드 알고리즘을 사용합니다. import sys import collections import heapq sys.setrecursionlimit(10**6) input = ..

다익스트라 알고리즘(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 ..

9466번 텀 프로젝트 파이썬 풀이 그래프 내에 순환이 존재하면, 순환이 되는 부분 그래프에 속하는 정점이 한 팀을 이루는 문제입니다. 따라서 유향 그래프 내에 (1) 순환을 찾고, (2) 순환에 해당하는 정점들의 수 체크하여 풉니다. import sys sys.setrecursionlimit(10 ** 6) input = sys.stdin.readline K = int(input()) # test 수 def dfs(v): global result visited[v] = 1 # 방문한 정점 기록 traced.append(v) # 탐색 경로 저장 w = graph[v] # 다음 방문할 정점 if visited[w] == 1: # 방문 가능한 곳이 끝났는지 체크 if w in traced: # 탐색 경로에 ..

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

백준 1707번 이분 그래프 www.acmicpc.net/problem/1707 1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K(2≤K≤5)가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V(1≤V≤20,000)와 간선의 개수 www.acmicpc.net 문제 풀이 코드 1) dfs 풀이 import sys sys.setrecursionlimit(10 ** 6) input = sys.stdin.readline # dfs def dfs(v, group): visited[v] = group # 방문한 노드에 group 할당 for i in graph[v]: if visited[i] == 0: # 아직 안 가본 곳이면 방문 i..

이분 그래프 판별(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 그룹으로..