mathematics21 [C/C++] 프로젝트 오일러 #508 : i−1 진법 표시하기(수학) 이번 문제는 아직까지도 푼 사람이 100명이 넘지 않는 문제네요. 그만큼 복잡할 수 있는 문제이므로, 블로그에 자세한 풀이법을 적기는 힘드네요. 문제는 주어진 범위안의 복소수를 i−1 진법으로 표현했을 때, 1의 갯수의 총 합입니다. 복소수에 보면, 정수가 계수인 복소수들이 자연수의 소수처럼 취급될 수 있는 것들이 있습니다. 이것들을 일반적으로 가우스 소수라고 합니다. 가우스 소수는 몇가지 법칙이 있는데요. 기본적으로 자연수의 소수에서 갈라지게 됩니다. 자연수의 소수 중 4k+3 형태의 소수는 자체로 가우스 소수가 됩니다. 즉, 3, 7, 11, 19, .. 등입니다. 그 외의 자연수 소수들은 모두 복소수 형태의 가우스 소수로 나누어지게 됩니다. 예를 들어서 소수 2는 \( \pm 1 \p.. 2015. 5. 2. [C/C++] 프로젝트 오일러 #28 : 회전하는 숫자들의 대각선 합 이 프로그램은 사실 원하는 배열을 잡고, 숫자를 배열한 후에 대각선의 합을 구해도 됩니다.그렇게 한다고 해서 시간이 엄청 걸리는 것도 아니니 말이죠. 그러나 처음 제가 이 프로젝트 오일러 글들을 쓰면서, 어떻게 하면 보다 빠르게 계산할 것인가를 고민했기 때문에, 이 문제 역시 복잡도를 낮추어 계산하도록 하였습니다. 1부터 N까지의 합, 제곱 합 등의 공식을 도출할 줄 안다면, 이 문제 역시 간단하게 하나의 식으로 만들 수 있습니다. 여기서는 다음과 같은 식이 나오게 됩니다. result=1+8n(n+1)(2n+1)3+2n(n+1)+4n 이 수식에 따라서 구한 프로그램은 다음과 같습니다.역시 이 프로그램은 참고용으로만 해주세요.//-----------.. 2015. 3. 4. [C/C++] 프로젝트 오일러 #5 : 1~20으로 나누어지는 가장 작은 자연수(수학) 문제의 난이도가 조금씩 높아져 가는 것을 느끼네요. 이번 문제는 효율성을 충분하게 발휘할 수 있는 문제입니다. 가장 쉬운 알고리즘으로는, 1부터 차례대로 모든 수에 대해서 1부터 20까지의 숫자로 나누어 떨어지는 첫번째 수를 찾으면 쉽게 해결이 되겠지만, 그렇게 되면 너무 많은 수에 대해서 검사를 해야 합니다. 여기서는 유클리드 방법에 의해서 최대 공약수를 찾고, 그 수를 가지고 곱을 해내가는 방식으로 알고리즘을 생각했습니다. 유클리드 방법에 의해서 최대공약수를 찾는 것은, 두 수중 작은 수 N에 대하여 O(log N)의 알고리즘으로 찾을 수 있습니다. 그러면 결국 20까지의 숫자를 N으로 표현한다면 O(N log N) 알고리즘으로 답을 찾을 수 있습니다. 가장 쉬운 알고리즘이라고 소개한 경우에는 답을 .. 2014. 12. 22. 이전 1 2 3 4 다음
