본문 바로가기
반응형

Programming/Project Euler89

10. 프로젝트 오일러 #10 : 2백만 이하의 소수의 합 구하기 사실 이번 문제는 에라스토테네스의 체를 이용하는 것 이외에는 별다른 좋은 방법은 없어보입니다. 큰 수에 대해서는 효율적인 알고리즘을 개발할 수 있지만, 2백만이라는 비교적 작은 수에 대한 것이라서 간단하게 짜보았습니다. #define LIMIT 2000000 void solve1() { int primes[200000]; int count = 0; int64_t sum = 0; primes[count++] = 2; sum += 2; primes[count++] = 3; sum += 3; for( int p = 5 ; p < LIMIT ; p+=2 ) { bool isPrime = true; for( int i = 1; primes[i]*primes[i] 2014. 12. 24.
9. 프로젝트 오일러 #9 : 합이 1,000인 피타고라스 수 구하기 이번 문제는 합이 1,000인 피타고라수 수 구하기입니다. 피타고라스 수의 일반항은 이미 잘 나와 있어서, 그 공식을 이용하면, 손쉽게 프로그램으로 만들 수 있습니다. 을 이용해서 피타고라스 쌍을 구하도록 합니다. G(s, t) = 1 인 수를 구하면, 원래 배수가 아닌 피타고라스 쌍을 얻을 수 있지만, 배수인 쌍으로도 나올 수 있기 때문에, 여기서는 s > t 라는 조건만 걸어서 제작했습니다. 단 무한대로 검사할 수 없으므로, 프로그램에서는 x+y+z 2014. 12. 23.
8. 프로젝트 오일러 #8 : 가장 큰 곱하기 수 구하기. 이 문제는 문서에서 단어찾기에도 이용할 수 있는 문제입니다. 단어찾기의 경우에는 보통 더하기 해시를 이용하든지 하겠지만, 여기서는 곱하기이기 때문에 일단 숫자 범위가 넘어가는지 생각해보는 것도 필요합니다. 그리고 0이란 숫자가 있기 때문에 좀 골치 아픕니다. 13개의 단자리 곱셈이기 때문에 최대 숫자는 9의 13제곱인 2,541,865,828,329이 됩니다. 약 20억정도의 숫자를 표시하는 int 형으로는 오버플로우가 발생할 수 있습니다. 그래서 int64 자료형을 이용해서 프로그램을 작성해야 합니다. 4개의 숫자를 가지고 한다고 하면, 7316717653 의 숫자의 경우, 7x3x1x6 3x1x6x7 1x6x7x1 ... 과 같이 하나씩 이동하면서 4개씩 곱해주어도 됩니다. 그렇지만, 7 3 1 6 .. 2014. 12. 23.
7. 프로젝트 오일러 #7 : 10,001번째 소수 찾기 큰 수에 대한 소수를 찾는 것이라면, 응당 다른 방법을 택해야 하겠지만, 비교적 작은 소수에 대해서는 에라스토테네스의 체 이상 가는 알고리즘이 별로 없습니다. 특히 이번 문제와 같이 10,0001번째 소수 찾기라면 더더욱 말이죠. 알고리즘 자체는 아주 간단합니다. 소수를 저장할 수 있는 배열 공간을 잡고, 여기에 차곡차곡 소수를 담아넣습니다. 일단 2를 제외한 모든 소수는 홀수이므로, 검사해야 하는 수를 절반으로 줄일 수 있습니다. 2를 제외한다면, 소수는 다음과 같이 표현될 수 있습니다. 2와 3을 제외한다면, 소수는 다음과 같이 표현될 수 있습니다. 2, 3, 5를 제외한다면, 소수는 다음과 같이 표현됩니다. 일반적으로 우리는 오일러 수만큼 해당하는 소수만 검사하면 됩니다. 제외하는 소수가 몇개이든 .. 2014. 12. 23.
6. 프로젝트 오일러 #6 : 합의 제곱과 제곱의 합 차 구하기. 사실 이번 문제는 앞에서 합을 구하는 문제와 동일합니다. 뭐 for 루프를 이용해서 답을 구해도 되겠지만, 그냥 알고 있는 공식을 이용해도 됩니다. 단 공식을 이용할 때 주의할 점은 결과의 범위가 넘어갈 것인가 아닌가입니다만, 그것을 무시한다면, 공식을 이용해서 계산하는 것이 더 빠르겠죠. int main() { int n = 100; int s1, s2; s1 = n*(n+1)*(2*n+1)/6; s2 = n*(n+1)/2; printf("Ans = %d\n", s2*s2 - s1); } 2014. 12. 22.
[C/C++] 프로젝트 오일러 #5 : 1~20으로 나누어지는 가장 작은 자연수(수학) 문제의 난이도가 조금씩 높아져 가는 것을 느끼네요. 이번 문제는 효율성을 충분하게 발휘할 수 있는 문제입니다. 가장 쉬운 알고리즘으로는, 1부터 차례대로 모든 수에 대해서 1부터 20까지의 숫자로 나누어 떨어지는 첫번째 수를 찾으면 쉽게 해결이 되겠지만, 그렇게 되면 너무 많은 수에 대해서 검사를 해야 합니다. 여기서는 유클리드 방법에 의해서 최대 공약수를 찾고, 그 수를 가지고 곱을 해내가는 방식으로 알고리즘을 생각했습니다. 유클리드 방법에 의해서 최대공약수를 찾는 것은, 두 수중 작은 수 N에 대하여 O(log N)의 알고리즘으로 찾을 수 있습니다. 그러면 결국 20까지의 숫자를 N으로 표현한다면 O(N log N) 알고리즘으로 답을 찾을 수 있습니다. 가장 쉬운 알고리즘이라고 소개한 경우에는 답을 .. 2014. 12. 22.
728x90

티스토리툴바