본문 바로가기
반응형

프로젝트 오일러69

14. 프로젝트 오일러 #14 : 최대 체인을 가지는 우박수 구하기 이번 문제는 동적 프로그래밍을 이용해서 작성을 하는 것이 가장 좋을 듯 합니다. 우박수를 구하다보면, 이미 전에 계산했던 우박수 체인수가 있을 수 있습니다. 그렇게 하지 않으면, 체인수가 100여개 있는데, 1,000,000까지 구한다면, 1억번정도 평균적으로 계산해야 합니다. 동적 프로그래밍을 이용하면, 이 수를 줄일 수 있습니다. 물론 수가 1이 된다는 가정하에서 이야기지만, 현재까지 예외는 없으니까요. 사실 수학적으로 1,000,000까지 우박수가 된다는 것을 확인하면, n/2로 건너뛰기를 하기 때문에 반드시 우박수가 될 수밖에 없습니다. 순수한 수학적인 증명만으로는 할 수 없지만요. 물론, 자꾸 홀수에 걸쳐서 숫자가 비대해질 수는 있습니다만, 3n+1 은 반드시 짝수가 되기 때문에 홀수가 연달아 .. 2014. 12. 30.
13. 프로젝트 오일러 #13 : BigInt 수의 합 구하기 사실 이번 문제는 꼼수로 푸는 것이 맞을 듯 합니다. BigInt 라이브러리를 이용해서 풀어도 되겠지만, 그렇게 하면 시간이 많이 걸리죠. 앞자리부터 10자리 숫자만 구하면 되는 것이니까요. 그렇게 하면 int형으로는 위험할지 몰라도 int64형으로는 충분한 자릿수가 됩니다. 32비트 자료형은 10의 9승정도를 표현할 수 있으니까요. 64비트는 10의 19승까지 표현할 수 있죠. 여기에 소스만 올리도록 할께요. 특별하게 설명할 일은 없는 듯 합니다. #include int main() { char *s = "37107287533902102798797998220837590246510135740250" "46376937677490009712648124896970078050417018260538" // 데이터.. 2014. 12. 30.
12. 프로젝트 오일러 #12 : 500개 초과 삼각수 구하기 이번 문제는 삼각수에 대한 것입니다. 간단한 중학수학 수준만 알고 있다면, 이 문제를 좀 빠르게 풀 수 있을 것이라 생각합니다. 1~n 까지의 합은 다음과 같은 식으로 구할 수 있습니다. 그 다음은 약수들의 갯수를 구하는 방법입니다. 예를 들어서 12의 약수의 갯수는 다음과 같이 계산할 수 있습니다. 이것만 알아도, 보다 쉽게 약수의 갯수를 구할 수 있습니다. 조금 더 나아간다면, n과 n+1은 서로소관계이므로, 을 적용할 수 있습니다. 그래서 n이 짝수인 경우와 홀수인 경우로 나누고, 동적 프로그래밍을 이용하면, 빠르게 원하는 답을 얻을 수 있습니다. 프로젝트 오일러 사이트에 가보면, 어떤분은 수십초가 걸렸다고 하는데요. 제 경우에는 노트북에 가상머신을 잡고 리눅스를 돌렸는데, time으로 실행시간을 .. 2014. 12. 29.
#11 : 그리드에서 가장 큰 곱수 구하기(Brute Force) 이번 문제는 사실 효율적인 알고리즘을 찾기가 어렵네요. 난이도 5%로 아주 쉬운 문제로 평가되어 있는 문제입니다. 탐욕 알고리즘을 이용해서 풀어볼려고 시도를 했는데, 탐욕 알고리즘이 늘 최선의 결과를 내는 것이 아니고, 오히려 정렬하는 시간 때문에 속도 향상을 기대하기 힘드네요. 400개의 데이터를 정렬하는 것 자체가, 순차적으로 모든 곱을 계산하는 것보다 기본적으로 점근적 접근상 더 큰 값을 가지니까요. 효율로 따져서 득 될 것이 없다고 생각했습니다. 제가 처음에 생각했던 탐욕 알고리즘은, 가장 큰 수부터 차례대로 근처에 있는 곱을 계산하고, 현재의 최대값이 다음 가장 큰수의 네제곱수보다 크다면, 거기서 종료하는 방법이었습니다. 이 알고리즘으로 한다면, 제일 큰 곱수를 구할 수 있습니다만, 과연 이게 .. 2014. 12. 28.
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.
728x90

티스토리툴바