본문 바로가기

프로그래밍/오일러프로젝트

(33)
[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..
[EP 023] 두 과잉수의 합으로 나타낼 수 없는 모든 수의 합 완전수는 자신보다 작은 약수의 합이 자신과 같은 수이다. 예로는 6, 28 등이 있다. 과잉수는 이 합이 자신보다 큰 것을 말한다. 두 과잉수의 합으로 나타낼 수 없는 모든 양의 정수의 합은? 자신을 포함하는 모든 약수의 합, 즉 약수함수가 곱셈적이라는 성질 때문에 재귀함수를 만들거나 캐시리스트를 만드는 방식으로 "쪼개서" 문제를 해결하는 전략을 쓸 수 있다. 아래코드는 s 라는 리스트에 약수함수값을 저장하여 n의 약수함수값을 s[n] 으로 가져올 수 있고, n = p q 일 때에, 가장 작은 소수인수를 만나면, s(n) = s[p] s[q] 라는 성질을 이용하여, 차례대로 s 리스트를 채우는 방식으로 문제를 풀어본 것이다. # PROJECT EULER # PROBLEM 23 def s_f(n): """..
[EP 092] T(n) = n의 각 자리수의 제곱의 합. T(T(T(..(n)...))) = n 이 되는 n은 1과 89 # http://projecteuler.net # Problem 92 # 2 2 2 2 2 # 89 -> 8 + 9 = 145 -> 1 + 4 + 5 = 42 -> 20 -> 16 -> 37 -> 58 -> 89 -> ... -> 89 # 1 -> 1 -> 1 from functools import lru_cache import time from tqdm import tqdm BIGN = 10 ** 7 sol_dict = dict() sol_dict[0] = 0 sol_dict[1] = 1 sol_dict[89] = 89 digit_sq = [i * i for i in range(10)] @lru_cache def arrives_at_89_recur(n: int): if n == 0 or n == 1 o..
[EP 005] least common multiple for a list of numbers #################################################### # http://projecteuler.net # # Problem 5 # # 2520 is the smallest number that can be divided # by each of the numbers from 1 to 10 without any # remainder. # # What is the smallest number that is evenly # divisible by all of the numbers from 1 to 20? #################################################### # Author : DwYoon # Date : 2007 04 12 N = ..