본문 바로가기
반응형

전체 글288

[Algorithm][Python]유니온-파인드(Union-Find) 알고리즘 + 코드 이번에는 유니온 파인드 알고리즘에 대해서 한 번 알아봅시다. 아직 학부생이던 시절에 저보다 먼저 알고리즘 공부를 하던 친구가 유니온 파인드 한 번 써보라고, 진짜 너무 편하다고 했던 기억이 나는데요. 그 때 저는 DFS/BFS도 모르던 시절이라 그런게 있구나 생각만 하고 넘겼습니다. 사실상 그런 일이 있었다는 것도 거의 잊고 지내다가 평소처럼 알고리즘 문제를 풀었는데 별로 런타임이 빠르지 않았고, 해당 문제가 어떤 태그가 있나 살펴보다가 분리 집합이라는 알고리즘으로 분류가 되어있어서 이걸 사용하면 좀 빨라지려나 싶어서 찾아봤던게 유니온 파인드와의 첫 만남이었네요. 사실 이게 유니온 파인드구나를 알았을 때는 약간의 당황과 겁이 났습니다. 저한테 유니온 파인드는 상당히 먼 얘기일거라고 생각하고 있었거든요. .. 2023. 8. 3.
[BOJ][Python]9370 풀이 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 www.acmicpc.net import heapq import sys ssr = sys.stdin.readline INF = 2000001 def dijkstra(start, end=None): h = [(0, start)] min_dist = [INF for _ in range(n+1)] min_dist[start] = 0 while h: cur_dist, cur_node = heapq.heappop(h) if cu.. 2023. 8. 3.
[BOJ][Python]1238 풀이 https://www.acmicpc.net/problem/1238 1238번: 파티 첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어 www.acmicpc.net import heapq import sys ssr = sys.stdin.readline INF = 1000001 def dijkstra(start, edges): time = [INF for _ in range(n+1)] time[start] = 0 h = [(0, start)] while h: cur_time, cur_node = heapq.heappop(h) if.. 2023. 8. 2.
[BOJ][Python]13549 풀이 https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net import heapq import sys ssr = sys.stdin.readline INF = 100001 def dijkstra(n, k): # -1, 1, *2 h = [(0, n)] time = [INF for _ in range(200001)] time[n] = 0 while h: cur_time, cur_node = heapq.heappop(h) .. 2023. 8. 1.
[Algorithm][Python]데이크스트라(Dijkstra) 최단 경로 알고리즘 + 코드 저를 가장 오랫동안 괴롭혔던 알고리즘 중에 하나인 데이크스트라 알고리즘에 대해서 정리를 해볼까합니다. 그 때의 헤매던 저와 비슷한 분들께 도움이 되면 좋겠네요. 데이크스트라(Dijkstra) 최단 경로 알고리즘 최단 경로라는 말에서 짐작할 수 있듯이 데이크스트라 알고리즘은 출발점에서 도착점까지 가장 빠르게 갈 수 있는 경로를 탐색하는 알고리즘입니다. 최단 경로를 구하는 알고리즘에는 대표적으로 데이크스트라, 플로이드-워셜, 벨만-포드, A*(에이 스타) 이렇게 네가지가 있으며 이번 포스팅에서는 데이크스트라 알고리즘에 대해서만 정리를 해보겠습니다. 알고리즘의 이름인 데이크스트라는 알고리즘의 고안자인 네덜란드의 컴퓨터과학자 에츠허르 데이크스트라(Edsger Dijkstra)의 이름을 따서 부르고 있습니다. 한.. 2023. 8. 1.
[BOJ][Python]1504 풀이 https://www.acmicpc.net/problem/1504 1504번: 특정한 최단 경로 첫째 줄에 정점의 개수 N과 간선의 개수 E가 주어진다. (2 ≤ N ≤ 800, 0 ≤ E ≤ 200,000) 둘째 줄부터 E개의 줄에 걸쳐서 세 개의 정수 a, b, c가 주어지는데, a번 정점에서 b번 정점까지 양방향 길이 존 www.acmicpc.net import heapq import sys ssr = sys.stdin.readline INF = 200000001 def dijkstra(start, end): h = [(0, start)] min_dist = [INF for _ in range(n+1)] min_dist[start] = 0 while h: cur_dist, cur_node = hea.. 2023. 8. 1.
[BOJ][Python]1753 풀이 https://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 import heapq import sys ssr = sys.stdin.readline INF = 3000001 def dijkstra(start): h = [(0, start)] dist[start] = 0 while h: cur_dist, cur_node = heapq.heappop(h) if cur_dist > dist[cur_node]: continue.. 2023. 8. 1.
[BOJ][Python]18352 풀이 https://www.acmicpc.net/problem/18352 18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net import heapq import sys ssr = sys.stdin.readline INF = 300001 def dijkstra(): while h: cur_dist, cur_node = heapq.heappop(h) if cur_dist > dist[cur_node]: continue for next_dist, nex.. 2023. 7. 31.
[BOJ][Python]1967 풀이 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net from collections import deque import sys ssr = sys.stdin.readline n = int(ssr()) adj_list = [[] for _ in range(n+1)] for _ in range(n-1): line = list(map(int, ssr().split())) adj_list[line[0]].append((line[1], li.. 2023. 7. 30.
[BOJ][Python]1167 풀이 https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net from collections import deque import sys ssr = sys.stdin.readline n = int(ssr()) adj_list = [[] for _ in range(n+1)] for _ in range(n): line = list(map(int, ssr().split())) for i in range(1, len(line), 2): if line[.. 2023. 7. 30.
반응형

티스토리툴바