뉴비의 PS 낙서장

https://www.acmicpc.net/problem/18919 18919번: Allowed Swaps You are given a permutation of length $N$ and a list of allowed swaps. Each swap is defined by two distinct integers between 1 and $N$, inclusive --- positions in the permutation that can be swapped. Your task is to sort the permutation using no more than www.acmicpc.net \(x, y\) 쌍이 들어오면 \(x\) 와 \(y\)를 이어주는 간선을 만들어준다. 그러면, 그래프가 형성되는데, 사..

https://www.acmicpc.net/problem/20052 20052번: 괄호 문자열 ? 괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이 www.acmicpc.net '('을 1, ')'을 -1이라 가정한다. 만약 어떤 구간 [l,r]이 올바른 괄호 문자열이 아니라면 ')'가 '('보다 많아지는 순간이 있을 것이다. 이를 누적합으로 표현해보면 l부터 누적으로 더하다가 0보다 작아지는 경우와 ')'가 '('보다 많아지는 경우은 동치이다. 따라서 구간의 누적합을 구하고, 누적합들의 최솟값이 0보다 작아지는 경우가 있는지 검사해보는 식으로 바꿀 수 있다..

https://www.acmicpc.net/problem/15311 15311번: 약 팔기 첫 번째 줄에 동규의 최대 약 요구량을 나타내는 정수 N ($=1\, 000\, 000$) 이 주어진다. www.acmicpc.net 이 문제는 언뜻 보면 어려워 보이는데, 사실 \((2000/2)^{2} = 10^{6}\) 임을 알면 왼쪽에 1000개, 오른쪽에 1000개에 적당한 약의 개수를 넣으면 \(10^6\) 개를 만들 수 있을 것 같다. 어떤 약의 수 X만큼을 주기 위해 X를 1000으로 나눈 몫과 나머지에 대한 식을 세워보자. $$X = 1000*b + r$$ 왼쪽엔 1000짜리 1000개, 오른쪽에는 1짜리 1000개를 넣으면, 원하는 수 만큼의 약을 담을 수 있다. #include using nam..