책 이야기

Consider the fraction, n/d, where n and d are positive integers. If n<d and HCF(n,d)=1, it is called a reduced proper fraction.

If we list the set of reduced proper fractions for d ≤ 8 in ascending order of size, we get:

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

It can be seen that 2/5 is the fraction immediately to the left of 3/7.

By listing the set of reduced proper fractions for d ≤ 1,000,000 in ascending order of size, find the numerator of the fraction immediately to the left of 3/7.

n과 d가 양의 정수인 분수 n/d를 생각해 보자. n<d이고 HCF(n,d)=1인 경우, 약분된 진분수라 부른다.

d가 8보다 작거나 같은 경우 크기가 커지는 순서로 약분된 진분수 목록을 구하면 다음과 같다.

1/8, 1/7, 1/6, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 5/6, 6/7, 7/8

여기에서 2/5는 3/7의 바로 왼쪽에 있는 것을 알 수 있다.

1,000,000 이하의 약분된 진분수를 크기가 커지는 순서로 나열할 때 3/7의 바로 왼쪽에 있는 분수의 분자는 무엇인가?

--------------------------------------------------------------------------

문제에서 요구하는 것을 다시 풀어보면, 분자가 분모보다 작고, 분자, 분모의 최대공약수가 1인 경우 약분된 진분수라 부른다고 정의하고 있으며, 진분수를 크기대로 나열했을 때, 3/7보다 작은 수가 무엇인지 물어보고 있다.

오래간만에 구현하기 간단한 문제가 나와 처음에는 분모가 2~1,000,000일때 까지의 약분된 진분수의 목록을 (분자, 분모, 나눈값)으로 구해서, 그것을 정렬하고, 3/7 바로 앞의 값을 찾는 형태로 구현했는데, 문제에서 제시한 예시를 구현했을 때에는 금방 동작했지만, 분모가 1,000,000일 때 까지 구하도록 하니 파이썬에서 처음 보는 '메모리 에러' 메시지와 함께 중단되었다. 진분수의 목록을 구하는 라인에서 에러가 발생한 것을 보니 수백만 개의 값이 있는 목록을 만드는 것에서 문제가 생긴 것 같다.

그래서, 각 분모값에 대해 분자를 1부터 키워나가면서 3/7에 근접하게 되는 값을 구하도록 접근 방법을 바꿨다. 리스트를 쓰지 않고 단순 계산만 하도록 몇 줄의 코드로 구현되어서 금방 값을 구할 것으로 예상했는데 실행 시간은 생각보다 너무 오래 걸려서 알고리즘 개선이 필요했다.

고민을 해 보니 분모가 커질수록 분자를 1부터 키워나가면서 3/7에 근접하는 값을 구하는 것에서 시간이 많이 소요되는 것을 찾아냈다. 분자가 시작하는 위치를 1에서 답에 가까운 것으로 바꾸었더니 1일 이상 필요할 것으로 예상되었던 시간이 줄어들어 4초 이내에 답을 구할 수 있었다. 더 빠르게 결과를 구하도록 개선 가능하겠지만 일단 이정도에서 만족하기로 했다.

정답 판정 화면에서 해결 과정을 구체적으로 쓰지 말기를 당부하면서 100번 이후 문제를 스포일하면 계정을 잠그겠다고 되어 있다. 해결과정을 조금 더 간결하게 써야겠다.

We hope that you enjoyed solving this problem. Please do not deprive others of going through the same process by publishing your solution outside of Project Euler. Members found to be spoiling problems beyond the first one-hundred problems will have their accounts locked.

If you are keen to share your insights and/or wish to see how other members have solved the problem, then please visit thread 71 in our private discussion forum.

By replacing the 1^st digit of the 2-digit number *3, it turns out that six of the nine possible values: 13, 23, 43, 53, 73, and 83, are all prime.

By replacing the 3^rd and 4^th digits of 56**3 with the same digit, this 5-digit number is the first example having seven primes among the ten generated numbers, yielding the family: 56003, 56113, 56333, 56443, 56663, 56773, and 56993. Consequently 56003, being the first member of this family, is the smallest prime with this property.

Find the smallest prime which, by replacing part of the number (not necessarily adjacent digits) with the same digit, is part of an eight prime value family.

2자리 숫자 *3의 첫번째 자릿수를 바꾸면 가능한 9개의 값 중 6개인 13, 23, 43, 53, 73, 83이 소수이다.

56**3의 3번째, 4번째 자릿수를 같은 숫자로 바꾸면, 가능한 10개의 값 중 5개(56003, 56113, 56333, 56443, 56663, 56773, 56993)가 소수가 되는 최초의 숫자이다. 따라서, 56003은 이러한 속성을 가지는 숫자 중 가장 작은 소수이다.

같은 자리의 숫자 일부를 바꿔(인접한 숫자일 필요 없음) 8개의 소수를 만드는 가장 작은 소수는 무엇인가?

--------------------------------------------------------------------------

문제를 보고 가장 난감했던 부분은 대상 숫자의 자릿수가 없고, 몇 개의 숫자를 바꿀 것인지 없으며, 어느 자리를 바꿀 것인지에 대한 힌트도 없는데 8개의 소수를 만들어내는 숫자를 찾으라는 것이었다. 짝수는 소수가 아니므로 8개를 만들기 위해서는 1의 자리 숫자를 바꾸지 않는 것은 확실한데 다른 숫자는 엄두가 나지 않았다.

몇 번의 반복문을 통해 해결했는데, 전체 자릿수를 두고, 바꾸면서 들어갈 숫자가 몇자리인지 정하고, 고정되게 들어갈 숫자를 반복하게 하고, 조합(combinations)을 이용해 바꾸면서 숫자가 들어갈 자리를 반복하고, 각 자리에 0~9를 대입하여 그 중 소수가 몇 개인지 찾도록 하였다.

반복되는 부분이 많고, 반복문이 독립적이지 않고 앞의 반복문에 연동되고(6자리 숫자인데 바꾸면서 들어갈 숫자가 2자리이면 고정되게 들어갈 숫자는 4자리), 파이썬의 특징을 살리지 못하는 전통적인 방식으로 코딩을 하다 보니 생각보다 코딩은 복잡했는데 답은 구할 수 있었다.

앞의 반복문에 연동되는 범위 계산을 잘못해서 오답을 구한 덕분에, 프로그램을 구성하는 시간만큼 수정하는 시간이 필요했다.

By starting at the top of the triangle below and moving to adjacent numbers on the row below, the maximum total from top to bottom is 23.

3
7 4
2 4 6
8 5 9 3

That is, 3 + 7 + 4 + 9 = 23.

Find the maximum total from top to bottom in triangle.txt (right click and 'Save Link/Target As...'), a 15K text file containing a triangle with one-hundred rows.

NOTE: This is a much more difficult version of Problem 18. It is not possible to try every route to solve this problem, as there are 2⁹⁹ altogether! If you could check one trillion (10⁹⁹) routes every second it would take over twenty billion years to check them all. There is an efficient algorithm to solve it. ;o)

아래 삼각형의 정상에서 시작하여 다음 줄의 인접한 숫자로 이동할 때, 정상에서 끝까지 가장 큰 합계는 23이다.

3
7 4
2 4 6
8 5 9 3

즉, 3 + 7 + 4 + 9 = 23 이다.

100개 줄이 있는 15K 크기의 triangle.txt (우클릭하고 "(으)로 링크 저장")에서 정상에서 끝까지 가장 큰 합계를 구하시오.

주의: 이것은 Problem 18의 훨씬 어려운 버전이다. 2⁹⁹ 개의 경로가 있으므로, 이 문제를 해결하기 위해 모든 경로를 확인하는 것은 불가능하다! 1초에 1조(10⁹⁹)개의 경로를 검사할 수 있으면 모든 경로를 검사하는 데 200억 년 이상 소요된다. 이 문제를 풀기 위해 더 효율적인 알고리즘이 필요하다. ;o)

--------------------------------------------------------------------------

18번 문제를 해결할 때 사용한 방법으로 해결하였다. 문제는 top-down 방식으로 물어봤지만, 해결은 bottom-up 방식으로 아래에서 올라가는 전략을 선택하는 것이다.

예를 들어 3번째 줄을 기준으로 보면, 2는 8과 5중 8이 크므로 둘을 합한 10, 4는 5와 9중 9가 크므로 13, 6은 9와 3중 9가 크므로 15, 이런 식으로 정상에 도달할 때까지 계산해 나가면 가장 큰 경로를 적은 시간으로 구할 수 있다.

A unit fraction contains 1 in the numerator. The decimal representation of the unit fractions with denominators 2 to 10 are given:

    1/2=0.5

    1/3=0.(3)

    1/4=0.25

    1/5=0.2

    1/6=0.1(6)

    1/7=0.(142857)

    1/8=0.125

    1/9=0.(1)

    1/10=0.1

Where 0.1(6) means 0.166666⋯, and has a 1-digit recurring cycle. It can be seen that 1/7 has a 6-digit recurring cycle.

Find the value of d<1000 for which 1/d contains the longest recurring cycle in its decimal fraction part.

분자가 1인 분수를 단위 분수(unit fraction)이라 한다. 분모가 2에서 10인 단위 분수는 다음과 같이 10진수로 나타낼 수 있다:

    1/2=0.5

    1/3=0.(3)

    1/4=0.25

    1/5=0.2

    1/6=0.1(6)

    1/7=0.(142857)

    1/8=0.125

    1/9=0.(1)

    1/10=0.1

0.1(6)은 0.166666⋯을 의미하고, 1자리의 반복 사이클을 가지고 있다. 1/7은 6자리의 순환마디가 있음을 알 수 있다. d<1000일 때, 1/d이 가장 긴 순환마디를 가지는 d를 찾으시오.

--------------------------------------------------------------------------

분수 값에서 순환소수 값을 구하는 방법을 알면 쉽게 풀 수 있고, 이것은 초등학교 산수 수준의 문제인 것 같기는 한데 어떻게 구하는 지 전혀 아이디어가 떠오르지 않아 보류하고 지나갔던 문제이다.

다시 봐도 아이디어가 떠오르지 않아 분수를 순환소수로 구하는 요령을 인터넷으로 검색하고 그것을 파이썬 코드로 만들어서 답을 구할 수 있었다. 9를 계속 만들어가면서 나눠지면 그 때 있는 9의 갯수가 순환마디의 크기를 뜻하는 것이 되는데, 예를 들어, 분모가 6일 때 90을 나눌 수 있고, 이 때 9는 1개 있으므로 순환마디는 1이고, 분모가 7일 때 999999을 나눌 수 있고, 이 때 9가 6개 있으므로 순환마디 6이 된다.

2~999까지의 반복문 안에, 9의 갯수(순환마디)를 찾는 2개의 반복문으로 구성해서 문제를 풀었고, 답을 구하는데 28초가 걸려 그리 성능이 좋은 방법으로 구현하지 않았다는 것을 알았지만 묵혀둔 미결 문제를 해결한 기쁨이 더 컸다.

프로젝트 오일러 문제를 100번까지 시도했는데, 이 중 (직접 풀어 해결한 79번 포함한) 72개를 풀었고, 28개 문제는 아직 해결하지 못했다. 남은 문제를 난이도 기준으로 보면, 난이도 5% 문제 2개(26, 59번), 10% 문제 4개(54, 69, 76, 81), 15% 문제 3개(51, 65, 85), 20% 문제 7개(60, 61, 64, 70, 72, 80, 82), 25% 문제 5개(66, 68, 77, 83, 96), 30% 문제 2개(78, 100), 35% 문제 4개(84, 86, 93, 98), 40% 문제 1개(88)이다.

바로 해결하지 못한 문제만 남았기에 시간이 많이 필요할 수도 있을 것 같지만, 일단 100번까지는 모두 해결하는 것을 목표로 계속 시도해봐야겠다.

파이썬을 익히기 위해 시작한 프로젝트 오일러인데, 이제는 수학공부를(특히나 정수론) 더 많이 한다는 느낌이긴 한데, 그래도 프로젝트 오일러 덕분에 파이썬 기반으로 파일 읽고 쓰기, 자료형 변환과 활용, 함수 활용, 모듈 사용 등을 편하게 활용가능하게 되었다. 하지만, 람다 표현식, 클래스, 제너레이터, 정규표현식 등 좀 더 파이썬스럽게 프로그래밍하기 위해 필요한 부분은 문제 해결에 잘 활용되지 않고, 아직도 체계적으로 이해하지 못하고 있는 것 같다.

그리고, 문제 해결하기 위해 작성한 코드가 파이썬이라기 보다는 C와 같은 전통적인 프로그램 형태에 가깝기 때문에 소스코드 없이 어떤 로직(내지는 알고리즘)이 필요한지만 기록하는 형태로 계속 정리할 생각이다.