Doby's Lab

https://www.acmicpc.net/problem/24602 24602번: Tree Hopping You are given a tree and a permutation of its vertices. It can be proven that for any tree and any pair of source/destination nodes, there is some permutation of the nodes where the first node is the source, the last node is the destination, and the distan www.acmicpc.net Solved By: LCA, Sparse Table 각 노드 사이의 거리 값을 담을 배열을 선언하는 방법을 사용하지 않..

https://www.acmicpc.net/problem/8927 8927번: Squares Your program is to read from standard input. The input consists of T test cases. The number of test cases T is given in the first line of the input. The first line of each test case contains an integer, n , the number of squares, where 2 ≤ n ≤ 100,000 www.acmicpc.net Solved By: Convex Hull, Rotating Calipers 좌표가 주어지고, w가 주어지면 사각형이 되게끔 a, b a + ..

https://www.acmicpc.net/problem/10254 10254번: 고속도로 n개의 도시를 가진 나라가 있다. 이 나라에서는 도시들 중 가장 먼 두 도시 사이에 직행 고속도로를 놓으려 한다. 고속도로는 시작점과 끝점이 아닌 다른 나라를 통과해도 된다. 즉, n개의 도시 www.acmicpc.net Solved By: Convex Hull, Rotating Calipers 최대 직경을 가지는 좌표를 구하는 문제입니다. Rotating Calipers를 가지고서 최대 직경을 갱신하며 최대 직경을 가지는 좌표 또한 갱신해주면서 코드를 작성하면 됩니다. #include #include #include #include #define ll long long // 10^10이 넘는 경우 있음 using..

https://www.acmicpc.net/problem/1310 1310번: 달리기 코스 첫째 줄에 기둥의 개수 N(1 ≤ N ≤ 100,000)이 주어지고, 이어서 N줄에 걸쳐 각 기둥의 좌표를 나타내는 정수 두 개가 주어진다. 좌표의 절댓값의 범위는 50,000을 넘을 수 없다. www.acmicpc.net Solved By: Convex Hull, Rotating Calipers 거리를 구하거나 CCW를 구하면서 int 범위를 넘는 경우가 생길 수 있으니 이 점을 유의하여 long long 타입으로 코드를 짜면 쉽게 풀리는 Rotating Calipers 문제였습니다. #include #include #include #include #define ll long long // 10^10이 넘는 경우..

https://www.acmicpc.net/problem/2049 2049번: 가장 먼 두 점 첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도 www.acmicpc.net Solved By: Convex Hull, Rotating Calipers 단순한 Rotating Calipers 문제였습니다. Rotating Calipers 문제를 처음 접할 때, 좋은 문제일 거 같습니다. 거리의 제곱을 구한다는 점만 인지하고 있으면 됩니다. #include #include #include #include #include #define ll lon..

https://www.acmicpc.net/problem/9240 9240번: 로버트 후드 첫째 줄에 로버트 후드가 발사한 화살의 수 C (2 ≤ C ≤ 100,000)가 주어진다. 다음 C개 줄에는 화살의 좌표가 주어진다. 좌표는 정수이고, 절댓값은 1,000을 넘지 않는다. www.acmicpc.net Solved By: Convex Hull, Rotating Calipers 처음으로 사용해본 Rotating Calipers 문제였습니다. Point 간의 계산을 간편화 하기 위해 Point operator를 따로 선언하였습니다. long double result = sqrt(distValue); 그리고, distValue가 long long type의 데이터인데 sqrt를 시키면 이때까지 long l..

https://www.acmicpc.net/problem/9344 9344번: 도로 어떤 나라에는 1부터 N까지 이름 붙여진 N개의 도시가 있다. 한 엔지니어는 모든 도시를 연결하는 도로를 건설하고자 한다. 즉, 모든 도시에 대해 항상 다른 어떤 도시로든 이동할 수 있어야 한다 www.acmicpc.net Solved By: MST, Kruskal Algorithm N개의 도시들 사이의 도로를 짓는 데에 필요한 비용들의 합이 최소가 되게끔 합니다. >> MST를 사용할 수 있습니다. MST가 만들어지는 과정에 p, q가 주어진다면 YES, 아니라면 NO를 출력합니다. #include #include #include #define MAX 10001 #define pii pair using namespace..

https://www.acmicpc.net/problem/14916 14916번: 거스름돈 첫째 줄에 거스름돈 액수 n(1 ≤ n ≤ 100,000)이 주어진다. www.acmicpc.net Solved By: Coin Change DP 처음으로 풀어본 DP, Coin Change 기법이었습니다. 자세한 설명은 코드에 주석으로 달아두었습니다. #include #define MAX 100001 using namespace std; int cache[MAX]; int main(){ int n; cin >> n; int coin[2] = {2, 5}; for(int d = 1; d