반응형 Project Euler41 프로젝트 오일러 #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. 프로젝트 오일러 #68 매직 오각 링 이 문제는 난이도 25%로 앞에 나열된 문제들에 비해서는 높은 편입니다. 매직 오각 링이라는 도형이 들어가는데, 이 도형만 잘 이해가 된다면 어려운 문제까지는 아닙니다. 위 그림은 매직 삼각 링입니다. 매직 삼각 링은 6개의 숫자가 있는데, 여기에 1 부터 6까지의 숫자를 채워넣게 됩니다. 그런데 여기에는 규칙이 있습니다. 일직선상의 세개 숫자의 합이 모두 같아야 합니다. 위 그림에서는 각 숫자들의 합이 9로 동일합니다. 이 그림이 매직 오각 링이며, 여기서 구해야할 문제입니다. 이 매직 오각 링에 들어갈 숫자는 1 부터 10까지의 숫자입니다. 이 숫자들을 세개의 숫자씩 시계방향으로 쭉 나열하면 총 15개의 숫자가 나옵니다. 그런데 10이란 숫자가 있으니까, 이 숫자들을 모두 붙이면, 16자리 또는 17.. 2016. 7. 4. 프로젝트 오일러 #67 최대 경로의 합 난이도는 5%로 별로 높지 않은 문제입니다. 그러나 A* 알고리즘 등 기초 알고리즘을 이용해서 짤 수 있는 문제이고, 또, 많은 게임 프로그램에서 활용 가능한 문제입니다. Maximum path sum II 어떤 한 곳에서 갈 수 있는 길은 2가지이므로, 높이가 10이면, 2의 9승인 512가지의 길이 존재합니다. 이 길 중 상당부분은 부분경로가 같기 때문에, 이러한 경로의 합을 구하는 방법으로는 동적프로그래밍(dynamic programming)이라는 알고리즘 기법을 이용해서 풀면 좋습니다. 동적 프로그래밍은 메모리를 추가로 사용해야 하지만, 저는 그냥 기존의 데이터 저장공간을 그대로 사용했습니다. 그렇게 하여도 큰 문제가 없겠죠. 중간에 한 지점에 대해서 올 수 있는 경로는 최대 2가지입니다. 그 2.. 2016. 6. 30. 프로젝트 오일러 #66 디오판투스 수식 이번 문제는 난이도 25% 문제이지만, 수학적인 부분을 모르면 매우 어렵습니다. 그냥 수식만 따라가서 풀려면, 풀기 힘든 문제예요. https://projecteuler.net/problem=66 Problem 66 - Project Euler Consider quadratic Diophantine equations of the form: x2 – Dy2 = 1 For example, when D=13, the minimal solution in x is 6492 – 13×1802 = 1. It can be assumed that there are no solutions in positive integers when D is square. By finding minimal solutions in proj.. 2016. 6. 29. 이전 1 2 3 4 5 ··· 7 다음 728x90
