블로그 옮겼습니다

\(2\leq{len}\leq{2500}\) 이 문제는 길이 len 의 correct parentheses sequence 가 주어졌을 때 왼쪽에 있는 '열린 괄호'를 하나와 임의의 위치에 있는닫힌 괄호 하나, 총 두개를 지우는 행위를 빈 문자열이 될 때 까지 반복하는 방법의 수를 구하는데, 지울 때 마다 지운 직후에도 correct paranthese sequence 이도록 지우는 방법의 수를 구하는 문제이다. 우선 이 문제를 좀 더 간단하게 바꿔보자. 왼쪽에서부터 열린괄호 하나와 닫힌괄호 하나를 지워나가는 것은 결국열린괄호 하나와 닫힌괄호 하나를 매칭시키는 것과 같다고 볼 수가 있다. 물론 한 쌍을 지워도correct parentheses sequence 이도록 말이다. 그럼 주어진 제약조건을 만족하..

문제 링크 \(2\leq{N}\leq{10^5}\)\(1\leq{M}\leq{2\cdot{10^5}}\)\(1\leq{c}\leq{10^9}\) 노드의 개수 N, 엣지의 개수 M, 각 엣지에는 색 c 가 부여된다. 색은 정수로 주어진다. 엣지는 양방향이다.두 노드 사이에 엣지는 여러개 있을 수 있다.출발점은 1번노드, 도착점은 N번노드이다. 출발점에서 도착점까지 갈 때 지나는 통로의 색을 순서대로 적는다.출발점부터 도착점까지 최단경로로 갈 때의 색의 sequence 를 구하는 문제. 만약 최단경로가 여러개라면사전순으로 앞서는 sequence 를 구하는 문제이다. 우선 priority_queue 를 사용해 다익스트라를 하듯이 거리와 색의 우선순위에 따라 도착지까지 가면서색의 seqeunce 를 구해주면 될..

예를 들어vector v[3] 이 있고v[0] = {2, 5, 9, 3}v[1] = {0, 7, 4}v[2] = {1, 6, 8} 일때, 각각의 벡터를 정렬한 뒤 벡터들은 사전순으로 정렬 하려면그냥 sort(v, v+3) 을 하면 알아서 한꺼번에 정렬됨

문제 링크 이 문제는 일단 모빌이 주어진다. 모빌이란, 막대기가 있고 막대기의 양쪽에 모빌또는 물체가 달린다.모빌의 깊이는 최대 16이다. 이때 각 모든 막대기의 양옆에 달린 덩어리 두개가 균형을 이루게 만들기 위해최소 몇개의 물체나 무게를 변경해야 하는지 구하는 문제이다.예를들어,이런 모빌이 있다면 7을 3으로 만들면 모든 막대기에서 균형이 맞게되므로 답은 1이다.3을 7로, 6을 14로 바꿔도 균형을 이루지만 최소의 개수가 아니기 때문에 답이 아니다. 그러면 결국 전체 모빌의 무게를 x로 만들려고 할때 각 덩어리의 무게는 다음과 같이 만들어 주어야 한다. 그렇다면 x를 정해주고 재귀적으로 따라 내려가면서 각각의 덩어리에 대해 되어야 하는 무게와 현재 물체의 무게가같다면 바꾸어 주어야하는 것이기 때문에..

문제 링크 \(1\leq{V}\leq{10^3}\)\(1\leq{E}\leq{V\cdot(V-1)/2}\)\(1\leq{T}\leq{10}\) 도시의수 V와 검사해야 할 도로의 수 E가 주어지고, E개의 줄에 대해 도로가 잇는 두 도시 a b 가 주어진다.모든 두 도시 간에는 도로가 있으며, 각 도로를 지나는데 드는 시간은 T이다. 도로를 검사하는 검사자가 주어진 E개의 도로를 모두 지나야 한다. 이 때 최소 시간을 구하는 문제이다. 모든 엣지의 가중치가 T로 같은 것이기 때문에 이 문제는 결국 최소의 간선을 지나면서 주어진 간선을 모두 지나는문제를 풀고 T를 곱하면 된다. 최소의 간선을 지나려면 주어진 간선들을 딱 한번씩만 지나고주어진 간선 외의 간선은 가능한한 지나지 않으면 될 것이다. 주어진 간선만..

홀수 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 대용으로도 쓸 수가 있으며 그 활용이 무궁무진하다.그런데 일반적인 방법으로는 집합을 한꺼번에 합치는 것은 가능하지만, 집합 내의 특정 한 원소 단위로는옮길 수가 없다. 하..