프로젝트 오일러 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초대에 답을 구할 수 있다.

정수 배열의 최대 부분합 (연습문제)

배열의 연속된 부분집합의 최대합

정수 배열이 주어질 때 배열내의 연속된 원소를 더한 부분합의 최대값을 구하는 문제이다. 구간이 아닌 최대값 자체를 구하면 되는 문제이다.

간단히 생각하면 0부터 1, 2, 3 … n 까지의 합 중 최대인 값, 그 다음은 1부터 2, 3, 4 .. n 까지의 값 중 최대인값 이렇게 비교해나갈 수 있는데 그러면 반복계산이 너무 많다. 따라서 DP를 이용한다.

  1. 0번 인덱스까지의 최대합은 0번 값 그 자체이다.
  2. i번 인덱스까지의 최대 부분합은, (i-1) 번 까지의 최대 부분합과 i번 값의 합이다. 이 때 이전인덱스까지의 최대부분합이 0보다 작으면 더하지 않는다.

이렇게 하면 되지롱


func maxSubsum(arr: [Int]) -> Int {
    var result = Array(count: arr.count, repeatedValue: 0)
    result[0] = arr[0]
    for i in 1..<arr.count {
        result[i] = (result[i-1] > 0 ? result[i-1] : 0) + arr[i]
    }
    return result.reduce(result[0], combine: max)
}

참고로 swift3에서는 Array(count:repeatedValue:)Array(repeating:count:)로 인자의 위치가 뒤집어 졌으니 참고.

연습문제(벽과 폭탄)

벽과 폭탄

각 테스트 케이스마다 ‘W’, ‘B’로 이루어진 문자열이 입력된다. B는 폭탄을, W는 벽을 의미하는데, 폭탄이 하나 터지면 폭탄을 중심으로 반경 2칸 이내의 벽이 모두 폭파된다. 이 때 폭탄이 일시에 터졌을 때 폭파되는 벽의 개수를 출력하라. (https://www.hackerearth.com/problem/algorithm/bob-and-bombs-cake-walk/description/)

BWW, BW, WB, WWB에 해당하는 W의 수를 세는 문제이므로, 이는 간단하게 정규식으로 해결할 수 있다.

연습문제(벽과 폭탄) 더보기

Fast Fibonacci Transform

빠른 피보나치 항 구하기

피보나치 수열은 0, 1, 1, 2, 3, 5, 8,… 과 같이 앞의 두 항의 합이 그 앞의 항이 되는 수열이다. 피보나츼 수열의 n 항을 구하는 함수는 보통 이렇게 많이 작성한다.

def fib(n):
    if n < 3:
        return (0, 1)[n]
    return fib(n-1) + fib(n-2)

하지만 이 함수는 지극히 비효율적이라

%time fib(35)
Wall time: 7.05 s
Out[7]: 9227465

이런 처참한 성능이 나온다. 이는 한 번 계산했던 값을 계속 재계산하기 때문인데, 이런 문제를 피하기위해서는 메모이제인션이라는 캐싱 기법을 쓴다.

# 메모이제이션을 위한 데코레이터 함수
def memoize(f):
    cache = {}
    def inner(arg):
        if arg in cache:
            return arg
        return cache.setdefault(arg, f(arg))
    return inner

# 메모이제이션을 적용한 피보나치 항 구하기
@memoize
def fib_cached(n):
    if n < 2:
        return (0, 1)[n]
    return fib(n-2) + fib(n-1)


# 그 결과는
%time fib_cached(300)
Wall time: 1 ms
Out[6]: 44552

상당히 준수하다. 하지만 이 방법은 치명적인 약점이 있는데, 그만큼 많은 메모리 공간을 캐시로 쓴다는 점과, 재귀에 기반하기 때문에 처음부터 너무 큰 값을 계산하는 경우 재귀 깊이의 한계에 빠지게 된다. (n = 30,000 일 때를 처음부터 계산할 수 없음)

dp 기법을 이용하는 방법도 있다. 이 역시 메모리를 부가적으로 쓰긴하지만, 캐싱보다도 더 빠르며, 재귀 한계에 대한 위험이 없다.

def fib_dp(n):
    ns = [1, 1] + [0] * (n - 1)
    for i in range(2, n+1):
        ns[i] = ns[i-2] + ns[i-1]
    return ns[n]

# 1000 loops, best of 3: 279 µs per loop

피보나치 수열은 단순히 앞의 두 값을 더한 값이 그 다음항이 되기 때문에 dp 대신 값을 바꿔나가는 방법으로 다음과 같이 구현해도 된다. 이는 추가적인 메모리를 더 쓰지 않는다.

def fib_f(n):
    a, b = 1, 1
    for _ in range(n):
        a, b = b, a + b
    return a

%timeit fib_f(1000)
10000 loops, best of 3: 108 µs per loop

되려 메모이제이션을 쓰는 것보다 빠르다.

하지만 이보다도 더 빠른 방법이 있으니, 그것은 빠른 피보나치 변환을 쓰는 것이다.

def multiply(x, y):
    a, b = x
    c, d = y
    return (a*c + b*d, a*d + b*c + b*d)

def power(x, n):
    if n is 0:
        return (1, 0)
    if n % 2 == 0:
        return power(multiply(x, x), n // 2)
    return multiply(power(multiply(x, x), n // 2), x)

def fib_fast(n):
    return power((1, 1), n)[0]

백만번째 항을 계산하는데, 빠른 피보나치 변환을 계산한 결과는 1.5초 가량이며, 앞에서부터 계산한 결과는 14초가 넘어간다. 거의 10배의 결과인데, 이는 큰 값에서는 빠른 피보나치 변환 알고리즘이 강력함을 발휘한다고 볼 수 있다. 하지만 어느정도 규모 이하의 값에서는 앞에서부터 계산하는 방식이 좀 더 간편하고 빠르게 써먹을 수 있을 것 같다.

체를 사용하여 소수 집합 구하기

가장 빠른 알고리듬

현재까지 순수 파이썬으로 작성된 알고리듬 중 가장 빠른 것으로 알려진 것은 @Robert William Hanks가 개발한 아래 알고리듬이다.

def primes(n):
    """Return a list of primes under n"""
    sieve = [True] * (n/2)
    for i in xrange(3, int(n**0.5)+1, 2):
        if sieve[i/2]:
            sieve[i*i/2::i] = [False] * ((n-i*i-1)/(2*i)+1)
    return [2] + [2*i+1 for i in xrange(1, n/2) if sieve[i]]