1. 밀러 라빈 소수 판별법(Miller-Rabin primality test) 어떤 홀수 n이 소수인지 확률적으로 판별해주는 알고리즘 확률적이라는 말은, 합성수를 소수로 잘못 판별할 수 있다는 뜻이다. 주어진 n이 "합성수이다" 또는 "아마도 소수일 것이다"라는 대답을 내놓는다는 의미 2. 핵심 아이디어 알고리즘의 아이디어는 페르마의 소정리에서 시작한다. https://deepdata.tistory.com/573 페르마의 소정리 문제 풀어보면서 익히기 1. 페르마의 소정리(Fermat's little Theorem) 1-1) p가 소수이고, a가 p의 배수가 아니면( = a와 p가 서로소이면 = gcd(a,p) = 1)이면, $$a^{p-1} \equiv 1 (mod p)$$이다. 1-2) p가 소수이..
1. 문제 11690번: LCM(1, 2, ..., n) (acmicpc.net) 11690번: LCM(1, 2, ..., n) 첫째 줄에 1보다 크거나 같고, n보다 작거나 같은 모든 자연수의 최소공배수를 출력한다. 정답이 매우 커질 수 있기 때문에, 232로 나눈 나머지를 출력한다. www.acmicpc.net 2. 풀이 두 수 a,b의 최소공배수를 어떻게 구하는지 생각해본다면.. a랑 b를 소인수분해하고... 각각 소인수분해에서.. 소인수의 지수가 큰것끼리 곱하면 그것이 a,b의 최소공배수이다. 예를 들어 18과 24의 최소공배수를 구한다면.. $$18 = 2 * 3^{2}$$ $$24 = 2^{3} * 3$$ 여기서 소인수는 2와 3만 나타나는데.. 각각에서 지수가 큰 경우는 $2^{3}$이랑 $..
1. 에라토스테네스의 체 기본형태 n이하의 소수를 구하는 알고리즘 n+1개의 1을 가지는 리스트로 초기화하고, 2부터 n의 제곱근까지 순회하여 해당 수의 배수를 모두 지우고 나면 소수만 남는다는 알고리즘이다 n = int(input()) result = [1]*(n+1) for i in range(2,int((n+1)**(1/2))+1): if result[i] == 1: for j in range(i*i,n+1,i): result[j] = 0 prime_list = [i for i in range(2,n+1) if result[i] == 1] 여기서 j의 시작 지점을 i+i로 하는 경우가 많은데, i*i로 해도 된다. 왜냐하면, i+i는 결국 가장 먼저 2의 배수에서 지워지기 때문이다. 2. 에라토스테..
나머지를 구할때 %로 구하면 되는데.. 효율적으로 구한다는게 도대체 무슨말인가? %연산은 계산 비용이 높아서 비효율적으로 알려져있다. n = 98 print(n % 2) #0 print(n % 4) #2 print(n % 8) #2 print(n % 16) #2 print(n % 32) #2 계산비용을 줄이고 싶다면 % 연산자를 사용하지 않고 나머지를 구해야한다. 예를 들어 4로 나눈 나머지를 어떻게 구할 수 있을까? 컴퓨터는 모든 수를 2진수로 인식하기 때문에.. 가장 쉬운 접근은 정수 n을 2진수로 나타내보는 것이다. 위 그림을 보면 어떤 수를 4로 나눈 나머지는 0,1,2,3중 하나인데... n을 2진수로 나타냈을때 4로 나눈 나머지는... n의 2진수 표현에서 오른쪽 끝의 2비트만 가져오는 것임을..
1. 문제 25342번: 최대 최소공배수 (acmicpc.net) 25342번: 최대 최소공배수 $N = 3$인 경우, $1, 2, 3$을 선택하면 최소공배수는 $6$이다. $N = 4$인 경우, $2, 3, 4$를 선택하면 최소공배수는 $12$이다. www.acmicpc.net 2. 풀이 3개의 수의 최소공배수가 최대가 될려면 어떻게 해야할까 두 수 a,b의 최소공배수는? a = Gn이고 b = Gm으로 표현할 수 있다면(G는 a,b의 최대공약수, n,m이 서로소) a,b의 최소공배수는 L = Gnm이다. 이 최소공배수가 가장 클려면 어떻게 해야할까? L = Gnm이므로, L = am이거나 L = bn으로 표현할 수 있다. 이 둘은 모두 ab보다 작거나 같다. 따라서, L
1. 문제 17427번: 약수의 합 2 (acmicpc.net) 17427번: 약수의 합 2 두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더 www.acmicpc.net 2. 풀이 문제를 요약하면 1부터 n까지 각각 약수의 합을 전부 더한 값을 출력하는 문제 시간이 0.5초라서 당연히 1부터 n까지 소인수분해하고 약수의 합을 구한다면 시간초과겠지 약수의 합을 구하는 공식은... https://deepdata.tistory.com/588 약수의 합과 약수의 개수 공식 익히기 1. 약수의 개수 자연수 n의 소인수..
딥러닝/머신러닝, 통계학, IT프로그래밍, 알고리즘을 좋아하는 사람 https://github.com/yundaehyuck
