Project Euler

프로젝트 오일러 014

프로젝트 오일러 14번, 백만 이하의 시작 숫자 중 가장 긴 우박수(Collatz sequence)를 생성하는 수를 찾는 문제입니다. 우박수 계산 과정을 설명하고, 메모이제이션을 활용하여 성능을 최적화하는 파이썬 풀이를 제시합니다.

4분
#project euler #python

콜라츠 수열은 ‘우박수’라는 이름으로 더 많이 알려져 있습니다. 구름속에서의 우박 알갱이의 움직임처럼 마구잡이로 오르내리기 때문입니다. 수열의 점화식은 현재 항이 홀수인지 짝수인지에 따라 다음 수를 계산하는 식을 다르게 사용합니다.

  1. 어떤 수가 짝수라면 다음 수는 그 수를 2로 나눈 몫입니다.
  2. 어떤 수가 홀수라면 다음 수는 그 수에 3배하고 1을 더한 값입니다.

어떤 수로부터 이 수열을 계속 전개해나가면 1에 이루는 것으로 추측됩니다. 우박수가 1에 다다르는 과정은 결국 최종적으로는 2의 거듭제곱 중 하나에 도달하면 경로를 취하게 됩니다.

점화식

어떤 수열에 대해 점화식이 알려져 있다면, 이 수열은 재귀를 통해서 코드로 표현할 수 있습니다. 사실 점화식과 재귀는 동일한 것으로 생각할 수 있습니다. 점화식의 조건을 생각하면 재귀 코드를 작성하는 방법도 명확하게 이해할 수 있습니다.

  1. 더 이상 ‘이전 항’이 존재하지 않는 초기 조건을 명시합니다. 재귀에서는 이걸 ‘기저 케이스’라고 합니다.
  2. 점화식을 코드로 표현합니다.

사실 이것이 전부입니다. 그래서 복잡해 보이는 로직도 재귀를 사용하면 코드가 짧고 상당히 간단하고 깔끔하게 정리됩니다.

어떤 수 N으로부터 시작하여 1에 도달하는 진행 과정의 수를 나타내는 수열을 F(N)이라 한다면, 이는 다음과 같이 파이썬 코드로 표현할 수 있습니다.

python
def F(n):
	if n == 1:
		return 1
	if n % 2 == 0:
		return F(n // 2) + 1
	return F(n * 3 + 1) + 1

재귀의 최대 깊이

파이썬에서 재귀를 사용할 때에는 한 가지 주의해야 하는 점이 있습니다. 바로 재귀의 최대 깊이가 1000을 넘을 수 없다는 것입니다. 재귀 깊이가 이를 초과하면 예외가 발생하면서 프로그램이 중단됩니다. 이 제한을 피하는 방법은 재귀를 반복문으로 변경하는 것입니다. 그 외에도 이전 계산 결과를 캐싱하여, 1000 이상의 항임에도 캐싱된 결과를 사용하여 실제 재귀 깊이를 더 줄이는 방법도 있습니다.

우박수

우박수열을 구하는 데 필요한 설명은 앞에서 다 한 것 같습니다. 우박수열은 현재항이 홀수일 때, 짝수일 때의 점화식이 다릅니다. n으로부터 1에 다다를 때까지의 우박수열의 길이를 구하는 함수 F(n)은 다음과 같이 정의할 수 있습니다.

python
def F(n):
  c = 1
  while n > 1:
    if n % 2 == 0:
      n = n // 2
    else:
      n = n * 3 + 1
    c += 1
  return c

코드는 더할 나위 없이 단순하지만, 우리의 상황은 그렇지 않습니다. ‘최대가 된다’는 것을 보장하려면 전수 검사를 해야 한다는 것을 의미합니다. 1백만 이하의 모든 자연수에 대해서 우박수열의 경로를 조사하고, 그 길이를 모두 비교해야 합니다. 해야 할 일이 많지만, 파이썬에서 이 과정은 사실 단 한줄로 표현할 수도 있습니다.

python
print(max((F(n), n) for n in range(1, 200_0001))[1])

그런데 이 방법은 매우 느리기 때문에 시간을 단축할 수 있는 최적화 방법을 찾아야 합니다.

캐시

백만 이하의 모든 수에 대해 이 과정을 추적하는 것은 상당한 시간이 필요할 것으로 예상됩니다. 소수 판정 같은 경우에는 이런 저런 최적화할 수 있는 지식이 동원되었습니다만, 우박수에 대해서는 예측이 힘든 부분이 많아 더 이상의 최적화는 어려울 것으로 예상됩니다. 하지만 이런 수열과 관련된 문제에서는, “어? 한 번 계산한 걸 또?”하는 시점이 있습니다.

예를 들어 200과 33을 봅시다. 200의 다음 항은 100입니다. 33의 다음항도 100입니다. 이는 200과 33이 같은 우박수 길이를 갖는다는 사실보다, 33에 대해 우박수 길이를 계산해보면, 다른 숫자의 우박수 길이에 대해서도 알게 된다는 것입니다. 실제로 33부터 시작하는 우박수열은 제법 긴 과정을 거치며, 다음과 같은 수가 등장합니다.

  • 33 > 100 > 50 > 25 > 76 > 38 > 19 > 58 > 29 > 88 > 44 > 22 > 11 > 34 > 17 > 52 > 26 > 13 > 40 > 20 > 10 > 5 > 16 > 8 > 4 > 2 > 1

이 과정에서 34가 등장하니, 34의 우박수 과정은 사실상 계산할 필요가 없을 수 있습니다. 이전에 벌써 계산해본 적이 있으니까요. 이처럼 이미 계산한 값을 기록해두었다가 사용하는 것을 ‘메모이제이션’이라고 합니다.

python

cache = [1:1]

def F(n):
	if n in cache:
		return cache[n]
	r = (F(n // 2) if n % 2 == 0 else F(n * 3 + 1)) + 1
	cache[n] = r
	return r

메모이제이션으로 이 과정의 계산을 반복하지 않으려면 중간 계산 결과에서도 캐시된 값을 사용할 수 있어야하기 때문에 반복문 보다는 재귀 형식으로 코드를 작성해야 효과가 있습니다. 계산 과정에서 발생하는 값에 대한 계산 결과 역시, 계속해서 캐시되므로 계산이 진행될수록 캐시가 적중하는 비율이 올라가며 시간 단축 효과가 더 많이 발생할 것입니다.

초기 캐시

N이 짝수인 경우에는 2로 나누는 연산을 합니다. 따라서, 2, 4, 8, 16, .. 등 2의 거듭제곱수들은 계속 절반으로 나눠진 후 1에 도달하게 됩니다. 즉 인 수는 의 길이의 우박수 경로를 갖습니다. 이는 계산해보지 않아도 알 수 있으므로 미리 캐시에 기록하여 성능을 향상시킬 수 있습니다.

python
cache = {2**n:n + 1 for n in range(30)}

def F(n):
	if n in cache:
		return cache[n]
	r = (F(n // 2) if n % 2 == 0 else F(n * 3 + 1)) + 1
	cache[n] = r
	return r

정렬하기

이 문제는 최대가 되는 단계의 수를 구하는 것이 아니라, 단계의 수가 최대인 값을 구하는 문제입니다. max() 함수는 개별 값 뿐만 아니라 짝지어진 튜플도 비교할 수 있습니다. 튜플의 비교는 첫번째 요소부터 비교하고, 첫번째 요소가 같다면 그 다음 요소를 순서대로 비교합니다. 따라서 (F(n), n) 을 비교하여 최대치를 구하면 F(n)이 최대일 때의 n도 알 수 있게 됩니다.

python
print(max((F(n), n) for n in range(1, 100_0001))[1])