python (68) 썸네일형 리스트형 파이썬 입력 시간 줄이기 input = lambda: __import__('sys').stdin.readline().rstrip() 입력이 많은 문제의 경우 시간 초과가 뜰 수 있다. 위의 코드가 진짜 효과적으로 줄여준다. 일반적인 input()보다 빠르다. 특히 많은 데이터를 한 번에 입력받을 때 성능 차이가 크게 나온다. sys.stdin.readline().rstrip()을 매번 쓰지 않아도 되고, 간단히 input()처럼 사용할 수 있다. [Numpy] Numpy, Pandas, Matplotlib 버전 문제 문제 발생 이전 포스트에 올렸던 것처럼 아래와 같은 경고가 나왔다. module 'numpy' has no attribute 'object', 'bool', 'typeDict'. 이전에는 야매(?)로 해결했는데 이번에는 근본적인 해결책을 찾은 것 같다. 문제 발생 원인은 numpy의 버전이 업데이트 되면서 변수명이 달라지게 되면서 다른 모듈에서 numpy의 이전 변수를 호출하여 위와같은 메시지가 발생한 것이다. 즉, numpy와 기타 모듈의 버전을 낮춰주면 되는 것이다. numpy 1.21.0 릴리즈 노트를 확인하면 해당 변경에 대한 메시지를 확인할 수 있다. 따라서 1.21.0의 이전버전을 사용하면 해당 에러는 발생하지 않을 것이다. numpy .. [파이썬 시간 초과] try , except가 은근 시간을 잡아먹는다 copy. deepcopy()보다 슬라이싱이 훨씬 빨르다 pop을 많이하는 경우 list보다 deqeu가 더 빠르다 [백준 / 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: .. 이전 1 2 3 4 ··· 9 다음
