정보과학 (Informatic) (7) 썸네일형 리스트형 [BOJ] 16602 Brexit Negotiations (NWERC 2018) 문제 설명 및 요약 $N$ 개의 회의가 있으며 각 회의별로 진행 시간과 선행되어야 하는 회의의 번호가 주어진다. 후행 회의는 선행 회의가 아직 진행하고 있어도 이미 시작하기만 했다면 시작할 수 있다. 회의들은 동시에 진행될 수 있지만 매 시간 1개의 회의밖에 시작하지 못한다. 모든 회의가 끝날 때까지 걸리는 시간의 최소값을 구하여라. 풀이 전형적인 그리디 문제의 일종이다. 이 문제의 핵심은 한 회의가 진행되는 동안 다른 회의들도 진행될 수 있다는 것이다. 즉 회의 시간이 긴 회의를 앞쪽에 배치한다면 그 회의를 시작한 후에 두 번째 회의를 시작할 때 두 번째 회의가 끝난 후에도 첫 번째 회의는 진행 중일 가능성이 높기 때문에 총 회의 시간은 크게 변하지 않아 이득이라는 것이다. 이 아이디어를 이용해보자. .. [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$ 라고 부르.. 이전 1 다음
