10216번: Count Circle Groups (acmicpc.net) 10216번: Count Circle Groups 백준이는 국방의 의무를 수행하기 위해 떠났다. 혹독한 훈련을 무사히 마치고 나서, 정말 잘 생겼고 코딩도 잘하는 백준은 그 특기를 살려 적군의 진영을 수학적으로 분석하는 일을 맡게 되었 www.acmicpc.net 각 위치 A[i]가 (x,y)를 중심으로 가지고 반지름은 r인 원으로 주어지는데... 두 원이 서로 닿거나 겹친다면 두 원은 통신이 가능하다. 두 원이 서로 닿거나 겹칠려면 어떻게 해야하나? 두 원의 중심사이 거리 AB랑 r1+r2를 비교하면 된다. AB = (r1+r2)이면 두 원이 서로 닿는것이고 AB < (r1+r2)이면 두 원이 서로 겹치는 것이다. 원의 개수가 ..
1. 문제 E - Modulo MST (atcoder.jp) E - Modulo MST AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 단순하게 최소 스패닝 트리를 바로 찾으면, cost 자체는 최소일지 몰라도 그것을 modulo로 나눈 값이 최소라는 보장은 없다 다행히 정점 N
1. 문제 E - Good Graph (atcoder.jp) E - Good Graph AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 2. 풀이 그대로 구현하면 바로 시간초과 당하는데 조금만 생각하면 상당히 간단한 문제가 된다 N개의 정점을 가지고 M개의 간선을 가지는 그래프 G가 주어지는데 모든 i = 1,2,3..,k에 대하여 G에 존재하는 두 정점 $x_{i}, y_{i}$가 서로 연결되어 있지 않다면, G가 good 그래프이다. 이 때, Q개의 query가 주어지는데, 그래프 내의 두 정점 $p_{i}, q_{i..
1. 문제 D - Unicyclic Components (atcoder.jp) D - Unicyclic Components AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online. atcoder.jp 주어진 그래프에서 모든 연결요소가 정점의 개수와 간선의 개수가 같은지 판단하는 문제 2. 풀이 연결요소 하니까 BFS로 찾아볼려고 했는데.. 이게 간선을 관리하기가 만만치 않다 심지어 이 문제는 두 정점 사이 간선이 여러개 있어도 상관없고, 동일한 정점에 간선이 있는 루프도 있다 editorial 피셜로 "One can manage the connect..
1. 문제 16168번: 퍼레이드 (acmicpc.net) 16168번: 퍼레이드 첫 번째 줄에 지점의 개수 V, 연결 구간의 개수 E가 주어진다. (1 ≤ V ≤ E ≤ 3000) 이후 E개의 줄에 걸쳐 각 연결 구간이 연결하는 두 지점의 번호 Va, Vb가 공백을 사이에 두고 주어진다. (1 ≤ Va, www.acmicpc.net 2. 오일러 경로(eulerian trail) "모든 변을 단 한번만 지나서 주어진 그래프를 완성할 수 있는가" 그래프의 모든 간선을 1번만 지나서 모든 정점을 방문하는 연속된 경로를 오일러 경로라고 부른다 혹은 한붓그리기라고도 불린다. 위와 같이 정점은 여러번 지나도 상관없다 위와 같은 그래프는 오일러 경로가 존재하는 그래프이다. 특히 시작점과 끝점이 같은 오일러 경로는 ..
1. 문제1 4143번: Bridges and Tunnels (acmicpc.net) 4143번: Bridges and Tunnels The first line of input contains one integer specifying the number of test cases to follow. Each test case begins with a line containing an integer n, the total number of bridges or tunnels built. This number will be no more than 100,000. We assume that al www.acmicpc.net 2. 풀이1 서로 연결되는 간선이 주어질때마다 각 노드의 집합 크기를 구하는 문제 find..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
