목록Algorithm (121)
블로그 옮겼습니다
홀수 Degree를 가진 노드의 수는 짝수개이다!짝수 Degree를 가진 노드에 대한 성질은 따로 없다.. 짝수개일 수도 홀수개일 수도 있음
문제 링크 \(N\leq{2\cdot{10^5}}\)\(1\leq{a_i}\leq{10^4}\)\(Q\leq{10^4}\)\(1\leq{l_i},\,{r_i}\leq{N}\) (\(l_i= 10000 일때는무조건 0을 출력, 그 외의 경우에는 그냥 직접 정렬을 해서 순회하며 답을 찾으면된다.그러면 각 쿼리마다 최악의 경우 O(KlgK) (K
1scanf("%*d%d",&y);cs 이런식으로 하면 %*d 는 정수하나 입력받아 무시하겠다는거고 그뒤에 y를 하나 입력받겠다는거다.
문제 링크 \(1\leq{N}\leq{10^5}\)\(1\leq{M}\leq{2\cdot{10^5}}\)\(1\leq{x,y}\leq{10^6}\) 2차원 좌표평면상에 도시의 개수 N이 주어지고 N개의 줄에 각 도시의 x,y 좌표가 주어진다.그리고 쿼리의 수 M이 주어지는데 각 쿼리의 동작은 두가지다. road a b : 도시 a와 b 사이에 직선 도로를 이어 하나의 state 로 만든다.line c : x축에 평행하게 y = c 직선을 그어 한 도로라도 이 직선에 교차되는 state 들의 수와그 state 들의 도시 수의 합을 출력한다. c는 무조건 1.5, 5.5 등 ~~.5 의 형태이며 도로들은 서로 교차하지 않는다. \(0\lt{c}\lt{10^6}\) 서로다른 state 가 도로에 의해 하나의 ..
Union-find 다른 말로 Disjoint sets(상호 배타적 집합) 이란 여러개의 집합들에 대해,서로 다른 두 집합의 교집합이 공집합이며, 모든 집합들의 합집합이 전체 집합이 되는 집합들을 말한다.그런데 이게 유용한 이유는 이렇다. 1. 서로 다른 두 원소가 같은 집합 내에 속해 있는지, 아니면 서로 다른 집합에 속해있는 지를 빠른 시간내에 구할 수가 있다.2. 서로 다른 집합에 속해있는 두 노드가 속해있는 두 집합을 빠른시간에 합쳐 더 큰 하나의 집합으로 만들 수가 있다. 그렇기 때문에 크루스칼 알고리즘에서도 유용하며, dfs 대용으로도 쓸 수가 있으며 그 활용이 무궁무진하다.그런데 일반적인 방법으로는 집합을 한꺼번에 합치는 것은 가능하지만, 집합 내의 특정 한 원소 단위로는옮길 수가 없다. 하..
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3138 정말 좋은 문제인것 같다. 풀이
https://uva.onlinejudge.org/index.php?option=onlinejudge&Itemid=99999999&page=show_problem&category=&problem=4075 해석이 너무 안돼서 제대로 이해하는데 엄청 오래걸렸다.. \(5\leq{N}\leq{2\cdot{10^4}}\)\(0\leq{M}\leq{2\cdot{10^5}}\)N은 회사의 수, M은 쿼리의 수N개의 회사는 각각 센터를 가지고 있다. 이 회사들의 일부를 병합을 하여 하나의 더 큰 덩어리로 만드는 동시에센터는 하나로 유지를 하려고 한다. 병합을 할 때에는 하나의 덩어리의 센터에서 나머지 덩어리의 아무 회사로도로를 놓으면서 병합을 한다. 도로의 길이는 회사 a와 b를 이을 때 | a - b| mod 10..
문제들 중에는 특정 조건을 가진 시간과 분을 hh:mm 의 포맷으로 출력하거나 리턴하기를 원하는 문제들이 있다.이럴때 괜히 쓸데없는곳에 시간과 노력을 낭비하지 않기 위해 좋은 방법이 있다.1sprintf(out, "%02d:%02d", h, m);cs 사실 너무 기초적인 것이지만 오랫동안 별로 쓸 일이 없었던 것이라 잊고있었다..이걸 모르면 이런 상황이 발생할 수가있다..123456string ret;if(h
https://community.topcoder.com/stat?c=problem_statement&pm=11514 \(1\leq{N}\leq{50}\)\(1\leq{C}\leq{N}\)\(1\leq{L}\leq{50}\)문자열의 개수 N개와 N개의 알파벳 소문자로만 이루어진 문자열이 주어지고,C와 L이 주어지는데, 길이 L의 문자열을 만들고 싶은데, 이 만들어진 문자열 내에 N개의 문자열들 중딱 C가지만 등장하도록 만드는 모든 문자열의 가짓수를 구하는 문제이다.우선 N가지의 문자열들 중 딱 C가지만 등장하는지 여부를 판단하려면 N개의 문자열을 동시에 하나의 긴 문자열에서등장하는지 찾아주는 알고리즘인 아호코라식 알고리즘이 필요하다는 것을 느낄 수가 있으며,N가지 중 지금까지 몇가지가 등장했는지를 알아야 ..
https://oj.uz/problem/view/KRIII5_YZ \(1\leq{N,M}\leq{400}\)N x M 의 격자가 주어진다. 격자의 각 칸은 'B' 또는 'W' 이다.이 격자를 상하좌우대각선으로 무한히 이어붙였을때 무늬가 나타날 것이다. 여기에는 같은 색끼리 상하좌우로붙어있기도하고 혼자있기도 할텐데 이 같이 붙어있는 수를 각 칸마다 구하는 문제이다. 무한히 많은 같은색 칸이붙게 되는 칸은 -1 을 출력한다.예를 들어 이 경우에는 답이2 2 -1-1 -1 -1이 된다.흰 칸들은 모두 무한히 이어지며, 검은칸들은 각각 두개씩 붙어있기 때문이다. 그럼 이문제를 어떻게 풀까?dfs로도 풀 수가 있겠지만 구현도 쉽고, 예외처리해줄것도 적어 깔끔한 유니온 파인드로 풀어보자.모든 칸들에 대해 상하좌우와..