본문 바로가기

그래프17

TIL : Kruskal(크루스칼) 알고리즘 (9) 💻 알고리즘 📌 크루스칼 알고리즘 프림 알고리즘과 같이 대표적인 최소 신장 트리(MST)를 찾는 알고리즘이다. 이 알고리즘의 특징과 동작 원리는 다음과 같다. ✔️ 특징 확인하는 그래프가 무방향 그래프이고 가중치가 존재한다. 가장 비용이 작은 것부터 확인하기 때문에 그리디 알고리즘의 일종이다. 순환(Cycle)이 있는지 확인하기 위해서 Union-Find 알고리즘을 사용한다. ✔️ 동작 원리 입력받은 간선들을 cost을 기준으로 정렬한다. 가장 작은 비용을 가진 간선을 확인한다. 사이클이 안 만들어지면 추가하고 만들어지면 다음 간선을 확인한다. 간선의 개수가 정점 - 1 개가 될 때까지 반복한다. # find function def find(x): if x != parent[x]: parent[x] = .. 2022. 8. 21.
[Python] 백준 1613번 : 역사 https://www.acmicpc.net/problem/1613 1613번: 역사 첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. www.acmicpc.net 💡 문제 풀이 그래프 이론 중 플로이드-워셜 문제이다. 이 문제에서는 최소 거리를 따지는게 아니라 순서만 따지면 된다. 따라서, 두 사건 a, b에 대해서 a 다음에 b가 오는지만 따지면 되므로 배열에는 참거짓만 저장해준다. ✔️ 느낀 점 pypy로 제출해야 통과가 되서 다른 분의 코드를 확인해봤는데 전적으로 나와 코드가 유사해서 그냥 넘어가야겠다. 💻 코드 import sys input .. 2022. 8. 17.
[Python] 백준 11404번 : 플로이드 https://www.acmicpc.net/problem/11404 11404번: 플로이드 첫째 줄에 도시의 개수 n이 주어지고 둘째 줄에는 버스의 개수 m이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 버스의 출발 도시의 번호가 www.acmicpc.net 💡 문제 풀이 그래프 문제 중 플로이드-워샬 알고리즘 문제이다. 플로이드-워샬 알고리즘을 구현하면 된다. 입력값 중에 목적지가 같은 버스가 있어서 edge들을 입력받을 때 더 작은 값으로 최신화해야 한다. ✔️ 느낀 점 플로이드-워샬 알고리즘 자체는 어렵지 않지만 문제 조건인 "갈 수 없을 때 0으로 출력하라."와 "같은 목적지의 버스가 있음."을 놓쳐서 계속 틀려서 화가 났다 ^^. 문제를 잘 .. 2022. 8. 17.
[Python] 백준 1916번 : 최소비용 구하기 https://www.acmicpc.net/problem/1916 1916번: 최소비용 구하기 첫째 줄에 도시의 개수 N(1 ≤ N ≤ 1,000)이 주어지고 둘째 줄에는 버스의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 M+2줄까지 다음과 같은 버스의 정보가 주어진다. 먼저 처음에는 그 www.acmicpc.net 💡 문제 풀이 다익스트라 그래프 이론 문제이다. 기본적인 다익스트라 알고리즘을 구현하면 된다. ✔️ 느낀 점 💻 코드 import sys, heapq input = sys.stdin.readline INF = int(1e9) # 도시의 개수(vertex), 버스의 개수(edge) 입력 N = int(input()) M = int(input()) # 입력 받은 값 .. 2022. 8. 17.
[C++] 프로그래머스 : 위클리 챌린지 (9주차) https://programmers.co.kr/learn/courses/30/lessons/86971 코딩테스트 연습 - 9주차 9 [[1,3],[2,3],[3,4],[4,5],[4,6],[4,7],[7,8],[7,9]] 3 7 [[1,2],[2,7],[3,7],[3,4],[4,5],[6,7]] 1 programmers.co.kr 문제 풀이 노드의 최대 개수가 100개이므로 전부 탐색을 하면서 간선의 길이를 구해서 따지면 된다. BFS를 통해서 간선의 최대 길이를 따지고 STL::set을 이용해서 각 노드마다 연결된 노드를 저장해준다. 느낀 점 처음에는 전혀 접근하 지를 못해서 조금의 구글링으로 도움을 받았다. 그래프 관련된 문제를 좀 더 많이 풀어봐야 할 것 같다. 코드 #include #include.. 2021. 10. 10.

티스토리툴바