반응형 프로젝트 오일러69 #74 자릿수 팩토리얼 연결 고리 10진수의 수를 각각의 자릿수를 분해해서 재조합하다보면 재미있는 수를 얻을 수 있습니다. 예를 들어서 145라는 수를 분해해서 팩토리얼을 취한후 합해보면, \(145 \to 1! + 4! + 5! = 1+24+120=145\)라는 결과를 얻게 됩니다. 이와 같이 같은 수가 나올 수 있지만, 어떤 수는 위의 작업을 반복하다보면, 자신의 수가 되기도 하고 중간에 나왔던 수가 되어 싸이클을 반복할 수도 있습니다. 이 문제는 이러한 수들의 연결고리가 반복되기 전까지 얼마나 오래 가는가에 대한 문제입니다. 난이도 15% 정도로 구현에 어려움이 없는 문제입니다. 문제의 링크입니다. https://projecteuler.net/problem=74 Problem 74 - Project Euler The number 1.. 2019. 12. 27. #73 범위안의 분수 세기 이 문제는 난이도 15% 정도의 문제입니다. 범위안의 분수를 세는 문제인데요. 프로젝트 오일러 #72 문제와 마찬가지로 분모의 범위가 주어지고, 그 안에서 1/3 와 1/2 사이의 분수의 갯수를 구하는 것입니다. 기약분수라는 조건이 달려있습니다. 즉, 1/3 와 1/2 사이에 2/5, 4/10, 6/15, .. 분수들이 있는데, 4/10, 6/15는 모두 2/5와 같은 분수이기 때문에 카운팅을 하면 안 됩니다. 프로젝트 오일러 #73 문제는 아래의 링크를 참조하세요. https://projecteuler.net/problem=73 Problem 73 - Project Euler Consider the fraction, n/d, where n and d are positive integers. If n p.. 2019. 12. 21. 프로젝트 오일러 #71 순서가 있는 분수 어려움 정도는 10%로 크게 어려움 없이 풀 수 있는 문제입니다. 분수문제가 연속으로 3문제가 나와있는데, 기약분수를 만드는 것만 잘 이해하면 풀 수 있는 문제들입니다. 아래는 이 문제의 원문이 있는 곳입니다. https://projecteuler.net/problem=71 Problem 71 - Project Euler Consider the fraction, n/d, where n and d are positive integers. If n projecteuler.net 분수를 표현하는 방법은 여러가지가 있을 수 있습니다. 그 중 유일한 표현법을 얻기 위해서 기약분수를 사용합니다. 기약분수로 표현을 할 때, 우리는 분수의 크기를 비교할 수 있죠. 그런데, 분모의 상한을 주게되면, 자연수를 나열하듯이 .. 2019. 11. 18. 프로젝트 오일러 #70 오일러의 수 순열 #69 문제와 비슷하게 이 문제도 오일러의 수를 다루고 있습니다. 난이도는 20%이네요. 문제 자체는 해석하는 데 있어서 어려움이 없습니다. n에 대한 오일러의 수가, n과 자릿수도 같고, 숫자의 조합도 같다면, 그 수는 순열수라고 할 수 있습니다. 이러한 순열수가 되는 10억 미만의 n 중에 그 비율이 최소가 되는, (즉, 상대적으로 오일러의 수가 크게 나오는) n을 찾으라는 것입니다. 이 문제를 #69와 같이 풀 수도 있겠지만요. 순열수가 되어야 한다는 조건 때문에, 일단 무식하게 프로그램을 짜보았습니다. 아쉽게도 무식하게 프로그램을 작성하면 시간이 많이 걸립니다. 전 12초정도 시간이 걸리네요. 순열수인지 아닌지는 9로 나눈 나머지가 동일한지 검사했습니다. 일단 그렇게 하면 많은 경우의 수가 줄어듭.. 2016. 9. 29. 프로젝트 오일러 #69 최대 오일러의 수 비율 이번 문제는 난이도 10%의 문제입니다. 사실 알고보면 어려운 문제는 아니지만, 오일러의 수라는 것에 대한 이해도가 없다면, 막막하게 느낄 수 있습니다. 오일러의 수는 어떤 수 n에 대하여, n보다 작을 자연수 중에, n과 서로소인 수의 갯수를 말합니다. 이 수는 암호학 등에서 아주 중요하게 다루어집니다. RSA와 같이 비대칭 키를 사용하는 암호학을 공부하고자 한다면, 오일러의 수를 이해하지 못 하면, 절대 해당 암호학을 이해할 수 없습니다. 대학에서 정수론이라는 과목을 들었다면 모를까, 그렇지 않다면, 배울 수 있는 기회는 별로 없죠. (요즘은 중학생들도 이것을 아는 애들이 있습니다. 수학 올림피아드에서 가끔씩 나오는 문제이다보니. 제 경우에는 정수론 책을 하나 사서 독학을 했습니다.) 문제에서는 n에.. 2016. 9. 27. 프로젝트 오일러 #152를 풀면서.. 프로젝트 오일러 #152를 풀면서 몇가지 새롭게 구현했던 것들이 많았네요. 기본적으로 모든 조합을 찾기 위해서는 $O(2^n)$인 탓에, 35, 45개일 때는 그나마 적정한 시간에 구할 수 있었지만, 80개에서는 그것이 안 되었네요. 이럴 때, 경우의 수를 줄여주는 것이 필요한데, 어떤 식으로 경우의 수를 줄일 것인지 고민을 많이 했네요. 더더구나 문제가 3의 배수는 총 26개나 나온다는 것이었죠. 처음에는 그룹을 지어서 할 생각이었는데.. 그룹을 지으면 전혀 안 되는 문제라는 사실을 조금 고민하면서 알게 되었네요. 회사에 있으면서도 어떻게 풀까 고민했었는데.. 결국 경우의 수를 줄이는 방법을 생각했고, 제 구닥다리 노트북에서도 0.1초에 답을 내었네요. 여러가지 연산시간을 줄이는 방법도 생각을 했었는데.. 2016. 7. 10. 이전 1 2 3 4 5 ··· 12 다음 728x90
