프로젝트 오일러
1. 개요
프로그래밍으로 수학 문제를 해결하는 사이트이다.
현재 740여문제가 업로드되어 있다.
프로젝트 이름은 오일러에서 따왔다.
홈페이지 주소는 http://projecteuler.net/
국가별랭킹도 제공하고 단계별 상도 수여한다.
2021년 2월 기준으로 한국인 1위는 스탠포드 컴퓨터공학과 박사 출신.
100번 문제까지는 인터넷에 풀이가 많이 공개되어 있으나 번호가 올라갈 수 록 공개된 풀이가 별로 없다.
2. 상세
이 사이트의 제작자는 Colin Hughes이며, 2001년 10월 5일 오픈했다. 비영리 사이트이다.
나이, 국적등에 관계없이 누구나 참여가 가능하다.
프로그래밍 언어는 무엇을 써도 상관없다.
문제마다 난이도도 나눠져 있다.
문제의 답을 입력하려면 로그인이 필요하다. 만약 올바른 답을 입력한 경우에는 해당 문제의 포럼에 들어갈 수 있는데, 여기서 다른 사람들의 풀이도 볼 수 있다.
우리나라의 경우 한국어 번역 사이트가 존재한다. 주소는 http://euler.synap.co.kr이다. 그러나 번역된 문제가 120문제정도 밖에 안되기 때문에 문제를 제대로 풀어보려면 원래 사이트를 이용하는것이 좋다.
영어 사이트의 경우 번역사이트보다 더 많은 기능이 있는데 25문제를 풀때마다 레벨이 올라가는 등의 기능이 있다.
3. 문제
문제는 예시로 작은 범위 내에서의 예시와 그에 대한 답을 알려 준 후 같은 내용의 좀 더 큰 값에 대한 답을 구하도록 출제된다. 문제의 이해를 돕고 알고리즘을 점검할 수 있도록 유도하기 위한 목적으로 추측된다.
3.1. 문제 1
삼각수 공식과 집합에 대한 개념만 안다면 직접 푸는 것도 가능하다. 물론 프로그래밍으로 구할 때는 이 문제에서 굳이 저런 공식이나 집합 개념을 사용 할 필요가 없다.1000 보다 작은 수 중 3또는 5의 배수인 수 들의 합을 구하시오.
어떻게 풀더라도 반복문 사이클이 많아봤자 3,000회 정도라서 성능 측정을 하는 의미가 별로 없는 문제다.
3.2. 문제 2
항의 개수가 많아지고 수의 범위가 100만 단위로 커지면서 직접 풀기에는 어려워진 문제다. 하지만 알고리즘으로서의 난이도는 직전 문제와 큰 차이가 없다.피보나치 수열의 각 항은 바로 앞의 항 두 개를 더한 것이 됩니다. 1과 2로 시작하는 경우 이 수열은 아래와 같습니다.
1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
짝수이면서 4백만 이하인 모든 항을 더하면 얼마가 됩니까?
3.3. 문제 3
본격적으로 숫자가 커지는 문제. 문제로 제시된 숫자가 6천억보다도 큰 수이기 때문에 C++처럼 변수가 커버할 수 있는 수의 범위에 제한이 있는 경우에는 단순히 int를 쓰는 것만으로는 문제를 풀 수가 없다. 변수가 다룰 수 있는 수의 범위를 파악하고 풀어야 한다.어떤 수를 소수의 곱으로만 나타내는 것을 소인수분해라 하고, 이 소수들을 그 수의 소인수라고 합니다.
예를 들면 13195의 소인수는 5, 7, 13, 29 입니다.
600851475143의 소인수 중에서 가장 큰 수를 구하세요.
3.4. 문제 4
수학적인 규칙을 파악하기보다는 대칭수라는 특징을 확인하는 방법으로 구현해야하는 문제다. 구현 방식에 따라 속도가 다소 느려질 수 있으며, 확장성에 대한 고려를 어떻게 하냐에 따라 구현 양상이 조금씩 달라지기 시작하는 문제다.앞에서부터 읽을 때나 뒤에서부터 읽을 때나 모양이 같은 수를 대칭수(palindrome)라고 부릅니다.
두 자리 수를 곱해 만들 수 있는 대칭수 중 가장 큰 수는 9009 (= 91 × 99) 입니다.
세 자리 수를 곱해 만들 수 있는 가장 큰 대칭수는 얼마입니까?
3.5. 문제 5
1부터 n까지 연속된 숫자들의 최소 공배수를 구하는 문제. 8이나 16처럼 m^n 형식으로 구성된 수를 어떻게 처리할 것이냐가 성능을 가른다.1 ~ 10 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 2520입니다.
그러면 1 ~ 20 사이의 어떤 수로도 나누어 떨어지는 가장 작은 수는 얼마입니까?
3.6. 문제 6
쉬운 문제. 수의 범위가 좁아서 계산기를 쓰든 뭘 하든 쉽게 풀 수 있다.1부터 10까지 자연수를 각각 제곱해 더하면 다음과 같습니다 (제곱의 합).
$$1^2+2^2+ ... + 10^2 = 385$$
1부터 10을 먼저 더한 다음에 그 결과를 제곱하면 다음과 같습니다 (합의 제곱).
$$(1+2+ ... + 10)^2 = 3025$$
따라서 1부터 10까지 자연수에 대해 "합의 제곱"과 "제곱의 합" 의 차이는 3025 - 385 = 2640 이 됩니다.
그러면 1부터 100까지 자연수에 대해 "합의 제곱"과 "제곱의 합"의 차이는 얼마입니까?
3.7. 문제 7
즉 $$\pi(x)=10001$$을 만족하는 가장 작은 수를 구하는 것이다.소수를 크기 순으로 나열하면 2, 3, 5, 7, 11, 13, ... 과 같이 됩니다.
이 때 10,001번째의 소수를 구하세요.
조건이 매우 단순하기 때문에 결과를 구하는 것만 놓고 본다면 풀기 쉽다. 하지만 소수를 구하는데 반복문을 어디까지 돌려야 하는가에 대해 알지 못한다면 남들은 0.01초만에 결과가 나오는 것을 혼자 10분이 걸리도록 기다려야 하는 상황이 발생한다. 결과가 금방 나오지 않는다면 반복문에서 놓치고 있는 것이 무엇인지 검토해볼 필요가 있다.
조금 편법을 써서 로그 적분 함수 $$\mathrm{li}(x) \approx 10001$$이 나오는 값만 골라서 계산할 수도 있지만[1], 이 함수를 프로그래밍하는 것이 매우 어려워서[2] 배보다 배꼽이 더 커질 수 있다. 좀 덜 정확하지만 쉬운 방법으로 $$\dfrac{x}{\ln x} \approx 10001$$를 이용하는 것이 있는데 이 식은 가우스와 르장드르[3]가 연구했던 유서 깊은 방식이다.
3.8. 문제 8
1,000자리나 되기 때문에 일반적인 숫자 변수로는 커버할 수 없다. 배열을 이용해 각 자리를 읽어서 비교한 후 최대값을 구해야 한다.다음은 연속된 1000자리 숫자입니다 (읽기 좋게 50자리씩 잘라놓음).
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098'''71112'''1722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
여기서 붉게 표시된 71112의 경우 7, 1, 1, 1, 2 각 숫자를 모두 곱하면 14가 됩니다.
이런 식으로 맨 처음 (7 × 3 × 1 × 6 × 7 = 882) 부터 맨 끝 (6 × 3 × 4 × 5 × 0 = 0) 까지 5자리 숫자들의 곱을 구할 수 있습니다.
이렇게 구할 수 있는 5자리 숫자의 곱 중에서 가장 큰 값은 얼마입니까?
3.9. 문제 9
피라고라스의 수를 구하는 문제. a+b+c=1000이라는게 문제의 핵심이다. 물론 이 문제는 제시한 범위가 크지 않기 때문에 어떤 방법을 사용해도 퍼포먼스에 큰 차이가 나지 않지만 범위가 커질 수록 미묘한 퍼포먼스 차이가 발생한다.세 자연수 $$a, b, c$$ 가 피타고라스 정리 $$a^2 + b^2 = c^2$$ 를 만족하면 피타고라스 수라고 부릅니다 (여기서 $$(a < b < c )$$.
예를 들면 $$3^2 + 4^2 = 9 + 16 = 25 = 5^2$$이므로 $$3, 4, 5$$는 피타고라스 수입니다.
$$a + b + c = 1000$$ 인 피타고라스 수 $$a, b, c$$는 한 가지 뿐입니다. 이 때, $$a×b×c$$ 는 얼마입니까?
3.10. 문제 10
퍼포먼스 능력을 판단하는 문제다. 문제의 정답이 최소 100억은 넘어가는 큰 숫자를 다루기 때문에 변수의 특성을 파악해둘 필요가 있다. 또, 연산만으로 끝낼 것이냐, 메모리를 이용할 것이냐에 따라 퍼포먼스에 상당한 차이를 보이는 문제기도 하다.10 이하의 소수를 모두 더하면 2 + 3 + 5 + 7 = 17 이 됩니다.
이백만(2,000,000) 이하 소수의 합은 얼마입니까?
3.11. 문제 11
문제 중에서 처음으로 파일 읽기를 유도하고 있다. 물론 배열에 수동으로 입력해도 되긴 하지만 손이 많이가고 번거롭다.아래와 같은 20×20 격자가 있습니다.
08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08
49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00
81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65
52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91
22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80
24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50
32 98 81 28 64 23 67 10 '''26''' 38 40 67 59 54 70 66 18 38 64 70
67 26 20 68 02 62 12 20 95 '''63''' 94 39 63 08 40 91 66 49 94 21
24 55 58 05 66 73 99 26 97 17 '''78''' 78 96 83 14 88 34 89 63 72
21 36 23 09 75 00 76 44 20 45 35 '''14''' 00 61 33 97 34 31 33 95
78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92
16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57
86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58
19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40
04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66
88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69
04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36
20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16
20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54
01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48
위에서 대각선 방향으로 연속된 붉은 숫자 네 개의 곱은 26 × 63 × 78 × 14 = 1788696 입니다.
그러면 수평, 수직, 또는 대각선 방향으로 연속된 숫자 네 개의 곱 중 최대값은 얼마입니까?
탐색할 때의 예외사항만 잘 처리하면 큰 어려움 없이 풀 수 있는 문제다. 구현이 쉽기 때문에 방법만 안다면 쉬어가는 문제 수준으로 취급받는다.
3.12. 문제 12
문제 자체는 단순한만큼 답을 구하기도 쉽다. 다만 약수 개수 구하는 알고리즘이 설계에 따라 시간을 상당히 잡아먹을 수도 있다. 최적화 없이 구현할 경우 10분이 넘는 시간동안 기다려야 하는 상황을 맞이할 수도 있으니 최적화 설계에 대한 고민을 해 볼 필요가 있다.1부터 n까지의 자연수를 차례로 더하여 구해진 값을 삼각수라고 합니다.
예를 들어 7번째 삼각수는 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28이 됩니다.
이런 식으로 삼각수를 구해 나가면 다음과 같습니다.
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
이 삼각수들의 약수를 구해봅시다.
1: 1
3: 1, 3
6: 1, 2, 3, 6
10: 1, 2, 5, 10
15: 1, 3, 5, 15
21: 1, 3, 7, 21
28: 1, 2, 4, 7, 14, 28
위에서 보듯이, 5개 이상의 약수를 갖는 첫번째 삼각수는 28입니다.
그러면 500개 이상의 약수를 갖는 가장 작은 삼각수는 얼마입니까?
3.13. 문제 13
50자리 숫자 100개를 합한 후 앞에서부터 읽었을 때의 첫 10자리가 어떤 수인지 구하는 문제.아래에 50자리 숫자가 100개 있습니다. 이것을 모두 더한 값의 첫 10자리는 얼마입니까?
(생략)
파이썬처럼 읽어들이는 수의 범위에 제한이 없다면 코파면서 풀어도 되는 문제지만
그렇지 않은 언어에서는 문자열을 이용해 반복문을 돌리면서 풀어야 한다.
문제 자체가 단순하다보니 언어 특성이 비슷할 경우 구현도 비슷하게 이뤄지는 경향을 보인다.
3.14. 문제 14
문제를 얼핏 봤을 때는 모를 수도 있지만 이번에도 계산 과정에서 수가 569억까지 커지는 문제다.양의 정수 n에 대하여, 다음과 같은 계산 과정을 반복하기로 합니다.
n → n / 2 (n이 짝수일 때)
n → 3 n + 1 (n이 홀수일 때)
13에 대하여 위의 규칙을 적용해보면 아래처럼 10번의 과정을 통해 1이 됩니다.
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
아직 증명은 되지 않았지만, 이런 과정을 거치면 어떤 수로 시작해도 마지막에는 1로 끝나리라 생각됩니다.
(역주: 이것은 콜라츠 추측 Collatz Conjecture이라고 하며, 이런 수들을 우박수 hailstone sequence라 부르기도 합니다)
그러면, 백만(1,000,000) 이하의 수로 시작했을 때 1까지 도달하는데 가장 긴 과정을 거치는 숫자는 얼마입니까?
참고: 계산 과정 도중에는 숫자가 백만을 넘어가도 괜찮습니다.
따라서 c++이나 js처럼 변수가 다루는 수의 범위에 제한이 있는 언어는 대충 int 넣고 돌렸다가 무한 루프에 걸릴 수 있으니 주의해야 한다.
조건이 명확한만큼 결과를 구하기는 쉽다. 깡으로 모든 수를 계산해도 되지만, 굳이 모든 계산을 다 할 필요는 없는 문제로
각 숫자에 대한 히스토리를 남겨서 이를 참고하게 하는 방법이 유효한 문제다.
3.15. 문제 15
격자 경로를 구하는 문제. 문제 풀이 방법은 크게 두 가지로 갈린다. 하나는 팩토리얼 공식으로 푸는 방법. 수식으로 표현한다면 $$\displaystyle \frac{20!}{10!10!}$$으로 나타낼 수 있다.아래와 같은 2 × 2 격자의 왼쪽 위 모서리에서 출발하여 오른쪽 아래 모서리까지 도달하는 길은 모두 6가지가 있습니다 (거슬러 가지는 않기로 합니다).
[image]
그러면 20 × 20 격자에는 모두 몇 개의 경로가 있습니까?
다른 하나의 방법은 격자의 각 수를 합해서 구하는 방법이 있다. 왼쪽에 있는 수 + 위쪽에 있는 수가 현재 위치의 경로 수인 규칙을 이용하여 합산하여 구하는 방법이 있다. 어느쪽을 이용하든 성능에는 큰 차이가 없는 편. 답이 4억 정도는 가뿐히 넘어가므로 이 점에 유의하여 구현하는게 좋다.
3.16. 문제 16
거대한 수에 대한 처리 문제다. 변수의 크기에 제한이 없는 파이썬은 코 파면서 풀 수 있는 문제지만 C언어처럼 변수가 커버할 수 있는 수의 크기에 제한이 있는 경우에는 문제를 풀기 위한 별도의 방법을 찾아야 한다. 통상적인 풀이는 배열을 넉넉하게 깔아두고 각 자리에 2를 곱한 뒤 결과를 다듬는 방식으로 $$2^{1000}$$을 구한 뒤 배열에 있는 수의 합을 구하는 방식으로 푼다. 때문에 문제를 푸는 것 자체는 배열을 사용해야겠다는 생각에 도달할 수 있다면 금방 풀 수 있다.$$2^{15} = 32768$$ 의 각 자리수를 더하면 3 + 2 + 7 + 6 + 8 = 26 입니다.
$$2^{1000}$$의 각 자리수를 모두 더하면 얼마입니까?
다만 이러한 방법은 배열 크기를 넉넉하게 깔아두고 해야하기 때문에 속도는 빠르지만 메모리가 어느정도 낭비가 된다는 단점이 있다. 실제로 $$2^{1000}$$은 302자리 밖에 안되고, 문제를 풀어낸 사람들은 대부분 메모리 할당을 가변형으로 하지 않고 고정형으로 넉넉하게 깔아두는 경향을 보인다. 밑수가 커지면 결과가 이상하게 나오는 경우도 심심치 않게 발생한다. 문제에 대해 좀 더 파고들어보고 싶다면 이 부분에 대해 해결을 해보도록 하자.
3.17. 문제 17
풀다보면 프로그래밍 공부라기보다는 영어공부라는 느낌이 강하다...1부터 5까지의 숫자를 영어로 쓰면 one, two, three, four, five 이고,
각 단어의 길이를 더하면 3 + 3 + 5 + 4 + 4 = 19 이므로 사용된 글자는 모두 19개입니다.
1부터 1,000까지 영어로 썼을 때는 모두 몇 개의 글자를 사용해야 할까요?
참고: 빈 칸이나 하이픈('-')은 셈에서 제외하며, 단어 사이의 and 는 셈에 넣습니다.
예를 들어 342를 영어로 쓰면 three hundred and forty-two 가 되어서 23 글자, 115 = one hundred and fifteen 의 경우에는 20 글자가 됩니다.
조건문을 이용해서 각 숫자에 대한 조건문을 만들어서 풀 수도 있고 딕셔너리형 자료형으로 풀이할 수도 있다.
철자가 틀리지 않도록 주의를 기울이도록 하자.
3.18. 문제 18
다음과 같이 삼각형 모양으로 숫자를 배열했습니다.
3
7 4
2 4 6
8 5 9 3
삼각형의 꼭대기부터 아래쪽으로 인접한 숫자를 찾아 내려가면서 합을 구하면, 위의 그림처럼 3 + 7 + 4 + 9 = 23 이 가장 큰 합을 갖는 경로가됩니다. 다음 삼각형에서 합이 최대가 되는 경로를 찾아서 그 합을 구하세요.
75
95 64
17 47 82
18 35 87 10
20 04 82 47 65
19 01 23 75 03 34
88 02 77 73 07 63 67
99 65 04 28 06 16 70 92
41 41 26 56 83 40 80 70 33
41 48 72 33 47 32 37 16 94 29
53 71 44 65 25 43 91 52 97 51 14
70 11 33 28 77 73 17 78 39 68 17 57
91 71 52 38 17 14 91 43 58 50 27 29 48
63 66 04 68 89 53 67 30 73 16 69 87 40 31
04 62 98 27 23 09 70 98 73 93 38 53 60 04 23
참고: 여기서는 경로가 16384개밖에 안되기 때문에, 모든 경로의 합을 일일이 계산해서 답을 구하는 것이 가능합니다.
하지만 67번 문제에는 100층짜리 삼각형 배열이 나옵니다. 그런 경우에는 좀 더 현명한 풀이 방법을 찾아야겠지요.