본문 바로가기

프로그래밍/알고리즘

(46)
[EP0062] 같은 숫자로 이루어진 세제곱이 다섯개 #!/usr/bin/env python # Project Euler 62 # http://projecteuler.net/index.php?section=problems&id=62 # Problem 62 # # The cube, 41063625 (3453), can be permuted to produce two other cubes: # 56623104 (3843) and 66430125 (4053). In fact, 41063625 is the smallest # cube which has exactly three permutations of its digits which are also # cube. # # Find the smallest cube for which exactly five permut..
[Python] 분수의 순환소수, 순환마디 구하기 예전에 순환소수를 구하는 코드를 만들어서 포스팅을 했었다. ( https://daewonyoon.tistory.com/354 ) 손으로 하는 나누기를 그대로 따라하면서, 나머지를 기억하고, 이전에 나왔던 나머지가 다시 나오면, 싸이클이 반복되어 순환마디를 구할 수 있다는 아이디어였다. 다른 방법이 좀 더 간단할지 어쩔지 궁금해서 대충 실험을 해 봤다. 이번 아이디어는 이렇다. 순환소수는 결국 999...99 를 분모로 하는 소수로 바꿀 수 있다. 그러니, 주어진 분수의 분모가, 999...99 를 떨어지게 나눌 때까지, 9, 99, 999, 9999, ... 를 늘려가고, 나누어 떨어지면, 그 배수를 분자에도 곱하면, 분자가 순환마디가 된다. 테스트를 해 본 것은 다음과 같다. def solve(a): ..
파이썬 자리수곱의합 문제 P(n)은 n을 십진수로 표시했을 때 0이 아닌 각 자리수의 곱으로 정의한다. 다음 값을 구하라. P(1) + P(2) + P(3) + ... + P(999999) 우선 무식한 방법 #!/usr/bin/python ########################################################## # ZiffernProdukte # --------------------------------------------------------- # # --------------------------------------------------------- # Mit P(n) bezeichnen wir das Produkt aller Ziffern # 1,2,3,4,5,6,7,8,9 in d..
[EP 057] 2의 제곱근의 연분수 표현 #!/usr/bin/env python def jarisu(n): su = 0 while n != 0: su += 1 n //= 10 return su bunja = 3 bunmo = 2 count = 0 for i in range(2, 1001): bunja, bunmo = bunja + 2 * bunmo, bunja + bunmo if jarisu(bunja) > jarisu(bunmo): count += 1 print(count) 오일러 프로젝트 57번 문제. 2의 제곱근을 연분수(continued fraction) 모양으로 근사한 분수들(초기 1000항)의 분자와 분모의 자리수 비교하여 분자의 자리수가 분모의 자리수보다 커지는 것의 갯수를 구하는 것. https://daewonyoon.tistor..
Swift codewars 연습문제 gravity swift 문법을 배우면서 연습을 하기 위해서, codewars 문제를 몇 개 풀어보기 시작함. gravity 라는 문제를 풀어봤다. 그냥 숫자로 주어진 리스트를 L 또는 R 인자에 따라 ascending, descending 으로 sort한 결과를 리턴하는 함수를 짜면 된다. 내 풀이는 다음과 같다. func flip(_ direction:String, _ a: [Int]) -> [Int] { if direction == "L" { return a.sorted(by: >) } return a.sorted(by: 와 < 라는 두 람다 중에 하나를 선택하게 했다. 람다를 3항연산자로 선택가능하고 (그것도 간단한 신택스로) 코드가 예뻐서 블로그에서 한번 언급하고 싶었다. codewars 를 풀면, 풀어내는 ..
[EP 047] 소인수분해의 소수의 갯수가 4개 문제는 이렇다. 644는 소인수분해하였을 때, 22 x 7 x 23 으로 세 개의 서로다른 소수로 이루어진다. n, n+1, n+2, n+3 이 모두 네 개의 서로다른 소수로 이루어지는 최소의 n을 구하라. 1부터 차례대로 소인수분해를 해 나가야 하기 때문에, 완전한 소수의 리스트를 관리할 수 있다. 소수판정이 매우 효율적이라서 기쁘다. 또한 소인수분해를 기록하는 리스트도 기록해 나가는데, 일단 하나의 소수만 발견하면 기록된 리스트를 이용해서 매우 효율적으로 원하는 값을 구할 수 있다. 소스를 봐라. # Author : DwYoon # PROJECT EULER # http://projecteuler.net/index.php?section=problems&id=47 # PROBLEM 47 import ti..
[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)) # ..