본문 바로가기

Algorithm Problem/Codility

 (91)
Lesson 12. Euclidean algorithm - CommonPrimeDivisors #4 (개선-3) 1. 속도 개선 아이디어두 수(N, M)의 밑이 같다면, 두 수의 소인수는 최대공약수의 밑으로만 구성이 되어있다. (10, 30)의 최대공약수(GCD)를 구해보자.\( 10 = 2 \times 5 \)\( 30 = 2 \times 3 \times 5 \)\( GCD = 2 \times 5 \) 최대공약수를 이용해서 두 수의 소인수를 제거 했을 때, 제거되지 않는 소인수가 있다면?이건 그 수만 가지고 있는 소인수가 된다.즉, 두 수의 소인수는 같지 않다라는 결론에 도달할 수 있다. 이 방법은 소인수의 밑을 찾을 때, 최대공약수를 활용하므로, 이전 코드에서의 불필요한 연산을 줄일 수 있다.이전코드에서는 10과 1000이 같은 소인수들을 가지고 있는지 확인하려면, 10과 1000의 모든 소인수들을 구하고 비교..
Lesson 12. Euclidean algorithm - CommonPrimeDivisors #3 (개선-2) 1. 속도 개선 아이디어최대공약수를 이용하면 예외처리를 추가할 수 있다.(최대공약수 = 1 = 서로소) 2. 코드 (C++)#include #include //최대공약수 구하기int GetCGD(int a, int b){ if(a % b == 0) return b; else return GetCGD(b, a % b);}//소인수 구하기map GetPrimeDivisors(int n){ map prime_divisors = {}; //map int i = 2; while(i (i, 1)); } else { it->second += 1; } // n을 i로 ..
Lesson 12. Euclidean algorithm - CommonPrimeDivisors #2 (개선-1) 1. 이전 코드의 문제점에라토스테네스의 체가 너무 커서, 메모리 할당에 실패했다. 2. 개선 아이디어에라토스테네스의 체를 쓰지 않고, 2부터 N까지 하나씩 나눠가며 소인수를 찾는다. 3. 코드 (C++)#include #include //소인수 구하기map GetPrimeDivisors(int n){ map prime_divisors = {}; //map int i = 2; while(i (i, 1)); } else { it->second += 1; } // n을 i로 나누어서, n 값을 줄인다 // 소인수 i가 여러번 쓰일수도 있기 때문에, i..
Lesson 12. Euclidean algorithm - CommonPrimeDivisors #1 1. 문제A prime is a positive integer X that has exactly two distinct divisors: 1 and X. The first few prime integers are 2, 3, 5, 7, 11 and 13.A prime D is called a prime divisor of a positive integer P if there exists a positive integer K such that D * K = P. For example, 2 and 5 are prime divisors of 20.You are given two positive integers N and M. The goal is to check whether the sets of prime d..
Lesson 12. Euclidean algorithm - ChocolatesByNumbers 1. 문제Two positive integers N and M are given. Integer N represents the number of chocolates arranged in a circle, numbered from 0 to N − 1.You start to eat the chocolates. After eating a chocolate you leave only a wrapper.You begin with eating chocolate number 0. Then you omit the next M − 1 chocolates or wrappers on the circle, and eat the following one.More precisely, if you ate chocolate numb..
Lesson 11. Sieve of Eratosthenes - CountSemiPrimes #3 (속도 개선-2) 1. 속도 개선 아이디어 CountSemiPrimes #2에서는 소수 판별 알고리즘과 semi prime 계산하는 부분을 수정했는데, 생각보다 성능 개선이 미비했다. (결과를 비교해보면, 아주 쪼금 좋아지긴 했다) 이제 개선해야할 코드로는, semi prime 개수 세는 부분만이 남아있다. semi prime 개수 세는 코드는 현재 이중반복문으로 되어있는데, prefix sum을 이용하면, 즉시 계산할 수 있다.   2. 코드 (C++)semi prime도 값을 직접 다루지 않고, table에 표시해두는 형태로 수정했다.  #include vector solution(int N, vector &P, vector &Q) { //소수 및 최소 소인수 구하기 vector prime_factors(N..
Lesson 11. Sieve of Eratosthenes - CountSemiPrimes #2 (속도 개선-1) 1. 속도 개선 아이디어CountSemiPrimes #1에서 사용하고 있는 소수 판별 알고리즘은 좋은 알고리즘이긴 하지만, 특정한 숫자가 소수인지 판별하는데 적합한 알고리즘이다. 게다가, semi prime을 구할 때, 소수를 하나 하나씩 곱해가며, 계산하고 있다. '에라토스테네스의 체'를 이용하면, 특정 범위안에 있는 소수를 모두 찾을 수 있고, semi prime 계산 속도도 증가시킬 수 있다. 아라토스테네스의 체에 대한 내용을 아래 링크를 참조 바란다.에라토스테네스의 체 이론에라토스테네스의 체 구현(C++) semi prime 설명을 잘 생각해보면, semi prime은 합성수 임을 알 수 있다.정확히는 합성수 중에서, 소인수만을 인수로 갖는 합성수이다. 아라토스테네스의 체를 응용하면,  합성수에 ..
Lesson 11. Sieve of Eratosthenes - CountSemiPrimes #1 1. 문제A prime is a positive integer X that has exactly two distinct divisors: 1 and X. The first few prime integers are 2, 3, 5, 7, 11 and 13.A semiprime is a natural number that is the product of two (not necessarily distinct) prime numbers. The first few semiprimes are 4, 6, 9, 10, 14, 15, 21, 22, 25, 26.You are given two non-empty arrays P and Q, each consisting of M integers. These arrays rep..
반응형

티스토리툴바