콘텐츠로 건너뛰기
Home » 스터디 » Page 9

스터디

오일러 프로젝트 70

어느덧 오일러 프로젝트 풀이를 포스팅한게 70번째에 다다랐다. 점점 강려크한 난이도의 문제들이 나오면서 한 회 한 회 포스팅이 정말 쉽지 않다. 오일러 프로젝트 70 번 문제도 오일러 피(phi) 함수에 대한 내용이다. 이번에는 피함수의 값이 원래 값과 순열이 되는 조금 특별한 케이스를 찾는 문제이다.
더 보기 »오일러 프로젝트 70

오일러 프로젝트 68

아래와 같이 바방진과 유사한 성질을 가진 도형이 있습니다. 1부터 6까지의 숫자가 한 번씩만 사용되었고, 선을 따라 합을 구하면 항상 9가 됩니다.

바깥으로 뻗친 가지 중에서 가장 숫자가 낮은 것부터 시작해서 직선들을 시계 방향으로 돌아가며 나열하면, 도형의 모양을 숫자로 나타낼 수 있습니다. 위 그림의 예를 들면 4,3,2; 6,2,1; 5,1,3 이 됩니다.

위 도형으로는 네 가지 다른 합계를 가지도록 배열할 수 있는데, 다음과 같은 여덟개의 풀이가 존재합니다.

  • 합계 9 : 4,2,3; 5,3,1; 6,1,2
  • 합계 9 : 4,3,2; 6,2,1; 5,1,3
  • 합계 10 : 2,3,5; 4,5,1; 6,1,3
  • 합계 10 : 2,5,3; 6,3,1; 4,1,5
  • 합계 11 : 1,4,6; 3,6,2; 5,2,4
  • 합계 11 : 1,6,4; 5,4,2; 3,2,6
  • 합계 12 : 1,5,6; 2,6,4; 3,4,5
  • 합계 12 : 1,6,5; 3,5,4; 2,4,6

하나의 풀이에 대해서 각 숫자를 모두 이어 붙이면 9자리의 숫자를 만들 수 있고, 그 중에서 가장 큰 것은 432621513이 됩니다.
이제 아래와 같은 도형에다 마방진의 성질을 가지도록 1부터 10까지의 숫자를 채우고, 같은 방식으로 풀이 숫자를 이어붙이면 16자리 혹은 17자리의 숫자가 만들어집니다. 이 때, 16자리 숫자 중에서 가장 큰 것은 무엇입니까?

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

람다표현식과 맵, 필터, 리듀스 (Python)

람다(lambda, )는 본래 수리논리학에서의 함수정의를 추상화한 형식 체계로, 간단히 말해서 이름이 없는 함수 혹은 인라인으로 정의하는 함수로 이해할 수 있다. 수학에서의 람다대수의 정의와 비슷하게 파이썬에서는 다음과 같이 람다함수를 정의한다. lambda {파라미터,…} : {표현식} 람다식은 그 자체로 표현식이며 다음 구성 요소로 작성한다. 키워드 lambda 파라미터 : 컴마로 구분되는 1개 이상의 파라미터. 파라미터는 반드시 1개 이상이어어야 한다. 콜론 : 표현식 : 파라미터와 그외 값으로 이루어지는 일련의 표현식 예를 들어 어떤 파라미터 x 에 대해서 1을 증가시킨 값을 구하는 함수는 람다대수로는 이라고 표현하며,… 더 보기 »람다표현식과 맵, 필터, 리듀스 (Python)

오일러 프로젝트 67

아래와 같은 삼각형의 꼭대기에서 인접한 수를 따라 내려가는 경로의 합을 계산해보면, 붉은 색으로 표시한 경우가 3 + 7 + 4 + 9 = 23 으로 가장 큽니다.

텍스트 파일 triangle.txt에는 100줄짜리 삼각형 수 데이터가 들어있습니다. 꼭대기에서 바닥에 이르는 경로의 합 중 최댓값은 얼마입니까?

참고: 이 문제는 18번 문제와 비슷하지만 훨씬 더 어려운 버전입니다. 이 문제를 풀려고 모든 경로를 계산하는 것은 가능하지 않은데, 경우의 수가 모두 299나 되기 때문입니다. 일 초에 1조(1012)개의 경로를 계산할 수 있다고 해도, 모든 경우의 수를 계산하려면 200억년이 걸립니다. 이 문제를 해결할 수 있는 효율적인 알고리듬을 찾아보시기 바랍니다.

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

하스켈에서 메모이제이션 구현하기

하스켈의 메모이제이션 하스켈의 함수는 순수함수이고, 이는 입력이 같다면 항상 같은 결과가 리턴되는 것을 보장한다. 이는 어떤 임의의 함수 f와 그 인자 x가 있을 때 최초 f(x)가 계산되고 나면 그 이후에 f(x)가 필요한 경우에 불필요한 반복 계산이 필요하지 않은 것 처럼 들린다. (왜냐면 f(x)는 이미 이전에 계산되어 값으로 축약되었고, 그 사이에 어떤 일이 있었든지 간에 같은 인자에 대해서는 하스켈의 함수는 같은 결과를 내놓을 것이기 때문이다.) 하지만 이것은 다른 문제이다. 이는 하스켈이 기본적으로 모든 함수 적용 연산에 대해 그 결과를 캐싱한다는 이야기인데,… 더 보기 »하스켈에서 메모이제이션 구현하기

오일러 프로젝트 66

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

Pages: 1 2

LCD 패널 방식으로 숫자를 표시해보기 (파이썬)

LCD 처럼 숫자를 표시하는 코드를 만들어 보자 크기와 출력할 숫자를 입력받는다. 크기는 LCD 표시 요소 하나의 크기를 가리킨다. (크기는 1~10,  숫자는 0~99,999,999)  가로선은 -, 세로선은 | 문자를 통해서 표현하며, 사이즈만큼 길이가 길어진다. 따라서 하나의 문자를 표시하기 위해서는 가로는 size + 2, 세로는 size * 2 + 3 만큼의 공간이 필요하다. 예시 – 출력: 0123456789. size: 3 — — — — — — — — | | | | | | | | | | | | | | | |… 더 보기 »LCD 패널 방식으로 숫자를 표시해보기 (파이썬)

오일러 프로젝트 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