본문 바로가기

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

(37)
[EP 078] 동전 나누기 문제 78 : p(n)을 n개의 동전을 무더기로 나누는 경우의 수라고 하자. 예를 들어서, 5개의 동전이 있다면, 다음과 같이 7가지 방법이 있어서, p(5) = 7이 된다. ooooo oooo o ooo oo ooo o o oo oo o oo o o o o o o o o 해법 : Q(n, m) 을 n개의 동전을 나눌 때 가장 큰 무더기를 이루는 갯수가 m개인 경우의 수라고 한다. 위 예에서 보면, Q(5,5) = 1 Q(5,4) = 1 Q(5,3) = 2 Q(5,2) = 2 Q(5,1) = 1 이 되는 것을 알 수 있다. 이렇게 정의한 Q(n, m)에서 다음과 같은 식이 항상 성립함을 알 수 있다. Q(n, n) = 1 Q(n, 1) = 1 m Q(n, m) = sum Q(n-m, i) i = 1 마지..
[EP 077] 소수의 합으로 나타내는 경우의 수 오일러 프로젝트 77번 문제. 10을 소수들의 합으로 나누는 경우의 수는 다음과 같이 다섯가지이다. 7+3 5+5 5+3+2 3+3+2+2 2+2+2+2+2 소수들의 합으로 나누는 경우의 수가 처음으로 5000을 넘는 수는 무엇인가? from typing import Set, Dict from functools import lru_cache from pprint import pprint primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97] @lru_cache() def summations(n: int) -> Set: # print(">"*depth + str(n)) # ..
[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..
[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(*..