프로그래밍/알고리즘 (46) 썸네일형 리스트형 [EP019] 윤년 1901년 1월부터 2000년 12월까지 중에서 1일이 일요일인 달의 갯수를 구하는 문제. 윤년을 구하는 조건이 주어지고, 그 조건만 잘 써 주고, mod 7을 이용하면 요일을 구할 수 있다. // leap_year.cpp : Defines the entry point for the console application. // /* http://projecteuler.net *____________________________________________________________________ Problem 19 14 June 2002 You are given the following information, but you may prefer to do some research for yourself. .. [EP 074] f(145) = 1! + 4! + 5! = 145 정수에 대해서 그 정수를 십진수로 표현했을 때, 각 자리수의 계승(팩토리얼)의 합을 취하는 조작이 있다. 어떤 정수에서 시작하더라도 이 조작을 반복하면 어떤 루프를 돌게 된다. 이 루프는 링크에서 말한 것 밖에 없다고 한다. 이걸 알고서... 1000000보다 작은 정수 중에서 그 정수에서부터 시작하여, 조작을 반복하여 만들어지는 수의 집합의 갯수가 60개인 것들의 갯수를 구하란다. #!/usr/bin/env python # http://projecteuler.net/index.php?section=problems&id=74 # factorial list from functools import lru_cache factorial = [1] # 0! = 1 for i in range(1, 10): fact.. 1/1, 1/2, ... 1/999 의 순환소수 표현 프로젝토 오일러 26번 문제를 오랜만에 다시 풀었다. 중간결과로 n=1부터 1000 이하까지의 1/n 의 순환소수 표현을 구했다. 순환마디의 길이가 커지는 숫자들은 거의 소수로 보이고, 이 숫자들에 대해서 순환마디의 길이는 n-1 이다. 나아가 오일러파이함수(totient)와 관련이 있음. (아래 see also 1, 2) see also : 0. 관련파이썬코드 1. http://daewonyoon.pythonanywhere.com/fraction/ 2. 순환마디에대한수학적논의 3. mathnet의 관련항목 괄호로 감싼 것이 반복되는 순환마디이다. 1/1 = 1.(0) 1/2 = 0.5(0) 1/3 = 0.(3) 1/4 = 0.25(0) 1/5 = 0.2(0) 1/6 = 0.1(6) 1/7 = 0.(14.. [EP 032] 복면산 39 x 186 = 7254 39 x 186 = 7254 란 등식에는 1부터 9까지의 모든 수가 등장한다. A x B = C 꼴이 되고 1부터 9까지의 숫자를 한번씩 모두 사용할 수 있도록 표현되는 C가 되는 모든 C의 합은 얼마일까? (A' x B' = A x B = C 인 C도 있으나 한번만 합산한다.) 무한 for문 겹치기 신공으로 무식하게 풀었다. #!/usr/bin/env python # http://projecteuler.net/index.php?section=problems&id=32 # # Solve # #### abc #### #### x de #### #### ----- #### #### fghi #### # # Or # #### abcd #### #### x e #### #### ----- #### #### fg.. [EP 102] 삼각형 내부외부 판별 평면상의 3점이 주어졌을 때, 그 3점으로 이루어지는 삼각형 안에 원점이 있는지를 판별하는 과제. 임의로 3점을 1, 2, 3 이라고 했을 때, 원점을 중심으로 1->2 의 뱡향, 2->3 의 방향, 3->1 의 방향이 같다면, 원점은 내부의 점. 방향이 바뀐다면, 외부의 점이다. 좌표가 주어진 두 점의 방향있는 각도의 방향은 두 점으로 만든 정방행렬의 판별식의 부호로 알 수 있다. (3차원으로 확장한 두 좌표의 외적으로 해석할 수도 있음. 동일한 것.) #!/usr/bin/env python # http://projecteuler.net/index.php?section=problems&id=102 # Given 3 points, check if the triangle formed by these # c.. [EP 018] 삼각형 배열에서 지나간 수의 합을 최대로 하는 경로를 구하기 문제에서는 경로를 다 구할 필요는 없었고, 경로합의 최대값만 구하면 되었다. 중간에 어떤 노드까지 거슬러 올 수 있는 모든 경로의 최대값을 알 수 있다고 하자. 한 줄에 대해서 다 안다고 하자. 그럼 그 윗줄의 어떤 노드 A까지 거슬러 올 수 있는 모든 경로의 최대값은, 그 A 아래의 두 노드 각각의 최대값과 A노드 값의 합, 두가지 경우 중에서 결정된다. #!/usr/bin/env python # http://projecteuler.net # Problem 18 # Find a top-to-bottom path which makes the path-sum maximum # Author : DwYoon # Date : 2020 # I reduce the triangle from the bottom. Ea.. [EP0010] 백만이하 소수의 합 특정 수 이하의 모든 소수를 구하는 알고리즘을 비교해 보았다. gen_primes 는 스택오버플로우에서 검색하여 발견한 방법. 에라토스테네스의 방법이 특정수 이하까지의 체를 만들기 위해 메모리를 잡아야 하는 단점이 있는데, 메모리를 덜 잡고 하는 방법이라고 한다. 이해를 하려면 좀 더 들여다 봐야하겠으나, 내 방법보다 훨씬 빠르게 나왔다. (무식하게 메모리 잡고 하는 방법보다는 약간 느렸지만) 커멘트로 써 놓은 테스트 결과는 천만으로 한 것. 백만일 때의 결과는 각각 3.1초, 3.3초, 1.3초, 1.5초. import time import functools from tqdm import tqdm def log_elapsed(func): @functools.wraps(func) def newfunc(*.. [EP003] 큰 수의 소수분해 from typing import List import math from time import time from tqdm import tqdm def get_primes_under_siev(n: int) -> List[int]: root_n = int(math.sqrt(n)) siev = {} siev[0] = siev[1] = 0 siev[2] = 1 for i in range(2, root_n + 1): # print(i) if siev.get(i, 1): for j in range(i + i, n + 1, i): siev[j] = 0 # print(siev) primes = [n for n in range(2, n + 1) if siev.get(n, 1)] return primes def facto.. 이전 1 2 3 4 5 6 다음
