딥러닝 공부방

1197번 최소 스패닝 트리 www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 파이썬 풀이 프림 알고리즘을 사용했습니다. # 프림 알고리즘은 다익스트라 알고리즘과 거의 유사하다고 생각합니다. # 차이점은 프림 알고리즘은 인접 간선을 추출하여 우선순위 큐에 삽입할 때, # 순환이 발생하면 안되므로 방문한 노드인지 확인을 하고 우선순위 큐에 삽입을 합니다. import heapq import collections im..

프림 알고리즘(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..

백준 1647번 도시 분할 계획 www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수N, 길의 개수M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 집 www.acmicpc.net 파이썬 코드 크루스컬 알고리즘을 사용하여 그래프를 MST로 만들었습니다. 또한 두 개의 집합으로 분리해야 하므로 MST의 간선 개수가 N-2가 될 때 중지되도록 구현했습니다. import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline N, M = map(int,input().spli..

백준 1922번 네트워크 연결 www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 파이썬 풀이 크루스컬 알고리즘으로 주어진 그래프를 MST로 만듭니다. MST의 총 가중치를 출력합니다. # 크루스컬 알고리즘 import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline N = int(input()) # 정점 수 입력 받기 M = int(input()) # 간선 수 입력 받기 parent = [0] * (N+1) # 루트 노드를 저장할 자료구조 rank = [0] * (N+1) # 정점의 rank..

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

백준 1717번 집합의 표현 www.acmicpc.net/problem/1717 1717번: 집합의 표현 첫째 줄에 n(1 ≤ n ≤ 1,000,000), m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. 합집합은 0 a b의 형태로 입력이 주어진다. 이는 www.acmicpc.net 파이썬 풀이 union-find 알고리즘을 사용하여 풀었습니다. import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline N, M = map(int,input().split()) parent = [0] * (N+1) # 부모 테이블 생성 for i in range(N+1): # 자..

1976번 여행가자 www.acmicpc.net/problem/1976 1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 파이썬 풀이 union-find 알고리즘으로 풀 수 있는 문제입니다. import sys sys.setrecursionlimit(10**6) input = sys.stdin.readline N = int(input()) # 노드 수 입력 받기 M = int(input()) # 정점 수 입력 받기 parent = [0] * (N+1) # 부모 테이블 초기화 # 부모 테이블 상에서 자기 자신을 ..

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번째 반복에서도 거리 값이 갱신된다면 음수 순환이 존재 다익스트라와의 차이점은 매 반복마다 모든 간선을 확인한다는 것입니다. 다익스트라는 방문하지 않는 노드 중에서 최단 거리가 가장 가까운 노드만..