본문 바로가기
반응형

Programming/Project Euler89

프로젝트 오일러 #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.
프로젝트 오일러 #64 홀수 주기의 제곱근 프로젝트 오일러 #64 는 연분수로 제곱근을 표현하는 문제입니다. 문제의 난이도는 20%입니다. 알고리즘적으로 어려운 것보다는 수학적 개념의 어려움이 있었던 문제라고 봅니다. 제곱근을 연분수로 표현하는 문제는 #57번(http://sdev.tistory.com/237)에 이미 나왔었습니다. 문제의 링크는 아래와 같습니다. https://projecteuler.net/problem=64 연분수로 표현할 때, 중요한 점은 분자는 항상 1이 되어야 한다는 것입니다. 예를 들어서 7의 제곱근인 \( sqrt{7} \)은 다음과 같이 표현할 수 있습니다. \[ \sqrt{7} = 2 + \sqrt{7} - 2 \] 위 식은 너무나도 당연한 것이겠지만요. 우리는 이것을 이용해서 연분수를 만들 수가 있습니다. 일단 .. 2016. 6. 22.
프로젝트 오일러 #63 제곱수의 자릿수 세기 제곱수 문제이긴 하지만, 의외로 이 문제는 쉽습니다. 난이도도 5%입니다. 문제는 n자리의 수중에 어떤 수의 n제곱이 되는 수가 몇개나 존재할까입니다. 예를 들어서 \(16807=7^5\) 인데, 16807은 5자리의 수이고 7의 5제곱이 되는 수죠. 이 문제의 링크는 아래에 있습니다. https://projecteuler.net/problem=63 Problem 63 - Project Euler The 5-digit number, 16807=75, is also a fifth power. Similarly, the 9-digit number, 134217728=89, is a ninth power. How many n-digit positive integers exist which are also an.. 2016. 6. 21.
프로젝트 오일러 #62 세제곱수 순열 이번 문제는 난이도 15% 문제네요. 저는 의외로 쉽게 풀었습니다. (단순무식법으로요.) 서로 다른 세제곱수 5개가 같은 숫자들로 이루어진 경우 그 중 가장 작은 수를 구하라는 문제입니다. 사실 이 문제를 정석적으로 푼다면, 정확하게 5개가 나오는지 검사해야 하지만, 저는 그것까지는 검사하지 않았습니다. 또한 같은 숫자가 4개 이상 나오는 것도 배제했습니다. 사실 그러면 안 되지만, 배열에다가 데이터를 저장하는 방식을 이용하다보니, 같은 숫자가 4개 이상 나오면 안 되어서요. 해시를 쓰면 좀 더 나으려나요. 그러면 자릿수가 6자리인것, 7자리인것, .. 형태로 정확하게 5개가 나오면서, 같은 숫자가 4개 이상 나오는 것도 허용할 수 있었을텐데요. 그치만 복잡한 자료구조 쓰는 것을 귀찮아해서요. (아무래도.. 2016. 6. 20.
프로젝트 오일러 #61 순환하는 n각수 이 문제는 60번에 이어서 연속으로 난이도 20% 문제이지만, 제 경우에는 그렇게 어렵지 않게 풀었던 문제입니다. n각수 문제를 풀기 위해서는 n각수인 조건을 잘 검사하면 큰 무리가 없을 것이라 생각합니다. 이 문제는 두자릿수씩 겹치면서 순환하는 6개의 수가, 각각 3각수, 4각수, ..., 8각수가 되는 수열을 구하라는 것입니다. 3각수가 되는 4자리 수를 구한후, 뒤의 두자리수로 시작하는 4각수가 되는 수를 구하는 식으로 연결지어서 최종적으로 3각수의 첫두자리수로 끝나는 8각수를 만들면 됩니다. 제 경우에는 미리 n각수를 다 구한다음에, 해당수들이 순환하는지 검사하는 코드를 작성했습니다. 실제로 4자리 n각수가 많지는 않습니다. 모든 n각수는 2차식이기 때문에 상당히 빠르게 숫자가 커집니다. #inc.. 2016. 6. 18.
프로젝트 오일러 #60 소수쌍 집합 이번 문제는 처음으로 난이도 20%짜리 문제입니다. 소수쌍이라고 해서 특별한 수학적인 내용이 들어가 있는 것은 아닙니다. 3, 7 이 두개의 소수가 있다고 하면, 이 두개의 소수를 단순하게 이어서 37, 73을 만들었을 때, 이 수들도 소수가 되면, (3, 7)은 소수쌍이 되는 것입니다. 이러한 소수들은 무한히 존재하겠지만, 빈도가 많지는 않습니다. 이 문제를 풀기 위해서는 메모리를 사용해서 해당되는 셋들을 만들것인가가 중요했습니다. 그렇게 하려면, 너무 자료구조가 복잡해서, 약간의 꼼수를 사용했습니다. 일단, 소수들을 결합하기 위한 재료는 미리 저장을 해놓고, 소수들을 결합한 결과에 대한 소수 검사는 별도의 라이브러리를 이용했습니다. 그리고 min이라는 정적 변수를 두어서, 이 값을 이용해서 현재 구해.. 2016. 6. 17.
728x90