Doby's Lab

https://www.acmicpc.net/problem/11400 11400번: 단절선 첫째 줄에 두 정수 V(1≤V≤100,000), E(1≤E≤1,000,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A www.acmicpc.net Solved By: Articulation 직전 포스팅인 Articulation Point와 접점이 많습니다. Articulation Point에서 childOrder가 현재 node의 visitedOrder보다 큰 경우가 Articulation Edge가 되는 경우입니다. #include #include #define MAX 100001 #define pii pair..

https://www.acmicpc.net/problem/11266 11266번: 단절점 첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B www.acmicpc.net Solved By: Articulation 처음으로 풀어본 Articulation 문제였습니다. Articulation을 찾는 방법을 설명합니다. [Solution] 1) DFS를 사용하여 모든 node들의 방문 순서(visitedOrder)를 매깁니다. 2) 특정 A node에서 child node들이 A node를 거치지 않고, A node보다 빠른 visitedO..

https://www.acmicpc.net/problem/3640 3640번: 제독 두 함선(빨강, 파랑)은 1에서 시작해서 6에서 만난다. 빨간 함선은 1 → 3 → 6 (총 33개 포탄)으로 이동하고, 파란 함선은 1 → 2 → 5 → 4 → 6 (총 53개 포탄)으로 이동한다. 두 경로에서 출발 www.acmicpc.net Solved By: MCMF 배가 2대가 움직입니다. 이 2대는 중간에서 만나서는 안 됩니다. 어떻게 중복을 체크할 수 있을까 생각을 해보면 저번부터 네트워크 모델링에서 자주 사용하던 테크닉을 사용했습니다. 자주 쓰이므로 앞으로 Node in-out Modeling이라 하겠습니다. 노드 안에 두 개의 노드가 있다고 생각하고, 하나는 in, out으로 사용하며 in과 out을 잇는..

https://www.acmicpc.net/problem/3679 3679번: 단순 다각형 첫째 줄에 테스트 케이스의 개수 c (1 ≤ c ≤ 200)가 주어진다. 각 테스트 케이스는 한 줄로 이루어져 있다. 테스트 케이스의 첫 번째 숫자는 점의 개수 n (3 ≤ n ≤ 2000) 이다. 다음 숫자는 점의 좌 www.acmicpc.net Solved By: Convex Hull, Geometry 이번 문제는 Convex Hull을 구하는 문제가 아닙니다. 주어진 모든 점을 사용하기 때문에 Convex Hull을 구하면서 누락된 점이 있으면 안 됩니다. Convex Hull을 구하기 직전까지의 정렬을 구하면 원하는 답을 찾을 수 있습니다. 시작점과 시작점을 기준으로 CCW를 하여 반시계 방향으로 정렬합니다..

https://www.acmicpc.net/problem/15824 15824번: 너 봄에는 캡사이신이 맛있단다 한 줄에 모든 조합의 주헌고통지수 합을 1,000,000,007로 나눈 나머지를 출력한다. www.acmicpc.net Solved By: Combinatorics, Exponention By Squaring 주어진 수열로부터 모든 조합을 찾아서 해당 조합의 최댓값 - 최솟값을 구하는 문제였습니다. 하지만, 모든 조합을 찾는 데에는 시간 초과가 발생합니다. 구글링으로 솔루션을 찾았는데 정말 배워둘 만한 테크닉인 거 같습니다. 어떤 값 v가 존재한다고 하겠습니다. v가 어떤 조합에서든 최댓값이 될 경우는 정렬을 시켰을 때, v를 포함한 v 이전의 값들을 가지고서 조합을 만듭니다. v 이전의 값들..

https://www.acmicpc.net/problem/14942 14942번: 개미 자연수 n이 주어진다. n은 방의 개수이다. (1 ≤ n ≤ 105) 다음 n개의 줄에는 차례대로 현재 각각의 개미가 보유하고 있는 에너지 값이 주어진다. i+1번째 줄에는 i번째 방에 있는 개미가 가진 에너 www.acmicpc.net Solved By: LCA, Sparse Table 1번 방까지 가야 하고, 경로가 n - 1개 있으며 한 방에서 다른 방으로 갈 수 있는 경로는 존재하며 유일하다 했으므로 이는 root node가 1인 트리를 의미합니다. 그리고, 각 방에서 주어진 에너지를 가지고, 1번 방까지 도달해야 하니 어떤 노드로부터 시작해서 1번 방으로 가는 길에 에너지를 다 쓰거나 남은 상태로 도착하게 되..

https://www.acmicpc.net/problem/5847 5847번: Milk Scheduling Farmer John's N cows (1

https://www.acmicpc.net/problem/1948 1948번: 임계경로 첫째 줄에 도시의 개수 n(1 ≤ n ≤ 10,000)이 주어지고 둘째 줄에는 도로의 개수 m(1 ≤ m ≤ 100,000)이 주어진다. 그리고 셋째 줄부터 m+2줄까지 다음과 같은 도로의 정보가 주어진다. 처음에는 도로의 www.acmicpc.net Solved By: Topological Sort or Dijkstra 우선적으로 최장 경로를 구해야 하기 때문에 Dijkstra가 떠올랐습니다. >> 가중치들을 음수로 바꾸어 최장 경로를 구하는 테크닉 사용 + Topological Sort를 사용하여 최장 경로를 구할 수 있습니다. Topological Sort의 기본 원리를 기억하며 문제를 풀어갑니다. [기본 원리]..