본문 바로가기
반응형

Programming/Project Euler112

프로젝트 오일러 #70 오일러의 수 순열 #69 문제와 비슷하게 이 문제도 오일러의 수를 다루고 있습니다. 난이도는 20%이네요. 문제 자체는 해석하는 데 있어서 어려움이 없습니다. n에 대한 오일러의 수가, n과 자릿수도 같고, 숫자의 조합도 같다면, 그 수는 순열수라고 할 수 있습니다. 이러한 순열수가 되는 10억 미만의 n 중에 그 비율이 최소가 되는, (즉, 상대적으로 오일러의 수가 크게 나오는) n을 찾으라는 것입니다. 이 문제를 #69와 같이 풀 수도 있겠지만요. 순열수가 되어야 한다는 조건 때문에, 일단 무식하게 프로그램을 짜보았습니다. 아쉽게도 무식하게 프로그램을 작성하면 시간이 많이 걸립니다. 전 12초정도 시간이 걸리네요. 순열수인지 아닌지는 9로 나눈 나머지가 동일한지 검사했습니다. 일단 그렇게 하면 많은 경우의 수가 줄어듭.. 2016. 9. 29.
프로젝트 오일러 #69 최대 오일러의 수 비율 이번 문제는 난이도 10%의 문제입니다. 사실 알고보면 어려운 문제는 아니지만, 오일러의 수라는 것에 대한 이해도가 없다면, 막막하게 느낄 수 있습니다. 오일러의 수는 어떤 수 n에 대하여, n보다 작을 자연수 중에, n과 서로소인 수의 갯수를 말합니다. 이 수는 암호학 등에서 아주 중요하게 다루어집니다. RSA와 같이 비대칭 키를 사용하는 암호학을 공부하고자 한다면, 오일러의 수를 이해하지 못 하면, 절대 해당 암호학을 이해할 수 없습니다. 대학에서 정수론이라는 과목을 들었다면 모를까, 그렇지 않다면, 배울 수 있는 기회는 별로 없죠. (요즘은 중학생들도 이것을 아는 애들이 있습니다. 수학 올림피아드에서 가끔씩 나오는 문제이다보니. 제 경우에는 정수론 책을 하나 사서 독학을 했습니다.) 문제에서는 n에.. 2016. 9. 27.
프로젝트 오일러 #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.
[Python]프로젝트 오일러 #65 : 자연지수 e의 수렴(수학) 프로젝트 오일러 문제 #65는 연분수(continued fraction)와 관련된 문제입니다. 이 문제는 구체적으로 다음과 같습니다.자연수 \(e\) (오일러의 수)에 대한 연분수 전개는 다음과 같은 형태로 표현됩니다.e = [2; 1, 2, 1, 1, 4, 1, 1, 6, 1, 1, 8, 1, ...]여기서 중괄호 안의 숫자들은 연분수 전개의 요소들을 나타냅니다. 연분수의 번째 수렴값은 해당 요소들을 사용하여 얻을 수 있는 분수입니다. 예를 들어, \(e\)의 연분수의 초기 수렴값은 다음과 같습니다:• 첫 번째 수렴값: \(2\)• 두 번째 수렴값: \(\frac{3}{1}\)• 세 번째 수렴값: \(\frac{8}{3}\)이렇게 계속해서 수렴값이 점점 더 정확하게 \(e\)에 가까워집니다.문제 요구.. 2016. 6. 28.
728x90