이동식 저장소

3000번: 직각 삼각형 첫째 줄에 점의 개수 N(3 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N개의 줄에는 점의 좌표가 X Y 순서대로 주어진다. (1 ≤ X,Y ≤ 100,000) 겹치는 점은 없다. www.acmicpc.net 아주 단순한 $O(N^{2}\log N)$짜리 풀이법을 생각할 수 있다. 빗변을 이루는 두 점을 고르고, 직각삼각형이 되기 위해 필요한 나머지 한 점이 존재하는지 찾으면 된다. 두 점을 고르는 데 $N^{2}$, 나머지 한 점을 찾는 데 $\log N$ 시간이 걸린다. 그러나 $N \le 100,000$이므로 이 풀이를 사용하면 시간 초과. 따라서 조금 더 빠른 풀이를 생각해야 한다. 사실 나도 꽤 오래 걸렸다. ``빗변이 아닌 두 변이 좌표축에 평행해야 한다``는..

저번 시간까지 RSA에 대해 공부했다. 이제 두 번째 암호에 대해 알아보자. 이산 로그 (Discrete Log) $Z_{n}^{*}=\{ g,g^{2},\cdots,g^{\varphi (n)} (=1) \} $이면 $g$는 $Z_{n}^{*}$의 ``Generator``이다. ``Generator``가 항상 존재하지는 않는다. 예를 들어 $Z_{15}^{*}$의 ``Generator``는 존재하지 않는다. 사실 ``Generator``가 존재할 조건은 다음과 같다. $Z_{n}^{*}$의 ``Generator``가 존재한다 $\Leftrightarrow~n=2,2^{2},p^{k},2p^{k}$, $p$는 홀수 소수 $Z_{7}^{*}=\{1,2,3,4,5,6\}$의 ``Generator`` $g=3$..

소인수분해는 얼마나 어려운가? RSA를 뚫는 것은 $n$을 소인수분해(factoring)하는 문제와 동치임을 보였다. 그러면 소인수분해는 얼마나 어려운가? 지금까지 알려진 바에 의하면 소인수분해는 $NP \cap co-NP$에 속한다. 그러나 소인수분해가 $P$에 속하는지는 알려지지 않았다. 추측하기로는 $P$에는 속하지 않고, $NP \cap co-NP$에 속하지 않을까 싶다. 소인수분해와 소수 확인 (Primality) 더보기 # 소인수분해와 소수 (펼치기) 소인수분해를 하면 소수인지 확인할 수 있다. 그러나 소수인지 아닌지 안다고해서 소인수분해가 가능한 것은 아니다. 소수가 아니라면 그 수의 소인수를 찾아야 하기 때문이다. 위에서 말했듯이 소인수분해는 $P$에 있는지 알려지지 않았다. $n$이 소수..

오랜만에 문제 풀이를 쓴다. 요즘 바빠서;; 2610번: 회의준비 첫째 중에 회의에 참석하는 사람의 수 N이 주어진다. 참석자들은 1부터 N까지의 자연수로 표현되며 회의에 참석하는 인원은 100 이하이다. 둘째 줄에는 서로 알고 있는 관계의 수 M이 주어진다. 이 www.acmicpc.net 위원회 구성 우선 위원회를 구성해야 한다. 서로 알고 있는 사람은 반드시 같은 위원회에 속해야 하므로, Union-Find를 이용하여 위원회를 구성할 수 있다. 서로 알고 있는 사람끼리 ``merge``한 다음, 각 참석자 ``i``를 ``root(i)`` 쪽으로 모은다. 대표 결정하기 대표를 결정하려면 우선 두 사람 사이의 의사전달시간을 알아야 한다. 매번 BFS 등으로 탐색하면 매우 비효율적이므로, 플로이드-와샬..

Complete Residue System $Z_{6}=\{0,1,2,3,4,5\}$에서, $5 \times 5=1 \mod 6$이므로 $5$의 역원은 $5$이다. 그런데 $2$와 곱해서 $1$이 되는 수, 즉 $2$의 역원은 존재하지 않는다. 따라서 Complete Residue System에서는 곱셈이 잘 정의되지 않는다. 곱셈이 잘 정의되지 않는다는 말은 역원 또는 항등원이 존재하지 않는다는 말과 같다. 우리는 곱셈과 나눗셈이 잘 정의되는 Residue System을 원한다. Reduced Residue System $Z_{m}^{*}=\{a|\gcd(a,m)=1,~0 \le a < m\}$ $Z_{m}^{*}$에서 곱셈이 잘 정의된다는 것을 증명한다. $\forall a \in Z_{m}^{*},..