전체 글 (15) 썸네일형 리스트형 [BOJ] 10075 친구 (IOI 2014) // [KOISTUDY] 1457~1459, 1461~1463 친구 1~6 Taipei에서 열린 IOI 2014에 출제되었던 문제로 어려워보이는 난이도와는 다르게 모범코드는 매우 짧으며 명확한 문제이다. 모든 정보가 주어진 상태에서 역행하면서 "같은 답을 얻을 수 있지만 정점의 수는 적은 그래프" 로 주어진 그래프를 변환하여 풀면 쉽게 해결된다. i번째 프로토콜로 WeAreYourFriends 가 입력됬다고 하자. WeAreYourFriends 프로토콜을 처리하면서 주목할 점은 host 와 사람 i를 동시에 표본에 포함시킬 수는 없지만 host 또는 사람 i가 표본에 포함되었을 때에는 상대방과 host 의 친구들은 모두 표본에 포함시킬 수 없다는 점이다. 이 사실을 바탕으로 그래프에서 사람 i 가 존재하지 않는 동치 그래프로 바꾼다면 host 의 신뢰도를 $trust[host].. [BOJ] 5257 timeismoney 문제가 영어라 혼동되는 분들을 위해 핵심을 적어보자면 다음과 같다. $N$ 개의 정점이 존재한다. $N-1$ 개의 무향 간선으로 이 정점을을 모두 잇고 싶다. $M$ 개의 간선이 들어오며 각 간선마다 건설할 때 필요한 시간과 비용이 존재하는데 $N-1$ 개 간선들을 건설할 때 걸리는 시간의 합과 소모되는 비용의 합의 곱이 최소가 되도록 만들고자 한다. 총 시간의 합과 총 비용의 곱의 최소값은 얼마인가? (단 두 정점을 잇는 간선은 한 개만 들어오며 건설해야하는 간선의 번호까지 출력해야 한다 Kruskal algorithm을 이용하면 시간의 합의 최소와 비용의 합의 최소는 쉽게 구할 수 있다. 그런데 이 둘의 곱의 최소는 어떻게 구할 수 있을까? 우선 간단한 아이디어로 구할 수 있는 "최소"의 틀을 확장시.. Pollard's rho 알고리즘 소인수분해를 해야한다. 그런데 대상인 수가 18자리의 거대한 수라면?! 가볍게 소인수분해를 할 때 사용하는 $O(\sqrt{N})$ 의 알고리즘으로는 어림도 없다. 만약 더 빠른 알고리즘의 필요성을 느꼈다면 아래의 Pollard's rho 알고리즘이 좋은 대안이 될 수 있다. Pollard's rho algorithm Pollard's rho algorithm은 영국의 수학자 John Pollard가 1975년 고안한 알고리즘으로 평균적으로 대략 $O(N^{1/4})$ 정도에 동작한다. 다만 언제나 $O(N^{1/4})$ 인 것은 아닌데, 이는 휴리스틱 알고리즘이기 때문이다. 난수와 관련된 부분에서 의사난수를 사용하기 때문에 늘 $O(N^{1/4})$ 임이 보장되지는 않는다. N을 소인수분해를 한다고 하.. Miller-Rabin primality test (밀러-라빈 소수판정법) "2,305,843,009,213,693,951을 소인수분해 하시오." 하고 싶어도 못할 것이다. 이 수는 소수이기 때문이다. 그러나 흔히 알려진 $O(\sqrt{N})$ 알고리즘을 사용하기에도 시간이 부족해 보인다. 이 경우 밀러-라빈 소수판정법을 사용하면 어마어마하게 단축된 시간에 소수인지 아닌지 여부를 판단할 수 있다. Miller-Rabin pirmality test 밀러 라빈 소수판정법은 하나의 $lemma$ 를 통하여 시작된다. $lemma$ 홀수인 소수 $p$ 에 대하여 $p-1 = 2^s d$ 라고 할 때 gcd$(p,\;a) = 1$ 인 $a$ 에 대해서 $a^d \equiv 1$ (mod $p$) 또는 $0 \leq r < s$ 인 정수 $r$ 에 대하여 $a^{2^r d} \equiv.. [KOISTUDY] 수열과 쿼리 [2124 / 084C] http://koistudy.net/?mid=prob_page&NO=2124 KOISTUDY Informatica Online Judge Time Limit(Test case) : 5000(ms)Number of users who solved : 9 Total Tried : 64 The Champion of this Problem (C++) : gs16044 - ms / 1134byte My Best Submission (C++) : N/A [koistudy.net (34th 김현수)] Background 현수는 수열과 쿼리 문제 시리즈의 추 koistudy.net 기본적인 틀은 간단하다. $i$~$j$ 범위 안의 $k$ 의 개수를 구하는 것은 우선 merge sort tree 를 형성해주고 1 2 3 .. 반복함수에서의 Cycle detection 유한집합 $X$ 에 대하여 $f : X\rightarrow X$ 인 함수 $f(x)$ 가 있다. $i>0$ 인 $i$ 에 대하여 $x_i = f(x_{i-1})$ 이라고 하면 수열 $x_i$ 는 반복되는 구간을 가짐이 자명하다. 그렇다면 반복의 시작점과 반복 주기는 어떻게 찾을 수 있을까? 이 글에서는 적은 공간복잡도로 빠른 시간 내에 답을 찾을 수 있는 알고리즘을 소개하려고 한다. Floyd's cycle-finding algorithm 우선 반복의 최초 시작점을 $\mu$, 가장 짧은 반복 주기를 $\lambda$ 라고 할 때 시간복잡도 $O(\mu+\lambda)$, 공간복잡도는 $O(1)$ 인 알고리즘이다. 이 알고리즘에서는 두개의 포인터를 사용하는데 두 포인터를 각각 $T$ 와 $H$ 라고 부르.. 이차곡선 식 유도하기, xy 항 소거하기 두 원뿔을 거꾸로 붙여놓은 도형을 평면으로 잘랐을 때 생기는 곡선을 원뿔곡선, 또는 이차곡선이라고 한다. 이차곡선에는 원, 타원, 쌍곡선, 포물선 등이 있다. 일반적으로 이차곡선은 다음과 같이 표현된다. $ax^2+bxy+cy^2+dx+ey+f = 0$ 우리가 알던 원, 타원, 쌍곡선, 포물선의 식과는 조금 다르지 않은가? 평행이동을 하여서 $x$ 항과 $y$ 항이 있을지는 몰라도 $xy$ 항은 처음 본다. 이 항은 회전변환에 의해 생긴 것이다. 우선 $b = 0$ 인 식은 모두 하나의 이차곡선과 대응된다는 사실을 우리는 알고 있다. 이제 $xy$ 항이 있는 식 또한 이차곡선의 식임을 증명해보자. 일반적인 회전변환의 행렬식은 다음과 같다. $ \begin{bmatrix} cos \theta& -sin \.. 이전 1 2 다음
