프로젝트 오일러
Problem 22
영문 이름 점수 합계 구하기
여기 5천개 이상의 영문 이름들이 들어있는 46KB짜리 텍스트 파일 names.txt 이 있습니다 (우클릭해서 다운로드 받으세요).
이제 각 이름에 대해서 아래와 같은 방법으로 점수를 매기고자 합니다.
- 먼저 모든 이름을 알파벳 순으로 정렬합니다.
- 각 이름에 대해서, 그 이름을 이루는 알파벳에 해당하는 수(A=1, B=2, ..., Z=26)를 모두 더합니다.
- 여기에 이 이름의 순번을 곱합니다.
예를 들어 "COLIN"의 경우, 알파벳에 해당하는 수는 3, 15, 12, 9, 14이므로 합이 53, 그리고 정렬했을 때 938번째에 오므로 최종 점수는 938 × 53 = 49714가 됩니다.
names.txt에 들어있는 모든 이름의 점수를 계산해서 더하면 얼마입니까?
result = []
with open ("names.txt") as f:
result = f.read().split(',')
result.sort()
from string import ascii_uppercase
print(ascii_uppercase.index('C')+ 1)
i = 0
total = 0
while i < len(result):
result_1 = 0
temp = result[i].strip('"')
for j in temp:
result_1 += (ascii_uppercase.index(j) + 1)
i += 1
total += (result_1 * i)
print(total)
Problem 23
두 과잉수의 합으로 나타낼 수 없는 모든 양의 정수의 합은?
자신을 제외한 약수(진약수)를 모두 더하면 자기 자신이 되는 수를 완전수라고 합니다.
예를 들어 28은 1 + 2 + 4 + 7 + 14 = 28 이므로 완전수입니다.
또, 진약수의 합이 자신보다 작으면 부족수, 자신보다 클 때는 과잉수라고 합니다.
12는 1 + 2 + 3 + 4 + 6 = 16 > 12 로서 과잉수 중에서는 가장 작습니다.
따라서 과잉수 두 개의 합으로 나타낼 수 있는 수 중 가장 작은 수는 24 (= 12 + 12) 입니다.
해석학적인 방법을 사용하면, 28123을 넘는 모든 정수는 두 과잉수의 합으로 표현 가능함을 보일 수가 있습니다.
두 과잉수의 합으로 나타낼 수 없는 가장 큰 수는 실제로는 이 한계값보다 작지만, 해석학적인 방법으로는 더 이상 이 한계값을 낮출 수 없다고 합니다.
그렇다면, 과잉수 두 개의 합으로 나타낼 수 없는 모든 양의 정수의 합은 얼마입니까?
def sum_of(number):
_sum= 0
for i in range(1, number):
if number % i ==0:
_sum += i
return _sum
result = []
for i in range(1, 28123):
if sum_of(i) > i:
result.append(i)
sum_set = set() #2개의 초과수 합을 저장하는 집합
for i in result:
for j in result:
if(i+j < 28123):
sum_set.add(i+j)
result = sum(range(1,28123)) - sum(sum_set)
print(result)
Problem 24
0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 만들 수 있는 1,000,000번째 사전식 순열은?
어떤 대상을 순서에 따라 배열한 것을 순열이라고 합니다. 예를 들어 3124는 숫자 1, 2, 3, 4로 만들 수 있는 순열 중 하나입니다.
이렇게 만들 수 있는 모든 순열을 숫자나 문자 순으로 늘어놓은 것을 사전식(lexicographic) 순서라고 합니다.
0, 1, 2로 만들 수 있는 사전식 순열은 다음과 같습니다.
012 021 102 120 201 210
0, 1, 2, 3, 4, 5, 6, 7, 8, 9로 만들 수 있는 사전식 순열에서 1,000,000번째는 무엇입니까?
import itertools
def cal_lexicographic_permutation(range_to) :
seq = 1
num = '0123456789'
num_list = itertools.permutations(num)
for lexi_num in num_list :
if seq == range_to :
return "".join(lexi_num)
seq += 1
print(cal_lexicographic_permutation(1000000))
#출처: https://yuda.dev/50 [YUDA't]
Problem 25
피보나치 수열에서 처음으로 1000자리가 되는 항은 몇 번째?
피보나치 수열은 아래와 같은 점화식으로 정의됩니다.
이에 따라 수열을 12번째 항까지 차례대로 계산하면 다음과 같습니다.
a = 1
b = 1
_sum = 2
while len(str(b)) != 1000:
_sum += 1
tmp = a
a = b
b += tmp
print(_sum)
Problem 26
1000 이하의 d 중에서 1/d 이 가장 긴 순환마디를 갖는 수는?
분자가 1인 분수를 단위분수라고 합니다. 분모가 2에서 10까지의 단위분수는 아래와 같습니다.
숫자 위에 찍힌 점은 순환마디를 나타내는데, 1/6의 경우 순환마디는 "6"으로 0.166666...처럼 6이 무한히 반복됨을 뜻합니다. 같은 식으로 1/7은 6자리의 순환마디(142857)를 가집니다.
d 를 1000 이하의 정수라고 할 때, 단위분수 1/d 의 순환마디가 가장 긴 수는 무엇입니까?
y = 0
n = 0
p = [1]
for i in range(2, 1000+1):
r = []
t = 1
while True:
t = t * 10
#print(i, t)
if t in r:
break
r.append(t)
t = t % i
#print(t, r)
if (r[len(r)-1] == 0):
print(i, r, len(r), "순환소수 아님")
else:
print(i, r, "순환소수임 소숫점첫번째부터 순환소수끝까지 자리 합계 : ", len(r))
p.append(len(r))
print(p, max(p), p.index(max(p))+1)
jcbang의 답안 참조
Problem 27
연속되는 n에 대해 가장 많은 소수를 만들어내는 이차식
절대값 주의하기
##### 27
def isPriminary(num):
for i in range(2, abs(num)):
if num % i ==0:
return False
return True
print(isPriminary(2))
print(isPriminary(3))
print(isPriminary(4))
max_a = 0
max_b = 0
def _fun(a, b):
n = 0
_result = []
while True:
_fun = n ** 2 + a*n + b
if isPriminary(_fun) == False:
break
_result.append(n)
n += 1
return _result
result = []
for a in range(-999, 1000):
for b in range(-999, 1000):
_result = _fun(a, b)
if len(_result) > len(result):
result = _result[::]
max_a = a
max_b = b
print(max_a, max_b)
print(max_a* max_b)
Problem 28
1001×1001 나선모양 행렬에서 대각선 원소의 합은?
수 1부터 시작해서 우측으로부터 시계방향으로 감아 5×5 행렬을 만들면 아래와 같이 됩니다.
여기서 대각선 상의 수를 모두 더한 값은 101 입니다.
같은 방식으로 1001×1001 행렬을 만들었을 때, 대각선 상의 수를 더하면 얼마가 됩니까?
_sum = 1
for i in range(3, 1002, 2):
count = 0
for j in reversed(range(1, i*i+1, i-1)):
count += 1
_sum += j
if count == 4:
break;
print(_sum)
Problem 29
2 ≤ a ≤ 100 이고 2 ≤ b ≤ 100인 a b로 만들 수 있는 ab의 개수
여기서 중복된 것을 빼고 크기 순으로 나열하면 아래와 같은 15개의 수가 됩니다.
4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
그러면, 2 ≤ a ≤ 100 이고 2 ≤ b ≤ 100인 a, b를 가지고 만들 수 있는 ab는 중복을 제외하면 모두 몇 개입니까?
result = []
for a in range(2, 101):
for b in range(2, 101):
result.append(a** b)
print(len(set(result)))
Problem 30
각 자리 숫자를 5제곱해서 더했을 때 자기 자신이 되는 수들의 합은?
각 자리의 숫자를 4제곱해서 더했을 때 자기 자신이 되는 수는 놀랍게도 단 세 개밖에 없습니다.
(1 = 14의 경우는 엄밀히 말해 합이 아니므로 제외합니다)
위의 세 수를 모두 더하면 1634 + 8208 + 9474 = 19316 입니다.
그렇다면, 각 자리 숫자를 5제곱해서 더했을 때 자기 자신이 되는 수들의 합은 얼마입니까?
result = []
for num in range(2, 10000000):
num_str = str(num)
len_num_str = 5
num_sum = 0
for i in range(len(num_str)):
num_sum += int(num_str[i]) ** len_num_str
if num_sum == num:
result.append(num)
print(result)
print(sum(result))
Problem 31
영국 화폐 액면가를 조합하는 방법의 수
영국의 화폐 단위는 파운드(£)와 펜스(p)이고, 동전의 종류는 아래와 같습니다.
1p, 2p, 5p, 10p, 20p, 50p, £1 (100p), £2 (200p)
이 동전들을 가지고 2파운드를 만드는 방법은 다양할 것입니다. 예를 하나 들면 이렇습니다.
1×£1 + 1×50p + 2×20p + 1×5p + 1×2p + 3×1p
2파운드를 만드는 서로 다른 방법은 모두 몇 가지나 있습니까?
def f(x):
coins=[1,2,5,10,20,50,100,200]
dp=[0 for i in range(x+1)]
dp[0]=1
for coin in coins:
for cost in range(1,x+1):
if cost-coin>=0:
dp[cost]+=dp[cost-coin]
return dp[-1]
print(f(200))
#qeqioieq
'문제 > Project Euler(프로젝트 오일러)' 카테고리의 다른 글
Problem 52~ (0) | 2021.06.07 |
---|---|
Problem 42 ~ 51 (0) | 2021.05.20 |
Problem 32 ~ 41 (0) | 2021.02.26 |
Problem 12 ~ Problem 21 (0) | 2021.01.19 |
Problem 1~Problem 11 (0) | 2020.08.21 |