늒네 기록

프로젝트 오일러 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들을 찾아 더..

백준 16785번은 solved.ac 가서 브론즈 IV 문제들 중에 눈에 띄는 거 아무거나 클릭했다가 걸린 문제다. 문제가 일본어로 되어있어서 당황했으나, 번역기 돌려보니 설명 자체는 간단. - 출첵하면 A만큼 점수를 준다. - 연속 7일 출첵하면 B만큼의 보너스 점수를 준다. 그리고 연속 출첵 카운터가 0일로 리셋. - C점 이상이 되기 위해서는 연속 며칠 동안 출석해야 하는가? 그리고 인풋으로 A B C 가 주어진다. 7일 연속 출첵하면 받을 수 있는 점수가 7*A+B점이므로, C안에 7*A+B를 몇 번 집어넣을 수 있는지 체크하고 --(1), 7*A+B를 계속 빼고 남은 나머지 점수를 며칠 동안 출석하면 채울 수 있는지 찾으면---(2) 문제가 풀린다. D = 7*A+B라고 두면, (1) C를 D로..

백준 6749번은 solved.ac 가서 브론즈 V 중에 안 푼 문제가 하나 있길래 들어가보게 되었다. 문제는 정말 단순하다. 셋째, 둘째의 나이가 각 줄에 순서대로 주어졌을 때 첫째의 나이를 구할 것. a, a+d가 주어졌을 때 a+2d를 최대한 적은 연산으로 찾으려면 어떻게 할지 고민해보는 것도 좋겠다. 나는 다음과 같이 풀었다. a,b=int(input()),int(input()) print(2*b-a)

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

프로젝트 오일러 7번 문제는 10001번째 소수를 찾으라는 문제다. 에라토스테네스의 체를 활용하여 나이브하게 접근하는 것을 시도해보도록 하자. 먼저, 1부터 10000사이에 있는 소수의 개수를 찾는 것부터 시작해본다. n = 10001 l = [False for _ in range(n)] p = [] for i in range(2, n): if not l[i]: p.append(i) for j in range(i, n, i): l[j] = True print(len(p)) #1229 해당 코드에서는, 크기 10001짜리(즉, 마지막 인덱스가 10000) 리스트 l에 대해서 전부 False를 할당해두고 i = 2일때부터 시작해서 만일 l[i]가 False이면 리스트 p에 더하고 (즉, p는 소수들이 들어있..

[python] string을 list()하면 어떻게 될까? 글에서 이어서, 문제 링크는 프로젝트 오일러 32번. 39 × 186 = 7254 같이, 곱하는 두 수와 곱한 결과에 1부터 9까지 숫자가 다 들어가는 경우를 찾으면 되는데, 이게 뜻하는 것은 결국 str(i) + str(j) + str(i*j)의 결과에 1부터 9까지 숫자가 모두 포함되어 있다는 것과 같다. 그런데 위에서 string을 list로 바꾸는 것이 쉽게 가능함을 보았으니, 이를 바로 활용하면 sorted(list(str(i)+str(j)+str(i*j))) == list('123456789') 이 조건이 true인 경우를 찾는 문제로 바뀐다. i, j중 작은 숫자가 100 이상일 경우, 3자리수 * 3자리수가 최소 5자리수이므로, ..