정리충의 정리노트

0. 문제 주소 https://www.acmicpc.net/problem/3948 3948번: 홍준이의 친위대 문제 홍준 왕국의 국왕 홍준이는 자신을 호위하는 N명의 친위대 병사가 있다. 병사들의 키는 모두 다르다. 홍준이는 그들을 일렬로 세울 때, 키 순서대로 세우는 것보다 맨 끝 두 병사를 제외한 � www.acmicpc.net 1. 풀이 처음엔 1차원 dp 배열로 점화식을 세워보려고 했으나 실패했다. 탑다운으로 현재 위치에 서려는 사람 기준 남아있는 사람들 중에 이 사람보다 키가 작은 사람 / 큰 사람의 수와 함께 다음에는 이 사람보다 큰 사람이 와야 하는지 여부를 파라미터로 사용한다. 2. 풀이 코드 * 유의할 점 #include #define ll long long using namespace ..

0. 문제 주소 https://www.acmicpc.net/problem/1222 1222번: 홍준 프로그래밍 대회 문제 홍준이는 프로그래밍 대회를 개최했다. 이 대회는 사람들이 팀을 이루어서 참가해야 하며, 팀원의 수는 홍준이가 정해준다. 팀원이 홍준이가 정한 값보다 부족하다면, 그 팀은 대회에 참여 www.acmicpc.net 1. 풀이 주어지는 수들의 범위가 작은 경우 그 수들을 인덱스로 이용하는 방법을 까먹지 말자 2. 풀이 코드 * 유의할 점 #include #define ll long long const int MAX = 2000005; using namespace std; int arr[MAX]; int main(){ #ifndef ONLINE_JUDGE freopen("input.txt",..

0. 문제 주소 https://www.acmicpc.net/problem/1507 1507번: 궁금한 민호 강호는 N개의 도시로 이루어진 나라에 살고 있다. 각 도시는 M개의 도로로 연결되어 있으며, 각 도로를 지날 때 필요한 시간이 존재한다. 도로는 잘 연결되어 있기 때문에, 도시 A에서 B로 이동할 www.acmicpc.net 1. 풀이 플로이드 워셜 알고리즘을 이용해서 i번 도시에서 j번 도시로 가는 최단거리가, 중간에 k번 도시를 거쳐서 가는 거리보다 클 경우 불가능, 같을 경우 i번 ~ j번을 직접적으로 잇는 도로는 필요가 없기 때문에 이를 저장해두고 순회가 끝나면 남은 도로들의 가중치만 더해주면 된다. 2. 풀이 코드 * 유의할 점 #include using namespace std; int ..

0. 문제 주소 https://www.acmicpc.net/problem/7469 7469번: K번째 수 문제 현정이는 자료 구조 프로젝트를 하고 있다. 다른 학생들은 프로젝트 주제로 스택, 큐와 같은 기본 자료 구조를 구현하는 주제를 선택했다. 하지만, 현정이는 새로운 자료 구조를 만들었다. www.acmicpc.net 1. 풀이 merge sort tree + binary search 쿼리마다 각 구간에서 어떤 수 보다 작은 수의 개수가 k-1개 인 것 중 가장 큰 수를 이분 탐색으로 찾는다. 2. 풀이 코드 * 유의할 점 #include const int INF = 1e9+7; const int NMAX = 100005; const int MAX = 1 =1;i--){ vector &c = tree..

0. 문제 주소 https://www.acmicpc.net/problem/9345 9345번: 디지털 비디오 디스크(DVDs) 문제 최근 유튜브와 같은 온라인 비디오 스트리밍 서비스 때문에 DVD 대여점들이 자취를 감추고 있다. 이러한 어려운 상황 속에서, DVD 대여점 주인들은 실낱같은 희망을 잡고자 인기있는 N개의 DV www.acmicpc.net 1. 풀이 "선반 A번부터 선반 B번까지 A번 ~ B번 dvd가 순서에 상관없이 모두 꽂혀있는 경우" "선반 A번부터 선반 B번까지 가장 작은 dvd 번호가 A, 가장 큰 dvd 번호가 B인 경우" 2. 풀이 코드 * 유의할 점 #include const int INF = 1e9+7; const int NMAX = 100005; const int MAX =..

0. 문제 주소 https://www.acmicpc.net/problem/3392 3392번: 화성 지도 문제 2051년, 야심차게 발사한 화성탐사선 성화가 탐사한 곳의 화성 지도를 N개 보냈다. 화성탐사선의 성공에 의기양양해진 BaSA(Baekjoon Space Agency)는 야심찬 계획을 발표했다. 화성 전체 지도를 만� www.acmicpc.net 1. 풀이 스위핑 풀이는 쉽게 이해가 갔다. 문제는 지금까지 유효한 y 좌표를, 즉 0번 이상 덮여져 있는 y 좌표가 얼마나 있는지를 알아야 하는데 update도 구간으로 주어져서 처음에는 lazy propagation을 생각했었다. 이 경우 lazy 배열을 이용한 느린 전파 ~ 0보다 큰 좌표의 개수의 합 연산 사이에서 구현이 어려워졌다. 그래서 구글..

0. 문제 주소 https://www.acmicpc.net/problem/1701 1701번: Cubeditor 문제 Cubelover는 프로그래밍 언어 Whitespace의 코딩을 도와주는 언어인 Cubelang을 만들었다. Cubelang을 이용해 코딩을 하다보니, 점점 이 언어에 맞는 새로운 에디터가 필요하게 되었다. 오랜 시간 고�� www.acmicpc.net 1. 풀이 KMP 알고리즘에서 사용하는 fail 함수를 이용하는 문제 2번 이상은 2번만 나와도 된다는 얘기고, 접두사와 접미사가 같다는 얘기는 동일한 부분 문자열이 2번 나온다는 것과 같다. 처음엔 가능한 모든 부분 문자열에 대해 fail 배열을 만들어서 최댓값을 찾게 했는데 TLE를 받았다. 당연히 N^3이라 터진다. 생각해보니까 양 ..

0. 문제 주소 https://www.acmicpc.net/problem/11495 11495번: 격자 0 만들기 문제 음수가 아닌 정수들의 격자가 주어진다. 당신은 이 격자에 다음 연산을 행할 수 있다. 1. 격자에서 가로 또는 세로로 인접한 정수 2개를 고른다. 2. 각 정수가 양수일 때 1 감소시킨다. 다음 그림은 총 4개의 연속한 연산을 2*2 격자에 가해서 모든 정수를 0으로 만든 과정을 보여준다. 위 예제에서는 모든 정수를 0으로 만들기 위해 4번의 연산을 행했다. 이보다 적은 횟수의 연산으로는 모든 정수를 0으로 만들 수 없다는 것을 쉽게 알 수 있다. www.acmicpc.net 1. 풀이 flow가 어려운 이유는 모델링이 문제 풀이의 90%를 넘게 차지하는데 그걸 하기가 어렵기 때문인 것..

0. 문제 주소 https://www.acmicpc.net/problem/11281 11281번: 2-SAT - 4 첫째 줄에 변수의 개수 N (1 ≤ N ≤ 10,000)과 절의 개수 M (1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에는 절이 주어진다. 절은 두 정수 i와 j (1 ≤ |i|, |j| ≤ N)로 이루어져 있으며, i와 j가 양수인 경우에는 각각 \(x_i\), \(x_j\)를 나타내고, 음수인 경우에는 \(\lnot x_{-i}\), \(\lnot x_{-j}\)를 나타낸다. www.acmicpc.net 1. 풀이 2-CNF(Conjunctive Normal Form)의 정의 : OR 연산만으로 연결된 괄호 단위(절, closure)들의 AND 연산만으로 이루어진 ..

0. 문제 주소 https://www.acmicpc.net/problem/2150 2150번: Strongly Connected Component 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이다. 이때 방향은 A->B가 된다. www.acmicpc.net 1. 풀이 단절점 알고리즘과 매우 유사. dfs ordering을 하면서, 자신과 자신의 자손들이 갈 수 있는 가장 작은 order가 자신이라면, 그 점 + 그 점의 자손들은 하나의 SCC를 이룬다. 물론 모든 자..

0. 문제 주소 https://www.acmicpc.net/problem/10167 10167번: 금광 첫 줄에는 금광들의 개수 N (1 ≤ N ≤ 3,000)이 주어진다. 이어지는 N개의 줄 각각에는 금광의 좌표 (x,y)를 나타내는 음이 아닌 두 정수 x와 y(0 ≤ x,y ≤ 109), 그리고 금광을 개발하면 얻게 되는 이익 또는 손해를 나타내는 정수 w(-109 ≤ w ≤ 109)가 주어진다. 금광의 좌표는 모두 서로 다르며 w > 0인 금광은 적어도 하나 존재한다. www.acmicpc.net 1. 풀이 1. 좌표의 범위때문에 좌표 압축을 해주어야 한다. 지금까지는 좌표 압축을 너무 원시적으로 했는데, 좋은 테크닉을 찾아서 주워왔다. x좌표, y좌표를 각각 따로 xco, yco 벡터에 저장해둔 ..

0. 문제 주소 https://www.acmicpc.net/problem/9938 9938번: 방 청소 문제 은기는 술병 N개(1부터 N까지 번호가 매겨져 있다)와 서랍 L개(1부터 L까지 번호가 매겨져 있다)를 가지고 있다. 술병은 은기의 방 바닥에 흩어져 있고, 어린이날을 맞이해 방 청소를 하려고 한다. 서랍에는 술병이 하나 들어갈 수 있다. 나중에 원하는 술을 빠르게 찾을 수 있게 하기 위해 은기는 각각의 술병이 들어갈 수 있는 서랍의 번호 Ai와 Bi를 공책에 적어 놓았다. 은기는 술병을 1번부터 N번까지 순서대로 정리할 것이고, 각각의 술병에 대 www.acmicpc.net 1. 풀이 분리 집합 문제인 걸 몰랐으면 절대 못 풀었을 것 같다. 사실 알고도 엄청 오래 걸렸다. 1. 한 번 채워진 서..

0. 문제 주소 https://www.acmicpc.net/problem/2532 2532번: 먹이사슬 1부터 N까지 번호가 붙여져 있는 N마리 서로 다른 동물이 있다. 모든 동물은 동일한 하나의 수평선 상에서 연속된 구간 내에서 활동한다. 이 구간을 그 동물의 활동영역이라 한다. 동물의 활동영역은 구간의 왼쪽 위치와 오른쪽 위치 쌍으로 나타낸다. 예를 들어, 7마리 동물의 활동영역이 다음 그림과 같다고 하자. 각 동물의 활동 영역은 선분으로 나타내어져 있다. 아래에서 동물 1의 활동영역은 (2, 4), 동물 2의 활동영역은 (6, 10), ..., 동물 www.acmicpc.net 1. 풀이 LIS 응용 문제. 원소간 크기 비교의 정의가 기존과 다르기 때문에 새로 정의해주어야 한다. 조건 1: x1 <..

0. 문제 주소 https://www.acmicpc.net/problem/10217 10217번: KCM Travel 각고의 노력 끝에 찬민이는 2014 Google Code Jam World Finals에 진출하게 되었다. 구글에서 온 초대장을 받고 기뻐했던 것도 잠시, 찬찬히 읽어보던 찬민이는 중요한 사실을 알아차렸다. 최근의 대세에 힘입어 구글 역시 대기업답게 비용 감축에 열을 내고 있었던 것이다. 초대장 내용에 의하면 구글은 찬민에게 최대 M원까지의 비용만을 여행비로써 부담해주겠다고 한다. 인천에서 LA행 직항 한 번 끊어주는게 그렇게 힘드냐고 따지고도 싶었지만, www.acmicpc.net 1. 풀이 DP가 어느 문제랑 안 어울리겠냐만은, 다익스트라 문제들을 파면서 DP랑 궁합이 너무 잘 맞는 ..

0. 문제 주소 https://www.acmicpc.net/problem/1162 1162번: 도로포장 문제 준영이는 매일 서울에서 포천까지 출퇴근을 한다. 하지만 잠이 많은 준영이는 늦잠을 자 포천에 늦게 도착하기 일쑤다. 돈이 많은 준영이는 고민 끝에 K개의 도로를 포장하여 서울에서 포천까지 가는 시간을 단축하려 한다. 문제는 N개의 도시가 주어지고 그 사이 도로와 이 도로를 통과할 때 걸리는 시간이 주어졌을 때 최소 시간이 걸리도록 하는 K개의 이하의 도로를 포장하는 것이다. 도로는 이미 있는 도로만 포장할 수 있고, 포장하게 되면 도로를 지나는데 걸 www.acmicpc.net 1. 풀이 다익스트라 응용 문제. 1차원 배열이었던 dist를 확장해서 dist[i][j] = (i번째 노드까지 도로를 ..

0. 문제 주소 https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 출발 도시의 번호가 주어지고 그 다음에는 도착 도시의 번호, 그리고 마지막에는 이 도로를 지나는데 걸리는 시간이 주어진다. 도로를 지나가는 시간은 10,000보다 작거나 같은 자연수이다. 그리고 m+3째 줄에는 지도를 그리는 사람들이 www.acmicpc.net 1. 풀이 위상 정렬 문제들을 풀다 보면 흔히 볼 수 있는 description이 보인다. 실제로 위상 정렬로 풀고 [PS..

0. 문제 주소 https://www.acmicpc.net/problem/9323 9323번: 무임승차 문제 상현이는 어떤 기밀 단체의 요원이다. 상현이는 매일 아침 기차를 타고 출근한다. 어느 날 출근을 하던 상현이는 무언가 불합리하다는 것을 알아챘다. 상현이는 매일 요금을 내고 기차를 타지만, 실제로 승무원이 티켓을 확인하는 경우는 드물었기 때문이다. 결국 몇 년에 걸쳐, 상현이는 각 기차마다 어느 정도의 확률로 티켓을 확인받게 되는지에 대한 정보를 모두 작성하는 데 성공했다. 하지만 무임승차 벌금은 일반적으로 실제 요금보다 많기 때문에, 상현이는 모든 www.acmicpc.net 1. 풀이 아래 문장이 굉장히 중요하다. 기차 티켓은 기본 s원에 출발지 A와 도착지 B 사이의 최단거리에 비례하여 1 ..

0. 문제 주소 https://www.acmicpc.net/problem/1967 1967번: 트리의 지름 파일의 첫 번째 줄은 노드의 개수 n(1 ≤ n ≤ 10,000)이다. 둘째 줄부터 n번째 줄까지 각 간선에 대한 정보가 들어온다. 간선에 대한 정보는 세 개의 정수로 이루어져 있다. 첫 번째 정수는 간선이 연결하는 두 노드 중 부모 노드의 번호를 나타내고, 두 번째 정수는 자식 노드를, 세 번째 정수는 간선의 가중치를 나타낸다. 간선에 대한 정보는 부모 노드의 번호가 작은 것이 먼저 입력되고, 부모 노드의 번호가 같으면 자식 노드의 번호가 작은 것이 먼 www.acmicpc.net 1. 풀이 1. 아무 점 u에서 가장 먼 거리에 있는 점 v를 구한다. 2. 점 v에서 가장 먼 거리에 있는 점 w를..

0. 문제 주소 https://www.acmicpc.net/problem/2982 2982번: 국왕의 방문 문제 지난주에 상그니 아라비아의 국왕 고둘라 창지즈 영사우드가 한국에 도착했다. 고둘라는 매우 중요한 사람이다. 따라서, 경찰은 그가 타고 있는 차량이 길에 진입했을 때, 그가 길에 있는 동안에 다른 차량이 들어올 수 없게 통제할 것이다. 하지만, 그가 진입하기 전부터 길에 있던 차량은 계속 있을 수 있다. 상근이는 오토바이 소년 승환이의 뒤를 이어 근처에서 피자를 트럭으로 배달하는 사람이다. 상근이는 교통 통제 때문에 배달을 정시에 하지 못해서 짤릴뻔했 www.acmicpc.net 1. 풀이 국왕이 방문하는 시간대를 pii 배열 forbid ( forbid[ i ][ j ] = pair( 시작 시..

0. 문제 주소 https://www.acmicpc.net/problem/2211 2211번: 네트워크 복구 첫째 줄에 두 정수 N, M이 주어진다. 다음 M개의 줄에는 회선의 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 컴퓨터와 B번 컴퓨터가 통신 시간이 C (1 ≤ C ≤ 10)인 회선으로 연결되어 있다는 의미이다. 컴퓨터들의 번호는 1부터 N까지의 정수이며, 1번 컴퓨터는 보안 시스템을 설치할 슈퍼컴퓨터이다. 모든 통신은 완전쌍방향 방식으로 이루어지기 때문에, 한 회선으로 연결된 두 컴퓨터는 어느 방향으로도 통신할 수 있다. www.acmicpc.net 1. 풀이 매우 국어 문제. 두 가지 조건을 보자. 해커가 다시 공격을 할 우려가 있기 때문에, 최소 개수의 회선만을 복구해야 한..

0. 문제 주소 https://www.acmicpc.net/problem/9370 9370번: 미확인 도착지 문제 (취익)B100 요원, 요란한 옷차림을 한 서커스 예술가 한 쌍이 한 도시의 거리들을 이동하고 있다. 너의 임무는 그들이 어디로 가고 있는지 알아내는 것이다. 우리가 알아낸 것은 그들이 s지점에서 출발했다는 것, 그리고 목적지 후보들 중 하나가 그들의 목적지라는 것이다. 그들이 급한 상황이기 때문에 목적지까지 우회하지 않고 최단거리로 갈 것이라 확신한다. 이상이다. (취익) 어휴! (요란한 옷차림을 했을지도 모를) 듀오가 어디에도 보이지 않는다. 다 www.acmicpc.net 1. 풀이 [PS/ShortestPath] - [BOJ] 5719: 거의 최단 경로에서 썼던 테크닉을 쓴다. S에서..

0. 문제 주소 https://www.acmicpc.net/problem/15480 15480번: LCA와 쿼리 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N-1개의 줄에는 트리 T의 간선 정보 u와 v가 주어지다. u와 v는 트리의 간선을 나타내는 두 정점이다. 다음 줄에는 쿼리의 개수 M(1 ≤ M ≤ 100,000)가 주어진다. 다음 M개의 줄에는 쿼리를 나타내는 r, u, v가 주어진다. www.acmicpc.net 1. 풀이 당연히 매번 루트를 재설정해가며 sparse table을 만들면 안 된다. 케이스 분류가 잘 안 돼서 구글링을 해봤는데 아래 링크가 가장 깔끔하게 정리해 둔 것 같다. https://cyberflower.github.io/2019/08..

0. 문제 주소 https://www.acmicpc.net/problem/2618 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5≤N≤1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1≤W≤1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄까지 사건이 발생된 위치가 한 줄에 하나씩 주어진다. 경찰차들은 이 사건들을 주어진 순서대로 처리해야 한다. 각 위치는 동서방향 도로 번호를 나타내는 정수와 남북방향 도로 번호를 나타내는 정수로 주어지며 두 정수 사이에는 빈칸이 하나 있다. 두 사건이 www.acmicpc.net 1. 풀이 메모이제이션 없이 풀려면 2^1000가지 경우를 다 봐야 한다. 사건이 W개 있을 때, 0번째 사건이 (1, 1)..

0. 문제 주소 https://www.acmicpc.net/problem/10714 10714번: 케이크 자르기 2 문제 JOI 군과 IOI 양은 쌍둥이 남매이다. JOI 군은 최근 과자 만들기에 푹 빠졌기 때문에, JOI 군은 오늘도 케이크를 만들어서 먹으려고 했지만, 막 구워진 참에 냄새를 맡고 온 IOI 양이 왔기 때문에 두 명이 케이크를 나누어 먹기로 했다. 케이크는 둥그런 모양을 하고 있다. 어느 점에서부터 직선으로 칼집을 넣어 케이크를 N 개의 조각으로 나눈 뒤, 각 조각마다 1부터 N 까지 반시계방향으로 번호를 매긴다. 즉, 1 ≦ i ≦ N에 대해, i www.acmicpc.net 1. 풀이 사선 dp 문제들과 유사하게, 구간을 고려하는 점은 비슷하지만, dp 테이블의 정의를 다르게 해야 ..

0. 문제 주소 https://www.acmicpc.net/problem/5719 5719번: 거의 최단 경로 문제 요즘 많은 자동차에서는 GPS 네비게이션 장비가 설치되어 있다. 네비게이션은 사용자가 입력한 출발점과 도착점 사이의 최단 경로를 검색해 준다. 하지만, 교통 상황을 고려하지 않고 최단 경로를 검색하는 경우에는 극심한 교통 정체를 경험할 수 있다. 상근이는 오직 자기 자신만 사용 가능한 네비게이션을 만들고 있다. 이 네비게이션은 절대로 최단 경로를 찾아주지 않는다. 항상 거의 최단 경로를 찾아준다. 거의 최단 경로란 최단 경로에 포함되지 않는 도로로만 www.acmicpc.net 1. 풀이 최단 경로가 여러개일 수 있고, 그 여러 최단 경로끼리도 간선을 공유할 수 있다. 풀이는 다음과 같다...

0. 문제 주소 https://www.acmicpc.net/problem/3860 3860번: 할로윈 묘지 문제 오늘은 할로윈이다. 상근이와 친구들은 할로윈을 기념하기 위해 묘지를 방문했다. 상근이와 친구들은 한 명씩 묘지로 들어가고, 혼자서 묘지의 출구를 찾아야 한다. 이제, 상근이의 차례가 돌아왔다. 상근이가 어렸을 적에 할머니는 상근이에게 할로윈 밤에 묘지에는 귀신 구멍이 나타난다고 말해주었다. 귀신 구멍으로 들어가면, 묘지의 다른 장소로 다시 나오게 된다. 이 구멍은 시간을 이동할 수 있는 구멍이다. 귀신 구멍에 떨어지면, 특정 시간이 지난 후(또는 이 www.acmicpc.net 1. 풀이 이 문제는 무조건 영어로 봐야 한다. 무조건이다. 제발 처음부터 영어로 보자. 한국어 번역에는 드러나지 않..

0. 문제 주소 https://www.acmicpc.net/problem/11400 11400번: 단절선 첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이며, 방향은 양방향이다. 그래프는 항상 연결되어 있으며, 같은 간선이 두 번 이상 들어오는 경우는 없다. 또, A와 B가 같은 경우도 없다. 그래프의 정점은 1부터 www.acmicpc.net 1. 풀이 [PS/BFS & DFS] - [BOJ] 11266: 단절점과 다른 점은 다음과 같다. 1. 루트 노드인지를 ..

0. 문제 주소 https://www.acmicpc.net/problem/11266 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이며, 방향은 양방향이다. 입력으로 주어지는 그래프는 연결 그래프가 아닐 수도 있다. www.acmicpc.net 1. 풀이 단절점이란, 제거했을 때 그래프가 둘 이상의 컴포넌트로 나뉘는 정점을 의미한다. DFS를 이용해 각 정점들을 돌면서, 방문 순서 번호를 order배열에 저장한다. 그리고 low라는 것을 정의하는데..

0. 문제 주소 https://www.acmicpc.net/problem/2887 2887번: 행성 터널 문제 때는 2040년, 이민혁은 우주에 자신만의 왕국을 만들었다. 왕국은 N개의 행성으로 이루어져 있다. 민혁이는 이 행성을 효율적으로 지배하기 위해서 행성을 연결하는 터널을 만들려고 한다. 행성은 3차원 좌표위의 한 점으로 생각하면 된다. 두 행성 A(xA, yA, zA)와 B(xB, yB, zB)를 터널로 연결할 때 드는 비용은 min(|xA-xB|, |yA-yB|, |zA-zB|)이다. 민혁이는 터널을 총 N-1개 건설해서 모든 행성이 서로 연결되게 www.acmicpc.net 1. 풀이 1. 모든 행성 연결, 2. 최소 비용 -> MST이다. 여기서 N이 10만이므로, 모든 간선을 다 고려한다..

0. 문제 주소 https://www.acmicpc.net/problem/3830 3830번: 교수님은 기다리지 않는다 문제 상근이는 매일 아침 실험실로 출근해서 샘플의 무게를 재는 일을 하고 있다. 상근이는 두 샘플을 고른 뒤, 저울을 이용해서 무게의 차이를 잰다. 교수님의 마음에 들기 위해서 매일 아침부터 무게를 재고 있지만, 가끔 교수님이 실험실에 들어와서 상근이에게 어떤 두 샘플의 무게의 차이를 물어보기도 한다. 이때, 상근이는 지금까지 잰 결과를 바탕으로 대답을 할 수도 있고, 못 할 수도 있다. 상근이는 결과를 출근한 첫 날부터 공책에 적어 두었다. 하지만, 엄 www.acmicpc.net 1. 풀이 처음엔 LCA를 생각했었는데, 트리 구조가 안나와서 다른 방법을 생각해보았다. [PS/Unio..