유클리드 알고리즘이란 정수 a와 b의 최대공약수 gcd(a,b)를 효율적으로 계산하는 방법이다.다음과 같은 공식을 기반으로 한다.def gcd(a,b): if(b==0): return a #만약 b가 0이라면 a=최대공약수 return gcd(b,a%b) #b와 a를 b로 나눈 나머지의 최대공약수이 알고리즘이 올바르게 작동하는 이유는 최대공약수 x는 a와 b 모두의 약수이기 때문에 a mod b의 약수이기도 하기 때문이다.이 알고리즘을 이용하여 시간복잡도를 O(log n)까지 줄일 수 있다. 이를 이용한 연습문제를 하나 풀어보고 마치겠다. 2981 - 검문(골드 4)https://www.acmicpc.net/problem/2981n개의 수가 주어졌을때 이 수들을 나누었을때 나머지가 모두 같은 ..

에라토스테네스의 체(sieve of Eratosthenes)는 2이상 n 이하의 정수 x가 소수인지 판별하는 알고리즘이다.다음은 n=10일때의 작동원리이다.2부터 시작하여 새로운 소수 x를 발견할 때마다 2x,3x,4x...를 소수가 아니라 체크한다.이러한 과정을 통해 시간 복잡도를 O(n log log n)까지 줄일 수 있다. 또한 이를 최적화 할 수 있는 방법이 몇가지 있다.1.새로운 소수 x를 발견할때마다 2x,3x,4x...를 소수가 아니라 체크하므로 x^2이 n보다 작을 때 까지만 실행하면 된다.2.새로운 소수 x를 발견하면, x부터 시작하는 것이 아닌 x^2부터 시작하면 된다. 이유는 그 사이값들은 이미 x보다 작은 소수들에 의해 체크되었기 때문이다. 이를 이용하여 간단한 백준 문제를 연습해보..