Doby's Lab

https://www.acmicpc.net/problem/12867 12867번: N차원 여행 예제 2의 경우에 (0,0) -> (1,0) -> (1,1) -> (0,1) -> (0,0)으로 이동하게 되어서 (0, 0)을 두 번 방문하게 되고, 예제 3의 경우에는 (0,0,0) -> (1,0,0) -> (1,1,0) -> (1,1,1) -> (0,1,1) -> (0,0,1) 으로 방문하게 되어서 모 www.acmicpc.net Solved By: Coordinate Compression 차원의 크기 N은 [1, 1,000,000,000]으로 너무 큽니다. 크기가 1,000,000,000인 배열을 선언하기는 부담스러우니 차원(값) 압축을 시킵시다. 하지만, 문제는 중복된 좌표를 어떻게 알고 처리할지가 문제..

https://www.acmicpc.net/problem/2171 2171번: 직사각형의 개수 첫째 줄에 N이 주어진다. 다음 N개의 줄에는 각 점의 x, y좌표가 주어진다. 좌표의 범위는 -1,000,000,000 이상 1,000,000,000 이하이며, 두 점의 좌표가 같은 경우는 없다. www.acmicpc.net Solved By: set Brute-Force로 4중 for문으로 만들어서 시간 초과로 헤매고 있을 때, 이 풀이를 발견했는데 정말 충격입니다. (https://jason9319.tistory.com/385) 점들의 입력을 받으면서 set에서도 좌표의 입력을 받아냅니다. 그리고, 2중 for문 Brute-Force로 두 가지 점을 고릅니다. 이 두 가지 점은 서로 대각선 상에 위치해야 ..

https://www.acmicpc.net/problem/18869 18869번: 멀티버스 Ⅱ M개의 우주가 있고, 각 우주에는 1부터 N까지 번호가 매겨진 행성이 N개 있다. 행성의 크기를 알고 있을때, 균등한 우주의 쌍이 몇 개인지 구해보려고 한다. 구성이 같은데 순서만 다른 우주의 쌍 www.acmicpc.net Solved By: Coordinate Compression 여러 개의 우주 중 두 우주 쌍을 골랐을 때, 각 인덱스의 해당하는 두 행성의 크기의 순서가 같으면 cnt를 합니다. 모든 우주의 행성의 크기는 제각각이고, 한 우주 안에서 행성들의 크기 순서를 구해야 하기 때문에 Coordinate Compression을 사용하여 문제를 풀었습니다. #include #include #includ..

Coordinate Compression이란 1차원 직선상에 N개의 점(1 n; for(int i = 0; i > value; v.push_back(value); temp.push_back(value); } // 정렬이 되어있어야 unique 함수를 통해 중복된 값을 지울 수 있다. // unique함수는 중복된 값들은 전부 다 뒤로 보낸다. // 그리고, unique함수는 중복되는 값이 시작되는 index의 iterator를 반환하므로 // 해당 iterator부터 끝까지 지워버리면 temp에는 값의 순서들만 남게된다. sort(temp.begin(), temp.end()); temp.erase(unique(temp.begin(), temp.end()),..

https://www.acmicpc.net/problem/15481 15481번: 그래프와 MST 첫째 줄에 정점의 개수 N과 간선의 개수 M (2 ≤ N ≤ 200,000, N-1 ≤ M ≤ 200,000) 둘째 줄부터 M개의 줄에 간선의 정보 u, v, w가 주어진다. u와 v를 연결하는 간선의 가중치가 w라는 뜻이다. (1 ≤ u, v ≤ www.acmicpc.net Solved By: MST, LCA MST를 구합니다. 그리고, 주어진 Query Node 사이에 maxDist를 빼고, Query Edge의 w를 더하는 것이 이번 문제의 핵심입니다. 여기서 궁금한 점은 경로를 맘대로 빼고, 더하는 행위가 component가 나뉘지 않는지 걱정했지만 몇 개의 case를 그려보면 그렇지 않다는 것을 알..

https://www.acmicpc.net/problem/15480 15480번: LCA와 쿼리 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리 T의 간선 정보 u와 v가 주어지다. u와 v는 트리의 간선을 나타내는 두 정점이다. 다음 줄에는 쿼리의 개수 M( www.acmicpc.net Solved By: LCA 쿼리마다 루트를 r로 만들어서 parent와 level을 초기화시키는 것은 시간 초과가 납니다. 3가지 케이스로 나누어서 풀 수 있습니다. [root node를 1로 잡은 트리를 만들었을 때] u, v가 r의 자식 노드인 경우 u 혹은 v 중 하나만 r의 자식 노드인 경우 둘 다 r의 자식 노드가 아닌 경우 1번의 경우 lca(u, v)..

https://www.acmicpc.net/problem/23355 23355번: 공사 한국항공대학교는 $n$ 개의 건물로 이루어져 있으며, 두 건물을 잇는 여러 개의 도로가 존재한다. 결벽증이 있는 동원이는, 한번도 가지 않은 길을 무서워한다. 동원이는 항공대의 여러 도로들 www.acmicpc.net Solved By: LCA 첫 시작은 Sparse Table로 LCA를 구한다면 x와 y 사이 경로에 k의 존재를 알 수 없을 거 같아서 Sparse Table을 사용하지 않고 LCA를 짰다가 시간 초과를 받았습니다. 그렇다면 \(Sparse Table\)이 필요하다고 느끼는데 경로 사이에 k가 존재하는 법을 알 수가 없어서 구글의 도움을 받았습니다. 다음과 같은 성질을 가지고서 문제를 풀 수 있습니다...

https://www.acmicpc.net/problem/14675 14675번: 단절점과 단절선 프로그램의 입력은 표준 입력으로 받는다. 입력의 첫 줄에는 트리의 정점 개수 N이 주어진다. (2 ≤ N ≤ 100,000) 트리의 정점은 1번부터 n번까지 존재한다. 다음 줄부터 N-1개의 줄에 걸쳐 간선의 정 www.acmicpc.net Solved By: Articulation 방금 공부한 Articulation Point와 Edge를 사용해보았습니다. #include #include #include #include #define MAX 100001 using namespace std; int n, q; vector adj[MAX]; bool isCut[MAX]; int visitedOrder[MAX]..