알고리즘135 [Python] 백준 6497번 : 전력난 https://www.acmicpc.net/problem/6497 6497번: 전력난 성진이는 한 도시의 시장인데 거지라서 전력난에 끙끙댄다. 그래서 모든 길마다 원래 켜져 있던 가로등 중 일부를 소등하기로 하였다. 길의 가로등을 켜 두면 하루에 길의 미터 수만큼 돈이 들 www.acmicpc.net 💡 문제 풀이 최소 신장 트리 (MST)에 관한 문제이다. 크루스칼 알고리즘을 이용해서 해결했다. 잘 읽어봐야하는 점은 문제에서 출력해야 하는 값은 최소 신장 트리의 비용이 아닌, 가로등의 불을 끔으로써 아낀 비용을 출력해야한다. ✔️ 느낀 점 문제가 요구하는 점을 제대로 안 읽어서 틀렸을 때 너무나도 당황했다. 💻 코드 import sys input = sys.stdin.readline def find(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. TIL : 플로이드-워샬(Floyd-Warshall) 알고리즘 (8) 💻 알고리즘 📌 플로이드-워샬 알고리즘이란? 그래프 이론 중 하나로 다익스트라 알고리즘과 비슷하게 노드와 노드 사이의 최단거리를 구하는 알고리즘이다. 이 알고리즘의 특징과 동작 원리는 다음과 같다. ✔️ 특징 모든 노드 간의 최단거리를 구한다. 따라서 2차원의 공간이 필요하다. 음의 비용을 가지는 그래프에서도 사용할 수 있다. O(n^3)의 시간복잡도를 가진다. (3중 반복문) 다이나믹 프로그래밍의 성질을 가진다. ✔️ 동작 원리 거쳐 가는 노드를 기준으로 알고리즘이 수행한다. a → b의 비용과 a → k → b의 비용을 비교해서 더 작은 비용으로 최신화한다. INF = int(1e9) # 정점과 간선 개수 입력 vertex, edge = map(int, input().split()) # 그래프 초기화.. 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. [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 💡 문제 풀이 그래프 탐색 문제이다. BFS와 다익스트라 알고리즘 2가지로 해결할 수 있다. 출발지점부터 큐에 넣고 가중치를 계산해주면 된다. ✔️ 느낀 점 코드를 짜다보니 어쩌다 보니 BFS로 구현했다. 💻 코드 import sys from collections import deque input = sys.stdin.rea.. 2022. 8. 16. 이전 1 ··· 7 8 9 10 11 12 13 ··· 23 다음
