기록일지

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 문제요약: N개의 문제는 모두 풀어야 한다. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다. 가능하면 쉬운 문제부터 풀어야 한다. 문제번호가 작을 수록 쉬운 문제이고 m개의 문제간의 우선순위(먼저 푸는것이 좋음) 이 주어질 때 문제를 풀어야하는 순서를 출력하시오. 난이도: 골드2 소요시간: 15분 제출횟수: 1회 코딩..

코딩테스트/그래프 이론 2023. 11. 3. 10:27

https://www.acmicpc.net/problem/1068 1068번: 트리 첫째 줄에 트리의 노드의 개수 N이 주어진다. N은 50보다 작거나 같은 자연수이다. 둘째 줄에는 0번 노드부터 N-1번 노드까지, 각 노드의 부모가 주어진다. 만약 부모가 없다면 (루트) -1이 주어진다 www.acmicpc.net 문제요약: 각 노드의 부모노드가 주어지고 지워질 노드가 하나 주어질 때 (그 지워지는 노드 포함 그 자식 노드들도 지워진다) , 리프 노드(자식이 없는 노드) 의 개수를 구하여라 난이도: 골드5 소요시간: 40분( 15분,5분,20분) 제출횟수: 2회 1차코드: import sys input = sys.stdin.readline n = int(input()) parent = list(map(..

코딩테스트/그래프 이론 2023. 10. 23. 10:58

강의 요약: 이코테 문제이며, 강의간 선수,후수과목이 존재하고 각 과목마다 수강까지의 최소시간이 있을때 수업당 수강까지 걸리는 최소시간을 구하시오. 이코테 난이도 3 소요시간: 28분 1차시도: from collections import deque n = int(input()) indegree = [0]*(n+1) graph_go = [[] for _ in range(n+1)] graph_back = [[] for _ in range(n+1)] cost = [0]*(n+1) for i in range(1,n+1): arr=list(map(int,input().split())) #들어야하는 시간은 일단 첫번째 숫자 cost[i] = arr[0] #맨앞은 시간 끝은 -1 for j in arr[1:-1]: ..

코딩테스트/그래프 이론 2023. 6. 14. 19:58

https://www.acmicpc.net/problem/2887 2887번: 행성 터널 첫째 줄에 행성의 개수 N이 주어진다. (1 ≤ N ≤ 100,000) 다음 N개 줄에는 각 행성의 x, y, z좌표가 주어진다. 좌표는 -109보다 크거나 같고, 109보다 작거나 같은 정수이다. 한 위치에 행성이 두 개 이 www.acmicpc.net 문제요약; 행성의 x,y,z좌표가 주어지고 각 행성간 거리는 서로의 좌표의 차이중 가장 짧은 것을 기준으로 한다. 모든 행성을 연결할 가장 짧은 엣지 합은? 플레5 소요시간: 30분 1차 시도: import sys input = sys.stdin.readline n = int(input()) arr = [] for i in range(n): x,y,z = map(i..

코딩테스트/그래프 이론 2023. 6. 9. 10:19

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 문제요약: 모든 도시들을 최소한의 cost로 연결후 두개의 대 도시로 분류한다. 골드4 소요시간: 14분 1차 접근(정답): 모든 길이연결되어있는 최소한의 cost이므로 바로 크루스칼을 떠올렸고, 마지막으로 추가된 마을의 cost를 빼면 가장적은 비용으로 큰 두개의 마을을 연결할 수 있다고 생각했다. import heapq as hp import sys inp..

코딩테스트/그래프 이론 2023. 6. 2. 11:01