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

오일러 프로젝트 14

오일러 프로젝트 14 번 문제는 우박수에 관한 내용이다. 이 문제는 간단한 재귀함수와 메모이제이션을 통한 최적화 문제인데, 범위가 1~1백만으로 제법 크기 때문에 조금 더 깊은 고민이 필요하다. 또한 Swift에서는 단순한 메모이제이션 함수를 쓰는 경우, 재귀함수에서는 파이썬처럼 동작하지 못하기 때문에 특별한 형태의 메모이제이션 함수가 필요하다. 재귀함수를 위한 메모이제이션 함수를 어떻게 작성하는지에 대해서도 알아볼 것이다.

양의 정수 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까지 도달하는데 가장 긴 과정을 거치는 숫자는 얼마입니까?
참고: 계산 과정 도중에는 숫자가 백만을 넘어가도 괜찮습니다.

접근
우박수의 루트의 길이를 구하는 것은 재귀식으로 간단하게 표현할 수 있다.
Hn = \begin{cases} 1 , (\text{  if  } n = 1) \\ H_{n/2} + 1 (\text{  if  } n \mod 2 = 0) \\ H_{3 \cdot n + 1} + 1 (\text{  if  } n \mod 2 = 1) \end{cases}
따라서 다음과 같은 간단한 재귀함수로 우박수의 루트를 구할 수 있다.

def hail(n):
  if n < 2:
    return 1
  if n % 2 is 0:
    return hail(n//2) + 1
  return hail(n*3+1) + 1

하지만 백만 개의 수에 대해서 우박수 경로를 찾아야 하기 때문에 어느 정도 최적화가 필요하다. 만약 호출되는 과정에서 이전에 찾았던 값이 나온다면 재귀 체인을 따라가지 않고 즉시 끊고 나오도록 하여 속도를 높여보자. 일종의 메모이제이션이다. (그래도 100만 사이의 값을 검사하기 때문에 시간이 제법 걸리는 점은 어떨 수 없다.)

def solve():
  memo = {1:1}
  def hail(n):
    if n < 2: return 1
    if n in memo: return memo[n]
    m = n // 2 if n % 2 is 0 else n * 3 + 1
    r = hail(m) + 1
    memo[n] = r
    return r
  ## 풀이 시작
  limit = 100_0000
  ways = [(x, hail(x) for x in range(1, limit+1)]
  ans = max(ways, key=lambda x: x[1])
  print(ans[0])
%time solve()
## Wall time 3.21 s

Swift의 메모이제이션

Swift의 경우에는 최적화를 위해서 좀 이상한(?) 짓을 해야 한다.  먼저 hail 함수는 Swift에서 다음과 같이 작성가능하다.

func hail(_ n: Int) -> Int {
  if n < 2 { return 1 }
  let m = (n % 2 == 0) ? n / 2 : 3 * n + 1
  return hail(m) + 1
}

이 함수의 성능을 높이기 위해서 메모이제이션 할 수 있는 함수를 만들어보자. 이런 함수는 파이썬에서도 흔히 데코레이터로 만들었던 것이라 별로 어렵지 않다.

func memoize <T: Hashable, U> (_ f: @escaping (T) -> U) -> (T) -> U {
  var memo = [T:U]()
  return { n in
    if let r = memo[n] { return r }
    let r = f(n)
    memo[n] = r
    return r
  }
}

참쉽죠? 예를 들어서 임의의 정수의 소수 여부 판별이라든지 그런 경우는 함수를 이용해서 쉽게 메모이제이션 할 수 있다. 그런데 hail 함수는 좀 애매한 구석이 있다. 바로 함수 스스로가 재귀호출을 한다는 것이다. 따라서 다음과 같이 적용했을 때를 보자.

let memoized_hail = memoize(hail)
print(memoized_hail(13)) // 10
print(memoized_hail(10)) // 7

위 예에서 13에 대해 우박수 경로를 계산할 때, 10이 경로에 포함된다. 하지만 해당 시점에 10에 대한 값은 캐싱이 되지 않는다. memoized_hail(13)이 실행되는 경로를 추적해보자.

  1.  memoized_hail 에 인자값 13이 전달되어 호출된다.
  2. 참조된 사전 memo 에는 13에 대한 값이 없다. 그래서 hail(40) 이 호출된다. 그런데 memoized_hail 이 아닌 hail 은 메모이제이션을 적용받지 않는다. 따라서 이 함수가 최종 리턴하는 시점에는 키 ’13’에 대한 결과만 캐싱되며, 중간과정이 캐싱되지 않는다.

이를 어떻게 개선할까? 개선을 위해서는 메모이제이션을 적용받은 함수가 재귀호출을 할 때 원형이 아닌 메모이제이션을 적용받은 함수를 호출해야 한다. 이를 위해서 memoize 함수를 수정하기 전에 어떤식으로 호출되어야 할지를 먼저 생각해보자.

재귀 호출하는 함수의 메모이제이션

대략 다음과 같은 식으로 원형 내에서 메모이제이션이 적용된 함수를 호출하도록 해야 한다.

let memoized_hail: (Int) -> (Int) = memoize{  n in 
    if n < 2 { return 1 }
    let m = (n % 2 == 0) ? n / 2 : 3 * n + 1
    return memoized_hail(m)
}

그런데  이 코드는 문제가 있다. 코드의 클로저에서 memoized_hail 을 호출하는데, 이는 현재 정의하려는 클로저 선언의 좌변이며, 따라서 클로저가 생성되는 시점에서는 선언된 바가 없다. 따라서 최초 선언식의 우변에서 자신을 참조하기 때문에 에러가 된다. 어떻게 이를 해결할 수 있을까? 다음과 같이 클로저 표현을 수정해본다면?

let hail: (Int) -> Int = memoize{ memoized_hail, n in
  ...
  return memoized_hail(m)

즉, 메모이제이션을 적용할 함수 원형이 인자로 메모이제이션이 적용된 클로저를 받아서 내부에서 참조하는 것이다. 어떻게 이걸 가능하게 할까? 이 클로저가 memoize() 함수 내부로 전달될 인자라는 점에 주목하자. 이 값 자체는 함수의 리턴값인 동시에, 리턴하기 전에 어떤식으로든 선언해두고 클로저 내부에서 참조되면 된다. 따라서 memoize() 함수는 다음과 같은 식으로 생겨야 할 것이다.  (완전한 코드가 아니라 와꾸를 보는 것이다.) 먼저 위에서 memoize 함수로 전달되는 클로저의 타입을 보면

  1.  메모이제이션이 적용된 함수 : (T: Hashable) -> U
  2. 함수의 인자가될 타입 : T

즉 ((T) -> U, T) 타입의 인자를 받고 다시 U타입의 값을 리턴하는 클로저를 인자로 받는 것이다. 그리고 이런 클로저를 인자로 받아서 (T) -> U 타입의 함수를 리턴해야 한다. 따라서 memoize() 함수의 원형은 아래와 같이 선언할 수 있다.

func memoize <T:Hashable, U> (_ body: @escaping ((T) -> U, T) -> U) -> (T) -> U
                                                  ^^^^^^^^^^ 클로저인자  ^^^^^^^^ 메모아이즈된 리턴타입
                                                ^^^^^^^^^^^^^^^^^^^ 클로저 전체 타입

그리고 그 이후를 살펴보자.

func memoize <T:Hashable, U> 
  (_ body: @escaping ((T) -> U, T) -> U)
  -> (T) -> U
{
  var memo = [T:U]()
  var result: ((T) -> U)! // IUO 타입으로 선언하여 초기값을 설정하지 않는다. 
  result = { n in 
    if let cachedResult = memo[n] { return n }
    let r = body(result, n) // body는 원형이다. 여기에 메모아이즈된 함수, 즉 리턴 결과를 넘겨준다.
    memo[n] = r
    return r
  }
  return result
}

조금의 최적화

그런데 역시 조금의 최적화가 필요하다. 만약 어떤 값 N에 대해서 우박수 경로를 구했다고 하자. 짝수인 경우는 그 절반에 해당하는 값의 우박수 경로보다 1칸 (즉 그 절반의 값으로 한 칸 더 이동한다)이 많다. 따라서 N을 2배, 4배, 8배하여 나오는 값에 대해서 +1, +2, +3 할 수 있는 것이다. 이렇게 특정 값에 대한 경로를 구했을 때, 그 수로 접근하는 2의 거듭제곱 배에 해당하는 값은 계산하지 않고 미리 만들어 둘 수 있다. 따라서 위의 함수에서 값을 캐싱하는 부분을 조금 조작하여 다음과 같이 작성해보자.

func memoize <T:Hashable, U> 
  (_ body: @escaping ((T) -> U, T) -> U)
  -> (T) -> U
{
  var memo = [T:U]()
  var result: ((T) -> U)! 
  result = { n in 
    if let cachedResult = memo[n] { return n }
    let r = body(result, n)
    // 새로 계산된 결과를 메모하면서, 짝수상향 방향의 값도 미리 만든다.
    var (i, j) = (n, r)
    while i <= 100_0000, meme[i] == nil {
      memo[i] = j
      (i, j) = (i*2, j+1)
    }
    return r
  }
  return result
}

위 메모이제이션 함수를 이용해서 다음과 같이 계산할 수 있다.

let hail: (Int) -> Int = memoize{ memoized, n in 
  if n < 2 { return 1 }
  let m = (n % 2 == 0) ? n / 2 : n * 3 + 1
  return memoized(m) + 1
}
let ways:[(Int, Int)] = (1...100_0000).map{ ($0, hail($0)) }
let result = ways.reduce(ways[0]){ $0.1 > $1.1 ? $0 : $1 }
print(result.0)

그 외

사실 일반화한 메모이제이션 함수를 쓰지 않는다면 hail 함수 자체가 자신의 계산결과를 메모하도록 전역 사전 객체를 하나 써서 구현할 수도 있다.

var cache = [Int: Int]()
func hail(_ n: Int) -> Int {
  if n < 2 { return 1 }
  if let r = cache[n] { return r }
  let m = (n % 2 == 0) ? n / 2 : n * 3 + 1
  let r = hail(m) + 1
  var (i, j) = (n, r)
  while i <= 100_0000, cache[i] == nil {
    cache[i] = j
    (i, j) = (i*2, j+1)
  }
  return r
}

 

태그:
%d 블로거가 이것을 좋아합니다: