https://www.acmicpc.net/problem/20530 20530번: 양분 첫째 줄에 두 자연수 $N$, $Q$가 주어진다. 주어지는 그래프의 정점과 간선의 개수가 $N$개이며 쿼리가 $Q$개 주어진다는 것을 의미한다. 둘째 줄부터 $N$개의 줄에는 $i$번 간선이 연결하는 두 정점 www.acmicpc.net 그래프는 하나의 사이클이 존재하고 해당 사이클에 사이클이 아닌 그래프들이 붙어있는 형태가 된다. 그래서 사이클에 속한 어떤 정점과 연결되어 있는 사이클에 속하지 않는 정점들을 한 그룹으로 하고, 사이클에 속한 각각의 정점들은 다른 그룹으로 하여 그룹을 만들어서 같은 그룹일 때는 단순 경로의 수가 1개, 다른 그룹일 때는 단순 경로의 수가 2개인 것을 이용하여 문제를 해결했다. 사이클에..

https://www.acmicpc.net/problem/20119 20119번: 클레어와 물약 첫 번째 줄에는 세상에 존재하는 물약의 종류의 수 N (3 ≤ N ≤ 200,000) 과 클레어가 알고 있는 레시피의 개수 M (1 ≤ M ≤ 200,000) 이 주어진다. 다음 M개의 줄에는 각각의 줄마다 레시피의 정보 k www.acmicpc.net 위상 정렬을 사용해서 문제를 해결했다. 만들어지는 물약이 처음 발견된 것일 때만 만들어지는 물약을 큐에 넣는 것에 주의하였다. 코드 #include #include #include #include #include using namespace std; int n, m; vector adj[200005]; //[물약번호] -> 레시피 번호 vector recipe..

https://www.acmicpc.net/problem/15732 15732번: 도토리 숨기기 첫째 줄에 상자의 개수 N(1 ≤ N ≤ 1,000,000)과 규칙의 개수 K(1 ≤ K ≤ 10,000), 도토리의 개수 D(1 ≤ D ≤ 1,000,000,000)가 주어진다. 그 후 K개 줄에는 A, B, C(1 ≤ C ≤ A ≤ B ≤ N)가 주어지며 A번 상자부터 www.acmicpc.net 해당 위치까지의 도토리의 개수가 d개 이상인지 확인하는 이분 탐색을 이용해 문제를 해결했다. 코드 #include #include #include #include using namespace std; int n, k, d; vector rule; //mid위치까지의 도토리의 개수가 d개 이상인지 확인 bool C..

https://www.acmicpc.net/problem/17835 17835번: 면접보는 승범이네 첫째 줄에 도시의 수 N(2 ≤ N ≤ 100,000), 도로의 수 M(1 ≤ M ≤ 500,000), 면접장의 수 K(1 ≤ K ≤ N)가 공백을 두고 주어진다. 도시는 1번부터 N번까지의 고유한 번호가 매겨진다. 다음 M개의 줄에 걸쳐 www.acmicpc.net 도로를 거꾸로 연결하여 그래프를 만들고 각각의 면접장에서 각각의 도시로 가는 최단 경로를 구해서 어떤 면접장에서 왔을 때 최적인 도시로의 최단경로가 정해졌을 때 가장 긴 거리의 도시를 구한다. 코드 #include #include #include #include #include using namespace std; int n, m, k; ve..

https://www.acmicpc.net/problem/4196 4196번: 도미노 도미노는 재밌다. 도미노 블록을 일렬로 길게 늘어세운 뒤 블록 하나를 넘어뜨리면 그 블록이 넘어지며 다음 블록을 넘어뜨리는 일이 반복되어 일렬로 늘어선 블록들을 연쇄적으로 모두 쓰러 www.acmicpc.net 타잔 알고리즘을 이용해 SCC를 구하고, SCC사이의 그래프를 만들어서 그 SCC사이의 그래프의 indegree가 0인 것의 개수를 구하는 방법을 통해 문제를 해결했다. 코드 #include #include #include #include using namespace std; int tc; int n, m; vector adj[100001]; vector visited(100001); vector maked(10..

https://www.acmicpc.net/problem/20181 20181번: 꿈틀꿈틀 호석 애벌레 - 효율성 꿈틀꿈틀 호석 애벌레는 N 개의 먹이가 일렬로 나열된 나뭇가지를 오른쪽으로 기어가려고 한다. 시작하는 순간의 호석 애벌레가 0의 위치에 있고 i 번째 먹이는 오른쪽으로 i 초 기어가야 도달할 www.acmicpc.net vector cache(100001, 0)을 사용하여 [위치] = 해당 위치에서 끝날 때 최댓값을 업데이트시키는 방법을 이용하였고, 이 과정에서 투 포인터를 이용해서 문제를 해결했다. cache를 업데이트시키는 방법은 cache[right] = max(cache[right], cache[right - 1])를 하고 난 뒤, right를 포함시키면 k이상이 되는 경우 cache..