본문 바로가기

파이썬127

[Python] 백준 2931번 : 가스관 https://www.acmicpc.net/problem/2931 2931번: 가스관 www.acmicpc.net 💡 문제 풀이 구현 문제이다. 문제의 조건만 맞춰서 풀어주면 된다. 중요한 조건은 다음과 같다. 무조건 답이 존재한다. 가스의 흐름이 유일하다. M과 Z에는 단 하나의 파이프와 연결되어있다. 무조건 하나의 파이프만 문제가 있다. 위 조건들에 따라서 우리는 파이프만 확인해주면 된다. 내 풀이의 사고 과정은 다음과 같다. 2차원 배열을 돌면서 파이프만 확인한다. 확인하는 파이프 모양에 맞게 파이프들이 연결되어있는지 체크한다. 단 하나의 파이프만 문제가 있으므로 연결되어있지 않는 파이프를 확인하면 바로 반복을 종료해준다. 길이 4의 배열에 문제가 있는 파이프 근처 상, 좌, 우, 하 순서로 파이프.. 2022. 8. 25.
[Python] 백준 14698번 : 전생했더니 슬라임 연구자였던 건에 대하여 (Hard) https://www.acmicpc.net/problem/14698 14698번: 전생했더니 슬라임 연구자였던 건에 대하여 (Hard) 각 테스트 케이스마다 슬라임을 끝까지 합성했을 때 청구될 비용의 최솟값을 1, 000, 000, 007로 나눈 나머지를 출력한다. 전기 에너지가 전혀 필요하지 않은 경우엔 1 을 출력한다. www.acmicpc.net 💡 문제 풀이 그리디 알고리즘 문제이다. 간단하게 작은 것부터 계산해주면 된다. 매번 정렬하면서 사용할 수 없으니까 우선순위 큐를 사용해주면 된다. ✔️ 느낀 점 heapq.heappop이 힙 구조로 되어있다는 가정 하에 0번 인덱스를 리턴하는 것인 것을 몰라서 heapify를 안 써서 계속 틀렸다. 이번 기회에 확실하게 잡고 가게 되었다. 💻 코드 imp.. 2022. 8. 24.
[Python] 백준 1647번 : 도시 분할 계획 https://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) 문제이다. 크루스칼 알고리즘을 통해서 해결했다. 문제 자체는 알고리즘을 이해하고 있으면 어렵지 않으나, 도시를 분리해야 해야 하므로 마지막에 추가된 비용을 빼줘야 한다. ✔️ 느낀 점 솔직히 마지막에 왜 빼줘야 하는지 이해를 할 수 없다. 크루스칼 알고리즘 자체를 이해하는 것이 목표라서 그냥 이해하지 않고 넘어갔다. 💻 .. 2022. 8. 21.
[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.

티스토리툴바