콘텐츠로 건너뛰기
Home » 스터디 » Project Euler » 페이지 3

Project Euler

오일러 프로젝트의 문제 풀이. 주로 파이썬과 Swift로 풀이합니다. (Python 3.6, Swift 4.0)

오일러 프로젝트 66

오일러 프로젝트 66번 문제는 펠 방정식의 최소해에 관한 문제이다. 나이브하게 접근했다가는 결코 풀어낼 수 없을 수준으로 시간이 많이 걸린다. 그리고 그나마 빠른 해법 역시 구현하기 위해 여러 가지 지식과 스킬이 동원된다.  접근 방법을 알고 있더라도 구현이 만만치 않은, 1번부터 현재까지는 최고 난이도의 문제라 할 수 있다. 통상 오일러 프로젝트의 문제들은 순서에 맞게 풀어나갈 필요는 없지만, 이 문제 만큼은 57번, 64번, 65번을 풀 때의 지식이 그대로 요구된다.
더 보기 »오일러 프로젝트 66

Pages: 1 2

오일러 프로젝트 65

제곱근 2는 아래와 같이 연분수의 꼴로 나타낼 수 있습니다.

연분수에서 이렇게 끝없이 반복되는 부분은 √2 = [1;(2)]처럼 나타낼 수 있는데, 여기서 (2)는 숫자 2가 반복됨을 뜻합니다. 같은 방법으로 √23은 [4;(1,3,1,8)]이 됩니다. 이 연분수의 부분 합을 구하면, 해당 제곱근의 훌륭한 근사값으로 쓸 수 있습니다.. √2의 수렴 과정을 한 번 보겠습니다.

이런 식으로 처음 10번에 해당하는 값은 다음과 같이 됩니다.

정말 놀라운 사실은 가장 중요한 수학 상수 중 하나인 e가 다음과 같은 연분수 꼴로 나타내어진다는 것입니다.

e = [2;1,2,1,1,4,1,1,6,1,…, 1,2k,1…]

이 경우 수렴 과정의 처음 10번은 이렇습니다.

여기서 열 번째 값의 분자 자릿수를 모두 더하면 1+4+5+7 = 17이 되는 것을 알 수 있습니다. 그러면 e의 100번째 연분수 확장 값의 분자 자릿수를 모두 더하면 얼마가 됩니까?

더 보기 »오일러 프로젝트 65

오일러 프로젝트 64

제곱근을 연분수로 나타날 때 반복 주기가 홀수인 경우 세기

모든 제곱근은 아래와 같이 연분수로 나타낼 수 있는데, 이 때 반복되는 부분이 나타납니다.

\sqrt{N} = a_0 + \frac{1}{ a_1 + \frac{1}{a_2 + \frac{1}{a_3 + \cdots}}}

예를 들어서 √23을 풀어 보면,

\sqrt{23} = 4 + (\sqrt{23} - 4) = 4 + \frac{1}{(\frac{1}{\sqrt{23} - 4})} = 4 + \frac{1}{\frac{\sqrt{23} + 4}{7}} = 4 + \frac{1}{1 + \frac{\sqrt{23} - 3}{7}}

같은 식으로 계속하면 아래와 같은 모양이 됩니다.

\sqrt{23} = 4 + \frac{1}{1 + \frac{1}{3 + \frac{1}{1 + \frac{1}{8 + \cdots}}}}

이 과정을 상세히보면 다음과 같습니다.

\begin{array}{llll}
a_0 = 4, & \frac{1}{\sqrt{23} - 4} = \frac{\sqrt{23} + 4}{7} = 1 + \frac{\sqrt{23} - 3}{7} \\
a_1 = 1, & \frac{7}{\sqrt{23} - 3} = \frac{7(\sqrt{23} + 3)}{14} = 3 + \frac{\sqrt{23} - 3}{2} \\
a_2 = 3, & \frac{2}{\sqrt{23} - 3} = \frac{2(\sqrt{23} + 3)}{14} = 1 + \frac{\sqrt{23} - 4}{7} \\
a_3 = 1, & \frac{7}{\sqrt{23} - 4} = \frac{7(\sqrt{23} + 4)}{7} = 8 + \sqrt{23} - 4 \\
a_4 = 8, & \frac{1}{\sqrt{23} - 4} = \frac{2(\sqrt{23} + 4)}{7} = 1 + \frac{\sqrt{23} - 3}{7} \\
a_5 = 1, & \frac{7}{\sqrt{23} - 3} = \frac{7(\sqrt{23} + 3)}{14} = 3 + \frac{\sqrt{23} - 3}{2} \\
a_6 = 3, & \frac{2}{\sqrt{23} - 3} = \frac{2(\sqrt{23} + 3)}{14} = 1 + \frac{\sqrt{23} - 4}{7} \\
a_7 = 1, & \frac{7}{\sqrt{23} - 4} = \frac{7(\sqrt{23} + 4)}{7} = 8 + \sqrt{23} - 4 \\
\end{array}

위에서 보듯이 4라는 정수부 다음에 1, 3, 1, 8 이라는 숫자가 무한히 반복되는데, 이것을 을 √23 = [4;(1,3,1,8)] 과 같이 표시하기로 합니다. 이런식으로 해서 무리수인 제곱근들을 연분수로 나타내면 다음과 같이 됩니다.

√2=[1;(2)], 주기=1
√3=[1;(1,2)], 주기=2
√5=[2;(4)], 주기=1
√6=[2;(2,4)], 주기=2
√7=[2;(1,1,1,4)], 주기=4
√8=[2;(1,4)], 주기=2
√10=[3;(6)], 주기=1
√11=[3;(3,6)], 주기=2
√12=[3;(2,6)], 주기=2
√13=[3;(1,1,1,1,6)], 주기=5

반복주기가 홀수인 경우는 N ≤ 13 일 때 모든 4번 있음을 볼 수 있습니다. 그러면 N ≤ 10000 일 때 반복 주기가 홀수인 경우는 모두 몇 번이나 있습니까?

https://euler.synap.co.kr/problem=64
더 보기 »오일러 프로젝트 64

오일러 프로젝트 62

세제곱수인 41063625(=3453)로 순열을 만들어 보면 그 중에서 56623104(=3843)와 66430125(=4053)가 또 세제곱수입니다. 실제 41063625는, 자릿수로 만든 순열 중에서 3개가 세제곱수인 가장 작은 수입니다.

그러면 자릿수로 만든 순열 중에서 5개가 세제곱수인 가장 작은 숫자는 무엇입니까?

https://euler.synap.co.kr/problem=62
더 보기 »오일러 프로젝트 62

오일러 프로젝트 61

삼각수, 사각수, 오각수 같은 다각수들은 아래의 공식으로 만들 수 있습니다.

  • 삼각수 – P3n = n * ( n + 1) / 2 >> 1, 3, 5, 10, 15, …
  • 사각수 – P4n = n * n >> 1, 4, 9, 16, 25, …
  • 오각수 – P5n = (n * ( n * 3 – 1)) / 2 > 1, 5, 12, 22, 35, …
  • 육각수 – P6n = (n * (n * 2 – 1)) > 1, 6, 15, 28, 45, …
  • 칠각수 – P7n = ((n * (n * 5 – 3)) / 2 > 1, 7, 18, 34, 55, …
  • 팔각수 – P8n = n * (n * 3 – 2) > 1, 8, 21, 40, 65, …

그런데 4자리 숫자 8128, 2882, 8281 (순서대로 각각 3, 5, 4각수)에는 재미있는 성질이 있습니다. 먼저 각 숫자들은 두 자리씩 꼬리를 물고 진행합니다. 그리고 각 숫자들은 모두 서로 다른 다각수입니다. 이런 성질을 갖는 네자리 숫자 세 개는 이들이 유일합니다. 이렇게 순환하면서 서로 다른 다각수가 되는 4자리 숫자 여섯개의 유일한 순서쌍을 찾고 그 합을 구하세요.

더 보기 »오일러 프로젝트 61

오일러 프로젝트 60

네 개의 소수 3, 7, 109, 673은 상당히 특이한 성질이 있습니다. 넷 중에 아무것이나 두 개를 골라서 어떤 쪽으로 이어붙이던지 그 결과도 소수가 됩니다. 예를 들어 7과 109를 고르면 1097, 7109 모두 소수입니다. 2, 7, 109, 673은 이런 성질을 가진 네 소수 중에서 그 합이 792로 가장 작습니다. 다섯 소수 중에 어떤 두 개를 골라 이어붙여도 소수가 되는 수들을 찾아서 그 합의 최소값을 구하세요.

더 보기 »오일러 프로젝트 60

오일러 프로젝트 59

컴퓨터상의 모든 문자들은 유일한 코드값에 대응되는데, 보통 ASCII 표준이 널리 쓰입니다. 예를 들면 대문자 A는 65, 별표(‘*’)는 42, 소문자 k는 107이라는 값을 가집니다.

현대적인 암호화 기법 중에, 텍스트 파일의 내용을 ASCII 코드로 바꾸고 각 바이트를 비밀키의 값으로 XOR 시키는 것이 있습니다. 이 방법의 장점은 암호화와 복호와에 동일한 키를 사용할 수 있다는 것입니다. 예를 들어 65 XOR 42 = 107 이고, 107 XOR 42 = 65가 됩니다. 암호문을 절대 깰 수 없도록 하려면, 암호화할 문장의 길이와 같은 무작위의 비밀키를 만들면 됩니다. 암호문과 비밀키는 따로따로 보관해둬야 하고, 그 반쪽짜리 정보 2개를 함께 확보하지 않는 한 해독은 불가능합니다.

하지만 이 방법은 대부분의 경우 실용적이지 못하므로, 원문보다 짧은 비밀키를 사용하게 됩니다. 이런 경우 비밀키는 전체 메시지에 대해서 반복적으로 돌아가며 적용됩니다. 이 때 키의 길이는 보안상 충분할 정도로 길어야 하지만 또한 쉽게 기억할 수 있을 정도로 짧아야 한다는 미묘한 균형이 요구됩니다.

이번 문제를 위해서 준비한 암호화 키는 단 3개의 영어 소문자이고, cipher1.txt 파일에 암호화된 ASCII 코드값이 들어있습니다. 원래의 메시지는 평범한 영어 문장임을 힌트로 삼아서 암호문을 해독하고, 원문에 포함된 ASCII 코드값의 총합을 구하세요.

http://euler.synap.co.kr/prob_detail.php?id=59
더 보기 »오일러 프로젝트 59

오일러 프로젝트 58

숫자를 1부터 시작해서 하나씩 늘려나가며 아래와 같이 시계반대방향으로 감아가면 한 변의 크기가 7인 정사각형 소용돌이가 만들어집니다. 우하단 대각선쪽으로 홀수 제곱수(9, 25, 49)들이 늘어서 있는 것이 눈에 띕니다만, 더 흥미로운 사실은 양 대각선상에 놓인 13개의 숫자 중 8개가 소수라는 점입니다. 그 비율은 대략 8/13 ≈ 62% 정도가 됩니다. 이런 식으로 계속 소용돌이를 만들어갈 때, 양 대각선상의 소수 비율이 처음으로 10% 미만이 되는 것은 언제입니까? 정사각형 한 변의 크기로 답하세요.

http://euler.synap.co.kr/prob_detail.php?id=58
더 보기 »오일러 프로젝트 58

오일러 프로젝트 57

오일러 프로젝트 57 번 문제는 2의 제곱근을 연분수 형태로 전개하는 것을 단계별로 진행할 때, 각 단계를 기약분수 형태로 만들어서 분자와 분모의 숫자 자리수를 비교하는 문제이다. 일단 자리 수가 엄청나게 커지는 관계로 쉬운 문제는 아니다.
더 보기 »오일러 프로젝트 57

오일러 프로젝트 56

구골(googol)은 10100을 일컫는 말로, 1뒤에 0이 백개나 붙는 어마어마한 수입니다. 100100은 1뒤에 0이 2백개나 붙으니 상상을 초월할만큼 크다 하겠습니다. 하지만 이 숫자들이 얼마나 크건간에, 각 자리수를 모두 합하면 둘 다 겨우 1밖에 되지 않습니다. a, b가 100보다 작은 자연수일 때, ab에 대해서, 자릿수의 합이 최대인 경우, 그 값은 얼마입니까?

http://euler.synap.co.kr/prob_detail.php?id=55
더 보기 »오일러 프로젝트 56