이동식 저장소

800문제 달성 기념. N개의 도시와 N-1개의 도로가 있다. 여기에서 도로망이 트리 형태임을 알 수 있다. 어떤 도시 A와 B를 연결하는 최단 경로는 A~LCA~B이다. 정답을 구하기 위해서는 이 경로에 속한 도로의 길이의 최댓값과 최솟값을 찾으면 된다. LCA를 O(logN)에 찾는 방법은 널리 알려져 있다. 따라서 우리가 할 일은 도로를 탐색하는 것이다. 그런데 도로가 최대 99999개네? 도로를 전부 탐색하면 O(N^2)이 되기 때문에 시간 제한에 걸릴 것 같다. 쿼리 1개당 O(logN) 안에 처리해야 할 것 같다. 답은 이미 나와 있다. LCA를 O(logN)에 구한 것처럼 도로도 O(logN)에 탐색하면 된다. LCA를 탐색할 때 "이 정점의 2^i번째 부모"를 찾은 것처럼, "이 정점부터 ..

Numpy는 수학 연산을 더 쉽고 빠르게 지원해 주는 Python 라이브러리입니다. Numpy는 내부의 많은 부분이 C로 작성되어 있기 때문에, Python 리스트 연산보다 빠른 속도를 자랑합니다. Python으로 회귀분석 등의 통계 작업을 하고자 한다면 Numpy를 꼭 알고 가도록 합시다. 저도 요즘 배우는 중입니다. Numpy는 외부 라이브러리입니다. 따라서 pip를 통해 먼저 설치해야 합니다. 다음의 커맨드를 입력하여 Numpy를 설치합시다. pip install numpy 위에서 썼듯이 외부 라이브러리인 Numpy를 사용하려면 먼저 import를 해야 합니다. 관례적으로 Numpy는 np라는 이름으로 줄여 씁니다. import numpy as np 저 역시 numpy 대신 np로 사용하도록 하겠습..