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

Project Euler

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

오일러 프로젝트 23

자신을 제외한 약수(진약수)를 모두 더하면 자기 자신이 되는 수를 완전수라고 합니다. 예를 들어 28은 1 + 2 + 4 + 7 + 14 = 28 이므로 완전수입니다. 또, 진약수의 합이 자신보다 작으면 부족수, 자신보다 클 때는 초과수라고 합니다. 12는 1 + 2 + 3 + 4 + 6 = 16 > 12 로서 초과수 중에서는 가장 작습니다. 따라서 초과수 두 개의 합으로 나타낼 수 있는 수 중 가장 작은 수는 24 (= 12 + 12) 입니다.

해석학적인 방법을 사용하면, 28123을 넘는 모든 정수는 두 초과수의 합으로 표현 가능함을 보일 수가 있습니다. 두 초과수의 합으로 나타낼 수 없는 가장 큰 수는 실제로는 이 한계값보다 작지만, 해석학적인 방법으로는 더 이상 이 한계값을 낮출 수 없다고 합니다.

그렇다면, 초과수 두 개의 합으로 나타낼 수 없는 모든 양의 정수의 합은 얼마입니까?

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

오일러 프로젝트 22

여기 5천개 이상의 영문 이름들이 들어있는 46KB짜리 텍스트 파일 names.txt 이 있습니다 (우클릭해서 다운로드 받으세요). 이제 각 이름에 대해서 아래와 같은 방법으로 점수를 매기고자 합니다. 먼저 모든 이름을 알파벳 순으로 정렬합니다. 각 이름에 대해서, 그 이름을 이루는 알파벳에 해당하는 숫자(A=1, B=2, …, Z=26)를 모두 더합니다. 여기에 이 이름의 순번을 곱합니다. 예를 들어 “COLIN”의 경우, 알파벳에 해당하는 숫자는 3, 15, 12, 9, 14이므로 합이 53, 그리고 정렬했을 때 938번째에 오므로 최종 점수는 938 × 53 = 49714가 됩니다. names.txt에 들어있는 모든 이름의 점수를 계산해서 더하면 얼마입니까?

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

오일러 프로젝트 21

n의 약수들 중에서 자신을 제외한 것의 합을 d(n)으로 정의했을 때, 서로 다른 두 정수 a, b에 대하여 d(a) = b 이고 d(b) = a 이면 a, b는 친화쌍이라 하고 a와 b를 각각 친화수(우애수)라고 합니다. 예를 들어 220의 약수는 자신을 제외하면 1, 2, 4, 5, 10, 11, 20, 22, 44, 55, 110 이므로 그 합은 d(220) = 284 입니다. 또 284의 약수는 자신을 제외하면 1, 2, 4, 71, 142 이므로 d(284) = 220 입니다. 따라서 220과 284는 친화쌍이 됩니다. 10000 이하의… 더 보기 »오일러 프로젝트 21

오일러프로젝트78

동전 100개를 나누는 방법 이 문제는 오일러 프로젝트 76번 문제와 같은 문제로 볼 수 있는데…. 처음 작성한 시점부터 너무 오래된 글이라, 진도를 기다리지 못하고 미리 발행한다. 5개의 동전이 있다.  이 동전들을 나누는 방법을 생각해 보자. 동전 5개는 아래와 같이 총 7가지 방법으로 나눌 수 있다. ooooo # 5개짜리 그룹 1개 oooo o # 4개 + 1개 ooo oo # 3개 + 2개 ooo o o # 3개 + 1개 + 1개 oo oo o # 2개 + 2개 + 1개… 더 보기 »오일러프로젝트78

오일러 프로젝트 19

다음은 달력에 관한 몇 가지 일반적인 정보입니다 (필요한 경우 좀 더 연구를 해 보셔도 좋습니다).

  • 1900년 1월 1일은 월요일이다.
  • 4월, 6월, 9월, 11월은 30일까지 있고, 1월, 3월, 5월, 7월, 8월, 10월, 12월은 * 31일까지 있다.
  • 2월은 28일이지만, 윤년에는 29일까지 있다.
  • 윤년은 연도를 4로 나누어 떨어지는 해를 말한다. 하지만 400으로 나누어 떨어지지 않는 매 100년째는 윤년이 아니며, 400으로 나누어 떨어지면 윤년이다

20세기 (1901년 1월 1일 ~ 2000년 12월 31일) 에서, 매월 1일이 일요일인 경우는 총 몇 번입니까?

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

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

참고: 여기서는 경로가 16,384개 밖에 안되기 때문에 모든 경로의 합을 일일이 계산해서 답을 구하는 것이 가능합니다. 하지만 67번 문제에는 100층자리 삼각형 배열이 나옵니다. 그런 경우에는 좀 더 현명한 풀이 방법을 찾아야겠지요.

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

오일러 프로젝트 64

자연수 n의 제곱근은 연분수 형태로 나타낼 수 있다. 정수부와 실수부를 각각 나눈다고 생각하고 n의 제곱근을 넘지 않는 정수와 실수부의 합으로 나눈 후, 실수부를 분자가 1이 되는 분수의 형태로 바꾼다. 즉 실수부의 역수를 다시 정수부와 실수부로 나누는 작업을 반복하면서 연분수로 전개한다. 그 과정은 아래와 같이 단계를 일반화 할 수 있다. 위 계산 과정으로부터 초기값 및 점화식을 아래와 같이 얻을 수 있다. 위 점화식을 사용하여, A, B, C의 다음 항을 각각 구해나간다. 이 때 완전 제곱인 형태이거나, 이전의 a, b, c 값의… 더 보기 »오일러 프로젝트 64

오일러 프로젝트 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글자가 됩니다. 접근 숫자를 영단어로 변환하는 함수를 작성하고, 1 ~ 1,000 의 범위에 대해 이 함수를 적용한 후, 글자 수를 모두 더하면 되겠다. 영어… 더 보기 »오일러 프로젝트 17