늒네 기록

프로젝트 오일러 41번은 어떤 소수 n이 x자리 수일때, 1부터 x까지의 숫자가 모두 등장하면 이를 pandigital prime이라고 부른다고 한다면, 이러한 조건을 만족하는 제일 큰 소수 p를 구하라는 문제다. pandigital 조건이 붙어있으므로 p는 아무리 커도 9자리여야 하는데, 1~9가 모두 등장하는 9자리 수는 각 자릿수를 다 더하면 45이므로 3의 배수가 되어 소수가 될 수 없다. 즉, p는 아무리 커봐야 8자리인 것이다. 문제에 나이브하게 접근하여 8자리 소수들을 전부 구한 뒤, 큰 소수부터 시작하여 위의 조건을 만족하는지 체크하는 루프를 도는 방식으로 문제를 풀었다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 n=10**8 p = [True ..

프로젝트 오일러 37번도 나이브하게 덤볐는데도 풀린 문제. 이 문제는 어떤 숫자 p가 주어졌을때, 이 숫자 자체도 소수이면서 좌측부터 숫자를 하나씩 제거하면서 만드는 숫자들도 전부 소수, 우측부터 숫자를 하나씩 제거하면서 만드는 숫자들도 전부 소수인 숫자를 truncatable prime이라고 정의하고, 딱 11개 존재하는 이 숫자들을 전부 찾아서 더하라는 문제다. 별 다른 테크닉 없이 10부터 시작하여 1씩 더해가면서 해당 숫자가 조건을 만족하면 리스트에 더하는 루프를 돌고, 리스트 크기가 11이 되면 루프를 빠져나오는 식으로 구현했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 def p_test(n): if n

프로젝트 오일러 27번에 처음 접근하면서 이거 나이브하게 풀어도 풀릴까 테스트 먼저 해보자고 생각하고 달려들었는데 바로 풀려버려서... 문제는 n^2 + a*n + b 꼴의 함수가 주어졌을때, 절댓값 1000 이하의 두 정수 a, b를 선택하여 n=0부터 i 이하의 숫자들을 대입했을 때 전부 소수가 되도록 하는 최대 i의 값이 최대가 되도록 하는 것이다. 즉, (a, b) 쌍에 대해 i가 결정되는데, 이 i값을 최대로 만드는 (a, b)쌍을 구하는 것. 나이브한 방법으로 풀 때에는 다음의 아이디어만 있어도 충분하다. - 어떤 수가 소수인지 판별하기 위해서는 2부터 그 수의 제곱근 이하의 모든 자연수에 대하여 나눠보면 된다. - 조금 탐색 공간을 줄이고 싶다면, n=0을 대입했을 때 값이 b가 되므로, b..

프로젝트 오일러 72번은 분모가 1,000,000 이하인 진분수의 전체 개수를 구하는 문제다. 이 문제를 풀기 위해서는 분모가 k로 주어져있을 때 진분수가 몇 개인지 구하는 방법을 알아야 하는데, 분자를 a, 분모를 b라 하면 진분수는 - gcd(a, b) = 1 - a

프로젝트 오일러 57번은 패턴만 찾으면 거저먹는 문제. i번째 분수가 b/a꼴로 생겼다고 하면, i+1번째 분수는 1+1/(1+b/a) = 1+1/((a+b)/a) = 1+a/(a+b) = (2a+b)/(a+b)가 되어, i번째 분수의 분자, 분모로 i+1번째 분수의 분자, 분모를 바로 구할 수 있으니 이를 활용하자. 1 2 3 4 5 6 sol=0 a,b=1,1 for _ in range(1000): a,b=a+b,2*a+b if len(str(a))

프로젝트 오일러 55번에서는 Lychrel number라는 것에 대해 먼저 설명해준다. 예를 들어 47이 주어졌을 때 이를 뒤집은 74를 더하면 121이 되어 1회 시행만에 palindrome이 된다. 349의 경우 349+943=1292 1292+2921=4213 4213+3124=7337 즉, 3회 시행만에 palindrome이 된다. Lychrel number는 이러한 뒤집기-더하기 시행을 아무리 반복해도 palindrome이 되지 않는 숫자를 뜻하는데, 이 문제에서는 10000보다 작은 숫자들 중에 이러한 뒤집기-더하기 시행을 50번 반복하는 동안 palindrome이 나오지 않으면 Lychrel number라고 친다 하고 이런 숫자가 몇 개나 있는지 구하라고 한다. 이 문제는 뒤집기-더하기 시행..

프로젝트 오일러 93번은 서로 다른 한 자리 숫자 4개가 주어졌을 때, 사이에 +, -, *, /, (, )를 적당히 끼워넣은 뒤 계산했을 때 나올 수 있는 숫자들을 전부 구한 다음, 그 안에 1부터 n 사이의 모든 숫자가 있다고 말할 수 있는 최대 n을 구하는 문제다. 예를 들어, 나올 수 있는 숫자들을 작은 순서대로 나열했을 때 1, 2, ..., 28, 30, ... 이런 리스트가 나온다면, 29를 만드는 방법이 없고 그보다 작은 자연수들은 모두 표현 가능하므로 답은 28. 계산식을 string으로 만든 뒤 이를 계산해주는 방법과, 숫자들의 순서, 사칙연산 기호의 순서를 조합해주는 방법을 알고 있으면 잘 활용해서 풀 수 있는 문제다. 아래의 두 글에 나온 함수들만 안다면 쉽게 풀 수 있을 것이다. ..

프로젝트 오일러 97번은 앞에선 열심히 메르센 소수에 대한 설명을 하고, 그 다음엔 넌-메르센 소수 이야기를 하더니, 마지막에 가서는 '앞에 주어진 수의 마지막 10자리 수를 구하시오'라고 하는, 조금 김빠지는 문제다. 이 문제에서 계산해야 하는 수는 28433×2^7830457+1로, 2^7830457를 어떻게 빠르게 계산해내는지가 관건이다. 해당 숫자는 계속 계산하기엔 큰 숫자가 될 것이고, 어차피 우리에게 필요한 숫자는 마지막 10자리 수이며, 그렇기 때문에 계산을 하다가 11자리수가 넘어가면 마지막 10자리 숫자만 잘라서 계속 계산을 이어나가는 방법을 활용할 것이다. 그런데 그렇다고 해도 2^7830457의 마지막 10자리 수를 빨리 계산해내야 하는 문제가 남는다. 문제에 나이브하게 접근하면 이렇..

프로젝트 오일러 21번 문제에서 말하는 amicable numbers란, 다음 조건을 만족해야 한다. - d(x)란 x의 진약수(proper divisor, x를 제외한 x의 양의 약수)들의 합 - x != y 이고, d(x)==y, d(y)==x이면 x, y 둘 다 amicable number 이 문제는 10000보다 작은 amicable number들의 합을 구하는 것이 목표다. 이를 위해서 문제를 아래의 과정들로 쪼개겠다. - 10000보다 작은 양의 정수들을 소인수분해한 결과를 담아놓는 list를 만들고, - 각 양의 정수마다 d(x)를 계산하는 함수를 만들어서 이 값을 담아놓는 list를 만들고, - x를 정해서 y=d(x), z=d(y)를 만족하면서 x != d(x)를 만족하는 x들을 찾아 더..

프로젝트 오일러 13번 문제는 파이썬으로 푼다고 하면 거저 먹는 문제다. 큰 수 연산 문제는, 특히 난이도가 낮은 문제라면 파이썬에서 특별히 신경 써야 하는 부분이 적어진다. 문제에서는 100개의 50자리수가 주어지고, 이를 다 더한 다음 앞의 10자리 수를 구하라고 한다. 이런 유형의 문제를 쉽게 푸는 환경을 세팅하는 것에 이 포스트의 의의를 두겠다. 가장 간단한 방법은, 먼저 코드 자체에 100개의 숫자로 이루어진 리스트를 두고 합을 구하는 것이다. 코드는 다음과 같다. l = [ 37107287533902102798797998220837590246510135740250, ... 53503534226472524250874054075591789781264330331690 ] print(sum(l)) 이..