본문 바로가기
반응형

Programming/Project Euler89

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.
프로젝트 오일러 #0 시작하며 프로젝트 오일러가 요즘 프로그래머(아 제가 좀 늦었을지는 모르겠지만)들에게 인기가 있어서, 프로젝트 오일러를 조금 다른 시각으로 풀어볼려고 합니다. 벌써 문제가 몇백개가 되어놓아서, 이 연재는 과연 얼마나 오래 걸릴지는 잘 모르겠습니다. 일단, 제가 가장 중요하게 생각하는 것은 효율성입니다. for 루프 등을 이용하면 쉽게 만들 수 있는 프로그램이지만, 여기서는 가장 효율적인 프로그램을 이용해서 만들어볼려고 합니다. 물론 한계가 있어서 가장 효율적인 프로그램이 안 될 수도 있겠지만요. 오일러 프로젝트를 검색했더니, 답을 넣으면 풀 수 있는 사이트가 있네요.(영문 사이트 : https://projecteuler.net/, 한글 번역 사이트 : http://euler.synap.co.kr/)제가 다른 프로그.. 2014. 12. 18.
728x90