오일러 프로젝트 62

오일러 프로젝트 62 번 문제는 순열로 이루어진 숫자들 사이에서 세 제곱수가 5번 나오는 수를 찾는 것이다.  60번을 넘어서면서부터는 한국어 사이트의 포럼에서 정답자 수나 코드를 올린 포스트의 수가 격감하는데, 이 문제는 그리 어려운 수준의 문제는 아니다.

오일러 프로젝트 62 더보기

프로젝트 오일러 51

오랜만에 다시 시작하는 프로젝트 오일러 문제이다. 참고로 50번을 넘어서면서부터는 꽤 어려운 문제들이 많이 나오고, 이런 저런 풀이들을 참고해봐도 영 이해가 안가는 문제도 몇 개 있다. (참고로 아직 100번까지는 몇 개 못 푼 문제들이 있어서 과연 몇 번까지 연재할 수 있을지도 모르겠다…) 일단 문제 갑니다…

두자리 숫자 *3 의 첫번째 자리를 여러가지로 바꿨을 때 가능한 아홉가지의 결과 중에서 13, 23, 43, 53, 73, 83의 여섯개는 소수입니다. 56**3의 세 번째와 4번째 자리를 동일한 숫자로 바꿔서 만들어지는 10개의 다섯자리 숫자 중에는 아래에서 보듯이 7개가 소수가 되며, 이것은 이런 식으로 7개의 소수가 만들어지는 첫번째 경우입니다. 이 소수 집단의 첫번째 수인 56003은 이런 성질을 갖는 가장 작은 소수입니다.

56003, 56113, 56333, 56443, 56663, 56773, 56993

위의 예처럼 원래의 일부를 동일한 숫자로 치환했을 때 8개의 소수 집단이 만들어지는 경우를 찾고, 그 집단에 속한 가장 작은 소수를 구하세요. 치환하는 자리는 인접하지 않아도 되고, 가장 앞부분을 치환하는 경우에는 거기에 0은 올 수 없습니다.

문제를 이해하기도 어려운 지경인데…. N 자리 숫자가 있고, 여기서 임의의 몇 개 숫자 위치를 정한 다음, 그 위치에 같은 숫자로 0, 1, 2 … 를 넣어서 만들어진 값이 소수가 되는 경우를 세어서 8개가 나오게 해야 한다. 그리고 그 중에서 가장 작은 소수를 구하는 것이다.

문제에서 8개가 나올 수 있는 숫자집단이 몇 개가 되는지는 언급하지 않고, 그저 “그 중에서 가장 작은 소수”를 찾으라고 했다. (8개 소수조합이 나올 수 있는 케이스가 1개 인지 그 이상인지는 알 수 없다.)

접근

이 문제의 가장 기본적인 접근은 12X45X 와 같은 식으로 치환되는 칸과 고정된 숫자를 조합하여, 템플릿을 만들고 치환되는 칸에 0부터 9까지를 넣고 이것이 소수가 되는지를 판별한다. 그리하여 8개의 소수가 만들어지면, 그 중에서 가장 작은 값을 출력해주면 끝난다.

문제는 2자리의 경우라면 1X 부터 9X 까지 81가지의 경우가 나오는데 치환하는 숫자의 개수가 고정되지 않았기 때문에 전체 자리수가 3자리, 4자리, 5자리로 올라갈 수록 체크해야 할 경우의 수가 급격히늘어난다는 점이 문제이다. 체크할 수 있는 개수를 줄이는 것이 필요한데, 의외로 문제의 조건인 “8개의 소수를 만든다”는 점에 착안해보자.

숫자를 치환해서 발생하는 값의 모든 자리수를 더했을 때, 그 값이 3의 배수가 되면 전체 수는 3의 배수가 된다. 그런데 0~9까지의 숫자를 바꿔가면 최소 4번의 3의 배수가 나타날 수 있다. (0, 3, 6, 9) 만약 치환되는 자리 외의 자리수의 합을 3으로 나눈 나머지가…

  • 0 이면 : 치환되는 숫자가 3의 배수일 때 Fail, 즉 최대 5개까지만 소수를 만들 수 있다.
  • 1 이면 : 치환되는 숫자의 합이 3n + 2 일 때 fail 한다. 역시 최소 3번은 실패한다.
  • 2 이면 : 치환되는 숫자의 합이 3n + 1 일 때 fail 한다. 최소 3번은 실패한다.

따라서 치환되는 숫자에 상관없이 전체 숫자의 합이 3의 배수가 되지 않도록 하는 방법은, 치환되는 숫자의 칸의 개수가 3의 배수개여야 한다.

그외에 마지막 자리 수가 짝수가 아닐 것, 그리고 첫 번째 자리 수는 0이 아닐 것의 조건이 추가될 수 있다.

참고로 원리만 파악하면 구현 자체는 큰 어려움이 없었던 다른 문제들과는 달리, 이 문제는 구현자체의 난이도도 제법 있다고 볼 수 있다.

치환영역 만들기

예를 들어 4자리 수 중에서 고정된 숫자가 ‘345’라고 가정해보자. 이 때 치환 영역의 위치는 X345, 3X45 등으로 다양하게 바뀔 수 있으며, 따라서 어느 위치의 숫자가 치환될 것인지에 따라서 다양한 값의 조합이 나올 수 있다. 이렇게 N 자리에서 m개의 고정 숫자를 제공한다면, 고정숫자와 변경숫자의 자리 조합을 만들어주고, 해당 조합에 따라서 필요한 숫자를 채워넣는 식으로 숫자를 구성하는 함수를 만들어야 한다.

치환 템플릿 생성 함수

먼저 숫자구성을 위한 템플릿을 생성하는 함수를 만들어보자. 0과 1을 사용하여 0은 변경숫자, 1은 고정숫자를 나타내도록하는 템플릿을 생성하는 함수를 만든다. 이건 간단하게 0과 1로 만들어진 문자열을 이용해서 순열을 생성하는 제너레이터를 만들면 되는 것이라, itertools 모듈 내의 permutations 함수를 사용하자.

from itertools import permutations

def make_templates(n):
  '''n자리 숫자에서 3개의 치환영역이 위치할 수 있는 모든 순열을 구한다.'''
  x = '0' * (n-3) + '111'
  return permutations(x)

숫자 생성함수

위에서 작성한 템플릿 생성함수는 N자리 숫자에서 3개의 교환숫자와 고정 숫자의 자리를 각각 0과 1로 표시할 수 있는 모든 조합을 생성하는 제너레이터 객체를 리턴한다. 이를 사용해서, 고정 숫자가 되는 n자리 정수와 (n+3)자리 템플릿을 이용해서 가능한 모든 숫자값을 생성하는 함수를 작성해보자.

루프의 매 반복마다 고정 숫자의 앞에서 하나씩 소모하거나 가변숫자를 쓰게 되므로, 별도의 인덱스를 사용하기 보다는 이터레이터를 얻어서 필요할 때마다 다음 글자를 얻는 식으로 처리했다.

def make_numbers(k, template):
  result = []
  for i in range(10):
    bucket = []
    x = iter(str(k))
    for j in template:
      # 템플릿의 현재 자리가 '0'이면 고정숫자, '1'이면 0~9의 숫자
      bucket.append(next(x) if j == '0' else str(i)) 
    if bucket[0] != '0':
      result.append(int(''.join(bucket)))
  return result

최종 정리

예상하기로는 답은 6자리 숫자에서 나올 것 같긴한데 혹시 몰라서 4, 5, 6자리에서 검사하도록 했다. 따라서 자리수 n을 받아서 해당 자리수에서 조건을 만족하는 값을 찾는 함수를 작성하고 이를 4, 5, 6 자리에서 각각 검사해보자.

참고로 소수검사는 100만 이하에서만 진행하면 되기 때문에 소수판별은 에라스토테네스의 체를 만들어서 검사하는편이 가장 빠를 것이다.

limit = 100_0000 # Python 3.6
seive = [False, False] + [True] * (limit - 1)
for i in range(2, int(limit**0.5)):
  if seive[i]:
    seive[i*2::i] = [False] * ((limit - i) // i)
    
is_prime = lamdba x: seive[x]

소수 판별 검사를 준비했으니, 이제 n 자리에 대해서 8개 조건을 만족하는 소수 그룹을 찾는 함수를 보자.

def p51(n=6):
  ## 6자리라면 가변숫자를 제외하면 3자리 숫자가 필요하므로, 
  ## 10**2 ~ 10**3 범위에서 찾는다.
  for k in range(10**(n-4), 10**(n-3)):
    for template in make_templates(n): # 일단 정해진 고정숫자에 대해서 템플릿별로 확인한다.
      groups = [x for x in make_numbers(k, template) if is_prime(x)]
      if len(groups) == 8:
        print(min(groups))
        return True
  return False

최종적으로는 4, 5, 6, 7 자리에 대해서 찾아본다. 작은 자리부터 확인하고, 실패하면 False를 성공하면 값을 출력하고 True를 리턴하도록 했으니, 성공한 후에 즉시 종료하도록 한다.

def main():
  for n in (4,5,6,7):
    if p51(n):
      return
    
%time main()

개선

대략 5초가까이 걸리는 시간을 좀 더 축약해보자.

  1. make_numbers에서 끝자리가 0,2,4,5,6,8로 끝나는 경우도 제외한다.
  2. 그랬을 때 결과의 수가 8개가 안된다면 어차피 소수검사를 할 필요가 없으니 빈 리스트를 리턴해버린다.
  3. 같은 이유로 템플릿의 끝자리가 가변숫자인 경우에도 []를 리턴해서 숫자를 생성할 필요가 없게 한다.
  4. 고정 숫자 k가 3의 배수라면, 생성되는 값 10개는 모두 3의 배수이므로, 이 부분도 건너뛰도록 한다.

이렇게 축약하면 대략, 1초대에 답을 구할 수 있다.

오일러 프로젝트 47

오일러 프로젝트 47번은 서로 겹치지 않는 소인수를 갖는 자연수가 연속해서 네 번 나오는 경우를 찾는 것이다. 이 문제는 크게 어렵지 않아 보인다. 간단히 어떤 자연수 N을 소인수분해하여 소인수가 4가지 나오고, N+1을 소인수분해하여 소인수가 4가지 나왔을 때 두 자연수의 소인수 사이에 겹치는 값이 없어야 한다. 이렇게 4개의 연속한 자연수가 “그 직전” 수와 겹치는 소인수가 없이 4개씩 나오는 경우를 찾는다. 소인수분해만 할 수 있으면 푸는 것 자체는 어렵지 않지만, C로 작성된 코드로도 40~50초가 걸렸다는 사람이 부지기수일 정도로 성능 최적화 측면에서 상당한 난이도를 자랑하는 문제이다. 오일러 프로젝트 47 더보기

오일러 프로젝트 43

오일러 프로젝트 43 번 문제는 0-9 팬디지털 숫자의 일부분이 특정한 규칙 (4번째 자리부터 세자리씩 끊었을 때 소수로 나눠짐)을 따른다고 할 때, 이런 규칙을 따르는 값 모두를 찾는 것이다.

숫자 1406357289은 0 ~ 9 팬디지털인데, 부분열에 관련된 재미있는 성질을 가지고 있습니다. d1을 첫째 자리수, d2를 둘째 자리수…라고 했을 때, 다음과 같은 사실을 발견할 수 있습니다.

d2 d3 d4 = 406 → 2로 나누어 떨어짐
d3 d4 d5 = 063 → 3으로 나누어 떨어짐
d4 d5 d6 = 635 → 5로 나누어 떨어짐
d5 d6 d7 = 357 → 7로 나누어 떨어짐
d6 d7 d8 = 572 → 11로 나누어 떨어짐
d7 d8 d9 = 728 → 13으로 나누어 떨어짐
d8 d9 d10 = 289 → 17로 나누어 떨어짐

위와 같은 성질을 갖는 0 ~ 9 팬디지털을 모두 찾아서 그 합을 구하면 얼마입니까?

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

접근

문제 자체는 사실 그리 어렵지 않은데, 경우에 따라서 성능이 문제가 될 수 있다. 따라서 다음과 같은 전략을 취한다.

  1. 앞자리 숫자부터 결정한다. 이전에 쓰이지 않은 숫자 중에서 순회하면서 선결 조건을 확인한다. 이 선결 조건이라는 것은 4번째 숫자부터 n – 3 번째 소수로 나눠지는지를 검사하는 것이다. 조건을 만족한다면, 그 숫자를 포함시켜서 다음 숫자를 찾고 그렇지 않은 경우는 이후 과정을 생략한다.
  2. 특정한 자리의 숫자까지 값이 결정된다 하더라도, 답이 하나가 아니다. 따라서 배열이나 세트를 이용해서 값을 수집한다.

결정된 값과 거기에 사용된 숫자. 그리고 지금 a 번째 숫자를 고르려고 할 때 필요한 가드. 이렇게 구성된 함수를 재귀호출하여 간단하게 풀 수 있는 문제이다. 물론 보다 무식한 방법(?)을 통해서 풀어도 된다.

참고로 여기서는 배열보다는 세트를 썼다.

let primes = [2, 3, 5, 7, 11, 13, 17] // 4번째 자리부터 소수로 나눠지는지 계산할 거다

func test(n: Int, seive: Set<Int>) -> Set<Int> {
  // 기저조건 : 채용한 숫자의 개수가 10개면 끝난다.
  guard sieve.count < 10 else { return [n] }

  var result: Set<Int> = []
  var d = sieve.count + 1 // 이번 단계에서 검사할 숫자가 몇 번째인지?
  let xs = (0...9).filter{ !sieve.contains($0) }

  for x in xs {
    // dn에 대하여 이전 3자리 숫자에 대한 검사
    if d > 3, case let y = (n % 100) * 10 + x, y % primes[d-4] != 0 {
      continue
    }
    var newSieve = sieve
    newSieve.insert(x)
    if case let temp = test(n: n * 10 + x , sieve: newSieve), !temp.isEmpty {
      result = result.union(temp)
    }
  }
  return result
}

처음에는 레벨값을 별도의 변수로 두려 했는데, 몇 번째 숫자를 체크할 것인가에 대해서 레벨값이 엄청 헷갈려서 그냥 이전까지 사용한 숫자의 개수로 이를 판별하도록 했다. 다음과 같이 코드가 정리되며 매우 빠르게 끝난다.

do {
  var s = 0
  for i in 1...9 { // 첫번째 숫자에는 0이 오지 않는다.
    if case ns = test(n: i, sieve: [i]), !ns.isEmpty {
      s += ns.reduce(0, +)
    }
  }
  print(n)
}

파이썬 풀이

재귀로 푸는 법은 Swift에서 확인했으니, 이번에는 무식하게 리스트 축약으로 푸는 법을 알아보자. 엄청 무식해보이기는하는데, 상당히 빠르게 계산된다.  (0.1초 대)

## Python 3.6
def check(a, b, c, d):
  return int(f"{a}{b}{c}") % d is 0

def solve():
  r = [(d1, d2, d3, d4, d5, d6, d7, d8, d9, 10)
        for d1 in range(1, 10)\
        for d2 in range(10) if d2 != d1\
        for d3 in range(10) if d3 not in (d1, d2)\
        for d4 in range(0, 10, 2) if d4 not in (d1, d2, d3)\
        for d5 in range(10) if d5 not in (d1, d2, d3, d4)\
                            and check(d3, d4, d5, 3)\
        for d6 in (0, 5) if d6 not in (d1, d2, d3, d4, d5)\
        for d7 in range(10) if d7 not in (d1, d2, d3, d4, d5, d6)\
                            and check(d5, d6, d7, 7)\
        for d8 in range(10) if d8 not in (d1, d2, d3, d4, d5, d6, d7)\
                            and check(d6, d7, d8, 11)\
        for d9 in range(10) if d9 not in (d1, d2, d3, d4, d5, d6, d7, d8)\
                            and check(d7, d8, d9, 13)\
        for d10 in range(10) if d10 not in (d1, d2, d3, d4, d5, d6, d7, d8, d9)\
                            and check(d8, d9, d10, 17)
  ]
  result = [reduce(lambda x, y: x*10+y, case) for case in r]
  print(sum(result))