콘텐츠로 건너뛰기
Home » 오일러 프로젝트 14

오일러 프로젝트 14

우박수

양의 정수 n에 대하여, 다음과 같은 계산 과정을 반복하기로 합니다.
n → n / 2 (n이 짝수일 때)
n → 3 n + 1 (n이 홀수일 때)
13에 대하여 위의 규칙을 적용해보면 아래처럼 10번의 과정을 통해 1이 됩니다.
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
아직 증명은 되지 않았지만, 이런 과정을 거치면 어떤 수로 시작해도 마지막에는 1로 끝나리라 생각됩니다.
(역주: 이것은 콜라츠 추측 Collatz Conjecture이라고 하며, 이런 수들을 우박수 hailstone sequence라 부르기도 합니다)
그러면, 백만(1,000,000) 이하의 수로 시작했을 때 1까지 도달하는데 가장 긴 과정을 거치는 숫자는 얼마입니까?
참고: 계산 과정 도중에는 숫자가 백만을 넘어가도 괜찮습니다.

백만 이하의 모든 자연수에 대해서 우박수열을 구하고, 그 중에서 우박수열이 가장 긴 값을 찾아야 한다. ‘최대’, ‘최소’와 관련이 있기 때문에 전수 검사가 필요하다. 우박수열의 길이를 구하는 것은 아주 간단한 문제이지만, 이 과정을 백 만 번 돌려봐야 하는 것은 다른 문제다.

단순한 접근방법

우박수열의 길이를 구하는 가장 단순한 방법은 문제에서 제시한대로 n 값을 변화시키면서 c를 매번 1씩 증가시키고 이를 n이 1이 될때까지 이걸 반복하는 것이다. (1일 때의 길이를 1이라고 했으므로 카운터의 초기값은 1이어야 한다.) 우박수열의 길이를 구하는 함수는 아래와 같이 매우 단순하다.

def hail(n: int) -> int:
  c = 1
  while n > 1:
    c, n = c + 1, n // 2 if n % 2 == 0 else n * 3 + 1
  return c

함수 자체는 무척 간단하지만, 백 만번을 돌아서 최대값을 찾아야 하기 때문에 전체 수행 시간은 제법 오래 걸린다. (이 글을 처음 작성한 후로 몇 년이 지났고, 더 좋은 시스템에서 돌려보지만 여전히 10초 이상 걸린다)

%time print(max(((hail(x + 1), x + 1) for x in range(100_0000)))

메모이제이션

수행시간을 단축시켜보자. 이런 간단한 경우를 한 번 생각해보도록 하자. 3으로 시작하여 1까지 가는 과정은 아래와 같이 8단계가 된다. 만약 우리가 이 사실을 미리 알고 있다면 6으로 시작하는 경우에는 9단계가 될 것이라는 걸 쉽게 알 수 있다. 왜냐하면 6은 3으로 변하고, 이후의 우박수열은 완전히 동일할 것이기 때문이다.

# 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 (8단계)
# 6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1 (9단계)

즉 우박수열을 전개하나가는 중에 앞서 1까지 다다른 수열의 길이를 알고 있는 값을 만나면 더 이상 계산을 하지 않아도 된다는 것이다. 이를 위해서 메모이제이션을 적용할 수 있다. 메모이제이션을 적용하는 가장 간단한 방법은 캐시로 사용할 사전의 값을 맨 앞에서 검사하고, 사전에 없는 결과를 리턴하기 직전에 캐시에 추가하는 것이다.

# hails function with simple and bad memoization

cache = {1:1}
def hails(n):
  c, m = 1, n
  while m > 1:
    if m in cache:
      c += cache[m]
      break
    m = m // 2 if m % 2 == 0 else m * 3 + 1
    c += 1
  cache[n] = c
  return c

하지만 이 코드는 (물론 이대로 써도 어느 정도 성능향상이 있긴하다) 불완전하다. 왜냐면 hail(6) 이 호출된 후 hail(3)의 결과를 사전으로부터 얻을 수 있게 되지만, 10, 5, 16 등의 값은 캐시에 그 때 담기지 않기 때문이다. 따라서 캐시의 효율을 높이기 위해서는 hail() 함수를 재귀의 꼴로 변형할 필요가 있다. 그러면 이전에 거치는 모든 우박수열의 수는 함수의 파라미터로 전달되고 모든 결과가 캐시에 기록된다.

cache = {1:1}
def hail(n: int) -> int:
  if n in cache:
    return cache[n]
  r = 1 + hail(n // 2 if n % 2 == 0 else n * 3 + 1)
  cache[n] = r
  return r

%time print(max(((hail(x + 1), x + 1) for x in range(100_0000)))

이렇게하면 하나의 n에 대해서 우박수 경로를 구할 때, 그 과정에 등장하는 모든 수에 대한 우박수열 길이를 기록하게 된다. 그만큼 많은 데이터를 캐시에 기록하게 될 것이고, 불필요한 반복을 그만큼 줄이게 된다.