# Coding (78) 썸네일형 리스트형 파이썬 입력 시간 줄이기 input = lambda: __import__('sys').stdin.readline().rstrip() 입력이 많은 문제의 경우 시간 초과가 뜰 수 있다. 위의 코드가 진짜 효과적으로 줄여준다. 일반적인 input()보다 빠르다. 특히 많은 데이터를 한 번에 입력받을 때 성능 차이가 크게 나온다. sys.stdin.readline().rstrip()을 매번 쓰지 않아도 되고, 간단히 input()처럼 사용할 수 있다. [백준 / 15809] 전국시대 - Python https://www.acmicpc.net/problem/15809 15809번: 전국시대 첫 번째 줄에 국가의 수를 나타내는 N과 기록의 수 M이 주어진다. (1 ≤ N, M ≤ 100,000) 두 번째 줄 부터 N개의 줄에 걸쳐 i번째 국가의 병력 Ai (1 ≤ i ≤ N)가 자연수로 주어진다. (1 ≤ Ai ≤ 10,000) 다 www.acmicpc.net Union-Find 알고리즘을 응용하여 풀 수 있는 문제다. conturies에 각 국의 전투력 또는 점령국(속국의 경우)을 적어놓은다. 전투력과 헷갈릴 수 있으므로, 속국인 경우에 점령국의 Index를 -1 을 곱한 음수 값으로 저장한다. 따라서 점령국의 경우 전투력이 나오고, 속국인 경우에는 해당 점령국의 인덱스가 저장되는 것이다. 따라서, .. [Python] 트리의 지름을 구하는 법 결론부터 말하면 트리의 지름은 임의의 한 점에서 가장 멀리 떨어져 있는 점(A)과, 해당 점(A)에서 부터 가장 멀리 떨어진 점(B) 사이의 거리(AB)이다. 즉, 한 점(n)으로 부터 DFS(n)으로 가장 먼 점(A)을 구하고, 해당 점(A)에서 DFS(A)로 가장 먼 점(B)과의 거리가 된다. 이제부터 이 이유에 대해서 생각해보자. 트리의 특징 중 사이클이 존재하지 않는다. 즉, 지나간 노드는 다시 방문할 수 없다. 이것을 기억하자. 트리는 어떤 점을 기준으로 잡아도 트리가 된다. 예를 들어보자. 위와 같은 트리가 있다고 가정해보자. 만약 3번 노드를 잡고 위로 올려서 다른 노드들이 데롱데롱 매달리게 된다고 생각해보면 아래와 같은 그림이 된다. 어느 노드를 잡고 아래로 내리게 되든지 트리와 같은 모양.. [백준 / 2132] 나무 위의 벌레 - Python https://www.acmicpc.net/problem/2132 2132번: 나무 위의 벌레 첫째 줄에는 트리의 정점의 개수를 나타내는 정수 n(1 ≤ n ≤ 10,000)이 주어진다. 다음 줄에는 차례로 1번, 2번, …, n번 정점에 매달려 있는 열매의 개수가 주어진다. 다음 n-1개의 줄에는 트리의 각 www.acmicpc.net 트리의 지름이란 트리를 양쪽으로 잡아당겼을 때 가장 긴 거리이다. 이 트리의 지름을 구하는 방법은 임의의 한점에서 가장 먼 점(A)을 구하고, 해당 점(A)에서 가장 먼 점(B)를 연결하는 길이(AB)가 가장 큰 길이이다. 이 특징을 이용해 해당 문제를 풀 수 있다. 주의해야 할 점은 길이가 같은 지름이 여러개 존재할 수 있으므로, 길이가 같은 것을 다 구해서 모두 구해.. [백준 / 1167] 트리의 지름 - Python https://www.acmicpc.net/problem/1167 1167번: 트리의 지름 트리가 입력으로 주어진다. 먼저 첫 번째 줄에서는 트리의 정점의 개수 V가 주어지고 (2 ≤ V ≤ 100,000)둘째 줄부터 V개의 줄에 걸쳐 간선의 정보가 다음과 같이 주어진다. 정점 번호는 1부터 V까지 www.acmicpc.net 트리의 지름은 임의의 한 점에서 가장 먼점(A)과, 그 점(A)와 가장 먼 점(B) 사이의 거리이다. 따라서 두번의 경로찾기(DFS나 BFS)로 해답을 찾을 수 있다. import sys from collections import deque V = int(sys.stdin.readline()) tree = {} for _ in range(V): line = list(map(int,.. [백준 / 1967] 트리의 지름 - Python https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n-1개의 줄에 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연 www.acmicpc.net 트리의 지름이란 두 점을 기준으로 길게 폈을 때 가장 길어지는 거리이다. 즉 기준이되는 두 점은 연결 노드가 한개다. 연결 노드가 한개인 점에서 다른 연결 노드가 한개인 점까지의 모든 길이를 비교해서 가장 긴 길이를 출력하면 된다. import sys from collections import deque N = int(sys.stdin.readline()) tree = {i: .. [백준 / 13913] 숨바꼭질 4 - Python https://www.acmicpc.net/problem/13913 13913번: 숨바꼭질 4 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 기존 숨바꼭질 문제에서 변형해왔다. 모든 경로를 list에 담아서 전달해줬더니 메모리 초과가 나온다. 따라서 해당 경로의 이전 값을 저장하는 리스트를 만들어줘서 역추적 했다. 2022.04.06 - [# Coding/# 백준] - [백준 / 1697] 숨바꼭질 - Python [백준 / 1697] 숨바꼭질 - Python https://www.acmicpc.net.. [백준 / 13549] 숨바꼭질 3 - Python https://www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 www.acmicpc.net 기존 숨바꼭질 문제에서 변형해왔다. 점프인 경우에만 time을 추가해주지 않고 진행하였다. 위치가 0인 경우에는 0 * 2가 무한으로 돌 수 있으므로 0인 경우는 점프를 계산해주지 않는다. 2022.04.06 - [# Coding/# 백준] - [백준 / 1697] 숨바꼭질 - Python [백준 / 1697] 숨바꼭질 - Python https://www.acm.. 이전 1 2 3 4 ··· 10 다음
