오일러 프로젝트 39

원문 : http://euler.synap.co.kr/prob_detail.php?id=39

 

세 변의 길이가 모두 자연수 {a, b, c}인 직각삼각형의 둘레를 p 로 둘 때, p = 120 을 만족하는 직각삼각형은 아래와 같이 세 개가 있습니다.

 

{20, 48, 52}, {24, 45, 51}, {30, 40, 50}

 

p가 1000이하일 때, 세변의 길이가 모두 자연수인 직각삼각형을 가장 많이 만들 수 있는 p의 값은 얼마입니까?

오일러 프로젝트 39 더보기

오일러 프로젝트 38

오일러 프로젝트 38 번 문제는 반복된 곱셈의 결과를 이어 붙인 것이 1-9 팬디지털 숫자를 만들어 내는지를 보고, 그렇게 만들어지는 팬디지털 숫자중에 가장 큰 값을 찾는다. 문제 그대로를 코딩하면 되는 것이기도 하고 검사 범위도 매우 좁기 때문에 1도 어렵지 않은 문제이다.

숫자 192에 1, 2, 3을 각각 곱합니다.

92 × 1 = 192
192 × 2 = 384
192 × 3 = 576

곱한 결과를 모두 이어보면 192384576 이고, 이것은 1 ~ 9 팬디지털(pandigital)인 숫자입니다. 이런 과정을 편의상 ‘곱해서 이어붙이기’라고 부르기로 합니다. 같은 식으로 9와 (1, 2, 3, 4, 5)를 곱해서 이어붙이면 918273645 라는 1 ~ 9 팬디지털 숫자를 얻습니다. 어떤 정수와 (1, 2, … , n)을 곱해서 이어붙였을 때 얻을 수 있는 가장 큰 아홉자리의 1 ~ 9 팬디지털 숫자는 무엇입니까? (단 n > 1) (http://euler.synap.co.kr/prob_detail.php?id=38)

 

접근

어떤 수 N에 대해서 1부터 9사이의 값 i (1, 2, 3 .. 9) 와 곱한 결과들을 모아서 팬디지털이 되는지 검사한다. 즉 문제의 내용 그대로를 코딩하면 된다.

  1. 임의의 수 n에 대해서
  2. 1, 2, 3..을 차례로 곱해나가면서, 곱한 값을 연결한다.
  3. 2의 과정을 반복하다가 결과가 9자리 이상이 되면 1-9 팬디지털인지 검사한다.

참고로 범위는 어떻게 정할까? 6자리의 경우 1, 2를 곱해서 붙이면 기본 12자리가 되므로 실패. 따라서 5자리 범위까지만 테스트한 후 최대값을 찾으면 되겠다.

def test(n):
    s = ""
    for i in range(1, 10):
        s += str(i * n)
        if len(s) >= 9:
            break
    if "".join(sorted(s)) == "123456789":
        return s
    return None

def e038():
    print(max(test(x) for x in range(1, 100_000) if test(x)))

%time e038()

Swift 풀이

동일한 알고리듬이다. 사실 펜디지털 숫자를 만들 수 있냐 없냐를 가지고 파이썬의 test 함수가 문자열 혹은 None 을 리턴했는데, 이는 옵셔널을 리턴하는 함수의 컨셉과 일치한다. 그리고 이렇게 이어진 결과에서 non-nil인 결과만을 추려내고 싶다면 flatMap을 쓰는 것이 가장 간편하다.

// Swift 4.0
func test(_ n: Int) -> String {
  var s = ""
  for i in 1...9 {
    s += "\(n * i)"
    if s.count >= 9 { break }
  }

  // 문자열을 정렬하는 것은 유니코드 문자배열을 정렬한 것이므로 [Chracter] 타입이 된다. 
  // 따라서 이는 Characater의 시퀀스이므로 String으로 바로 만들 수 있다.
  if String(s.sorted()) == "123456789" { return s } 
  return nil
}

print((1...99999).flatMap(test).max()!)

오일러 프로젝트 37

오일러 프로젝트 37 번 문제는 순환소수와 약간 비슷하지만, 의외로 성가신 구석이 매우 많은 문제이다. 동시에 잘 설계된 가드가 얼마나 수행 속도를 빠르게 만들어줄 수 있는지에 대한 좋은 예이기도 하다.

오일러 프로젝트 37 더보기

오일러 프로젝트 36

오일러 프로젝트 36 번은 대칭수에 대한 문제이다. 대칭수는 이전에도 몇 번 나왔던 문제이다.

대칭수(palindrome)인 585는 2진수로 나타내도 10010010012가 되어 여전히 대칭수입니다. 10진법과 2진법으로 모두 대칭수인 1,000,000 이하 숫자의 합을 구하세요. (주의: 첫번째 자리가 0이면 대칭수가 아님)

http://euler.synap.co.kr/prob_detail.php?id=36

오일러 프로젝트 36 더보기

오일러 프로젝트 35

오일러 프로젝트 35 번 문제는 순환하는 소수에 대한 내용이다.

소수 중에서 각 자리의 숫자들을 순환시켜도 여전히 소수인 것을 circular prime이라고 합니다. 예를 들어 197은 971, 719가 모두 소수이므로 여기에 해당합니다. 이런 소수는 100 밑으로 2, 3, 5, 7, 11, 13, 17, 31, 37, 71, 73, 79, 97 처럼 13개가 있습니다. 그러면 1,000,000 밑으로는 모두 몇 개나 있을까요?

http://euler.synap.co.kr/prob_detail.php?id=35

접근

먼저 순환하는 수를 어떻게 만들 수 있을까? (문자열로 변환) -> (앞글자를 떼어) -> (맨뒤에추가) -> (정수로변환) 하는 작업을 해도 되는데, 괜히 깔끔하지가 못하고 너저분한 느낌이다. 문자열의 개입없이 이걸 처리할 수 있을까? 10진수의 자리 숫자와 관련된 작업에는 로그(log)가 등장하면 된다. 예를 들어 423의 상용로그값은 약 2.6263인데, 여기서 정수 부분만 취해서 1을 더하면 423이 몇 자리 수인지를 알 수 있게 된다. 따라서 10으로 나눈 나머지와 몫을 가지고서 이 나머지에 원래 수의 상용로그의 정수부만큼 10을 거듭곱하여 더하면 끝자리 수를 앞으로 이동시킨 값이 된다.

from math import log10
a = 423
n = int(log10(a))
q, r = divmod(a, 10)
b = r * (10**n) + q
print(b) # 342

이 동작을 계산중에 나오는 n (자리수)만큼 반복해서 변환된 숫자가 소수인지를 판단하면 된다.

개선 포인트

성능 개선을 위한 포인트는 다음과 같다.

  1. 모든 순환 버전을 소수인지 검사한다. 따라서 0, 2, 4, 6, 8 이 포함된 숫자라면 이 들 숫자가 1의 자리에 오는 시점에 짝수로서 검사를 통과못하게 된다. 이를 이용하면 빠르게 탈락여부를 결정할 수 있다.
  2. 같은 원리로 5가 포함된 경우도 빠른 탈락
  3. 당연한 이야기지만, 백만번의 (혹은 짝수는 거른다 생각해서 양보하면 50만번)의 루프를 돌 필요도 없다. 처음에 출발하는 수 자체가 소수여야하므로, 에라토스테네스의 체를 만들어서 소수집합에서 원소를 꺼내어 검사하면 된다.

순환하는 수를 만드는 건 쉽다. 자리수에 해당하는 10의 제곱수로 나눈 몫과 나머지를 가지고 나머지*10 + 몫으로 순환시킨다. 검사를 빠르게 하기 위해 소수채를 만들고 여기에 있나 없나를 검사한다.

from math import log10, floor

def prime_sieve(bound):

    sieve = [True] * (bound//2)
    for i in range(3, int(bound**.5)+1, 2):
        if sieve[i//2]:
            sieve[i * i // 2::i] = [False] * ((bound - i * i - 1) // (2 * i) + 1)
    return [2] + [2*i+1 for i in range(1, bound // 2) if sieve[i]]

def e35():
    def check(n):
        k = str(n)
        for c in "024568":
            if c in k:
                return False
        c = int(log10(n))
        l = 10**c
        m = n
        for _ in range(c+1):
            q, r = divmod(m, l)
            m = r * 10 + q
            if m not in s:
                return False
        return True

    s = set(prime_sieve(1000000))
    b = [2,5] + list(filter(check, s)) // 2, 5는 자리 숫자 검사에서 탈락하므로, 예외적으로 추가
    print(len(b))

%time e35()
# Wall time: 208 ms

보너스 : Swift 풀이

Swift에서 에라토스테네스 체를 만드는 부분과, 로그 연산등을 수행하는 부분을 살펴보자. 로그 연산은 Foundation을 통해서 C 라이브러리의 함수를 그대로 사용한다.

// Swift 4
import Foundation

// 소수체를 만들자
let limit = 999_999
let sieve: [Bool] = {
  var s = [false, false] + Array(repeating: true, count: limit)
  for k in 2...limit where s[k] {
    for j in stride(from: k*2, through: limit, by: k) { s[j] = false }
  }
  return s
}()

let isPrime: (Int) -> Bool = { sieve[$0] }
let primes = (0...limit).filter{ sieve[$0] }


func test(_ n: Int) -> Bool {
  // 먼저 글자로 체크한다.
  var n = n
  let s = String(n)
  for c in "024568" {
    if s.contains(c) { return false }
  }
  // 자리수 및 가장 앞자리로 옮기기 위해 필요한 값
  let c = floor(log10(Double(n)))
  let l = Int(pow(10, c))
  // 자리수를 돌려가며 검사한다.
  for _ in 0..<Int(c) {
    let (q, r) = (n / 10, n % 10)
    n = r * l + q
    if !isPrime(n) { return false }
  }
  return true
}    

main: do {
  let result = [2, 5] + primes.filter(test)
  print(result.count)
}