본문 바로가기
반응형

오일러 프로젝트6

7. 프로젝트 오일러 #7 : 10,001번째 소수 찾기 큰 수에 대한 소수를 찾는 것이라면, 응당 다른 방법을 택해야 하겠지만, 비교적 작은 소수에 대해서는 에라스토테네스의 체 이상 가는 알고리즘이 별로 없습니다. 특히 이번 문제와 같이 10,0001번째 소수 찾기라면 더더욱 말이죠. 알고리즘 자체는 아주 간단합니다. 소수를 저장할 수 있는 배열 공간을 잡고, 여기에 차곡차곡 소수를 담아넣습니다. 일단 2를 제외한 모든 소수는 홀수이므로, 검사해야 하는 수를 절반으로 줄일 수 있습니다. 2를 제외한다면, 소수는 다음과 같이 표현될 수 있습니다. 2와 3을 제외한다면, 소수는 다음과 같이 표현될 수 있습니다. 2, 3, 5를 제외한다면, 소수는 다음과 같이 표현됩니다. 일반적으로 우리는 오일러 수만큼 해당하는 소수만 검사하면 됩니다. 제외하는 소수가 몇개이든 .. 2014. 12. 23.
[C/C++] 프로젝트 오일러 #5 : 1~20으로 나누어지는 가장 작은 자연수(수학) 문제의 난이도가 조금씩 높아져 가는 것을 느끼네요. 이번 문제는 효율성을 충분하게 발휘할 수 있는 문제입니다. 가장 쉬운 알고리즘으로는, 1부터 차례대로 모든 수에 대해서 1부터 20까지의 숫자로 나누어 떨어지는 첫번째 수를 찾으면 쉽게 해결이 되겠지만, 그렇게 되면 너무 많은 수에 대해서 검사를 해야 합니다. 여기서는 유클리드 방법에 의해서 최대 공약수를 찾고, 그 수를 가지고 곱을 해내가는 방식으로 알고리즘을 생각했습니다. 유클리드 방법에 의해서 최대공약수를 찾는 것은, 두 수중 작은 수 N에 대하여 O(log N)의 알고리즘으로 찾을 수 있습니다. 그러면 결국 20까지의 숫자를 N으로 표현한다면 O(N log N) 알고리즘으로 답을 찾을 수 있습니다. 가장 쉬운 알고리즘이라고 소개한 경우에는 답을 .. 2014. 12. 22.
4. 프로젝트 오일러 #4 : 가장 큰 대칭수 구하기 이번 문제는 간단하게 생각하면, 세자리수 a, b를 곱한 수가 대칭수인가 판단하면 된다고 할 수 있습니다. 그러나 그럴 경우 세자리수 x 세자리수의 갯수가 1억개정도 나오게 되죠. 그것에 대한 대칭수를 판단하는 것은 문제가 있을 수 있습니다. 그래서 제가 구현한 알고리즘은, 1) 세자리수 x 세자리수 해서 나올 수 있는 가장 큰 대칭수부터 차례대로 발생시키고 (최대 900개) 2) 그 수들이 세자리수의 곱으로 표현되는가 (최대 900개) 결국 첫번째와 두번째가 오더가 비슷하지 않는가 하겠지만, 실제로는 많은 차이가 있습니다. 첫번째 알고리즘은 최댓값을 구하는 과정이 다시 필요합니다. 그러나 두번째 알고리즘은 첫번째 매칭이 되는 결과가 최댓값이 됩니다. 프로그램을 표시하자면, 아래와 같습니다. 세자리수 곱.. 2014. 12. 19.
#3 : 가장 큰 소인수 찾기 이번 문제는 주어진 수에 대해서 가장 큰 소인수를 찾는 프로그램입니다. 사실 에라스토테네스의 체를 이용하여 가장 큰 소인수를 찾을 수밖에 없습니다. 일단 필요한 것은 주어진 수를 계속 나누기 하는 것입니다. 프로그램 역시 이 범주를 벗어나지 않습니다. 조금 속도를 빠르게 하기 위해서는 소수의 일반적인 형태, 2를 제외한 모든 소수는 홀수이다. 홀수 소인수는 6k+1, 6k+5를 가진다 등을 이용해서 시도횟수를 줄일 수는 있습니다. 이번에는 더 효율적인 알고리즘을 찾기 위한 방법은 별로 없어보이네요. 간단하게 프로그램을 짜보면 다음과 같습니다. int main() { int p = 3; int64 n = 600851475143; while( n%2 == 0 ) n /= 2; if( n == 1 ) { pr.. 2014. 12. 19.
프로젝트 오일러 #2 피보나치 수열의 짝수항 합 C/C++ 언어를 배우다보면, 꼭 한번은 프로그램해보는 것이 있다면, 피보나치 수열일거라 생각합니다. 피보나치 수열은 재귀함수를 사용한 곳에서도 많이 나오지만, 동적 프로그램이 필요한 예로도 자주 사용됩니다. 피보나치 수열은 한쌍의 토끼의 개체수 증가라는 퀴즈 형태에서 출발한 것인데요. 꼭 토끼가 아니라도 대장균의 증식같은 데에서도 응용할 수 있습니다. 기하함수로 증가하는 곡선을 보이게 됩니다. 피보나치는 아주 간단한 점화식을 이용합니다. \[ F_{n} = F_{n-1} + F_{n-2} \] 점화식을 보면 아주 간단한 형태입니다. 전항과 전전항을 더한 값이 현재항의 값이 됩니다. 그래서 첫번째 항과 두번째 항이 초기값으로 주어져야 합니다. 첫번째 항은 1, 두번째 항은 1입니다. 자연수 범위안에서 피.. 2014. 12. 19.
프로젝트 오일러 #1 3 또는 5의 배수의 합 대학 과제에서 보면, 1부터 100까지 다 더하는 프로그램을 만드세요라는 문제가 많이 나옵니다. 대부분 결과는 for 루프를 이용해서 답을 구하고 있습니다. (물론 문제 출제 의도는 for 루프를 잘 쓸 수 있는지를 보는 것이니 당연하다고 할 수도 있겠죠.) 그렇다고 해서, 1부터 n까지 합을 구하는 가장 기본적인 공식을 알고 있다면, 굳이 for 루프를 돌리지 않아도, 계산을 할 수 있습니다. for 루프를 돌린다면, \(O(n)\)만큼의 시간이 기본적으로 듭니다. 그렇지만, 등차수열의 합 공식을 이용하면, 상수 시간으로 계산을 할 수 있습니다. 사실 더해야 하는 범위가 오일러 프로젝트의 문제처럼 1,000정도라면, 프로그램 실행시간은 사람이 눈치챌 수 없을 정도입니다. 해당 숫자 범위 안에서 m배수만.. 2014. 12. 18.
728x90