[문제 출처 : Codechef] 이번에 살펴볼 문제는 꽤나 흥미로운 문제입니다. 이번 문제에서는 Recursive 함수, Dynamic Programming, 수학적인 해까지 종합 선물세트로 다뤄볼 수 있습니다. 아마 a+b+c=n의 해의 수 구하기와 같이 좋은 예제가 될 것 같습니다. 먼저 어떤 문제인지 살펴보겠습니다.

도현이와 리진이가 게임을 하고 있습니다. 얘들은 일단 N이라는 숫자로 게임을 시작합니다. 규칙은 다음과 같습니다.

  • 리진이가 먼저 게임을 시작합니다. 그리고 교대로 진행합니다.
  • 자신의 차례에 N을 나누어 떨어지게 하는 수(N 자신은 제외)를 택하고 N에서 그 수를 빼서 N'을 만듭니다.
  • 더 이상 게임을 진행할 수 없을 때, 그 차례를 가진 사람이 지게됩니다.

    둘 다 optimally 게임을 진행한다고 가정할 때, 도현이와 리진이 중 누가 게임을 승리하게 될까요?

    • 가장 먼저 살펴볼 것이 $N=1$인 경우입니다. 이 경우 무조건 turn을 가진 사람이 지게 됩니다. 그럼 $N=2$일 때는 어떨까요? 나눌 수 있는 수는(N을 제외한) 1밖에 존재하지 않습니다. 따라서 1을 빼주고 turn을 넘깁니다. 그러면 결국 상대방이 1을 받게 되고 게임에서 지게 됩니다. $N=3$인 경우도 마찬가지로 1만 가능하기 때문에 2를 상대에게 넘겨주게 되고, 2를 가진 상대는 무조건 승리하게 되어있기 때문에 이번에는 처음 시작한 사람이 무조건 지게 됩니다. 결국,

    Winner(N=1) = 도현
    Winner(N=2) = 리진
    Winner(N=3) = 도현
    …

    이런 가지를 모든 N에 대해서 할 수는 없겠죠? 그럼 어떻게 이것을 프로그래밍 할 수 있을까요? 그것은 바로 무식한 방법인 Recursive 함수를 이용하는 방법입니다. 편의상 이름 대신에 True와 False로 turn을 나타내겠습니다.

    def whoLost(n, turn):
	# 일단 n=1이면 그 turn을 가진 사람이 진 것입니다.
    if n == 1:
        return turn

    for i in range(1, int(n**0.5)+1):
        if n % i == 0: #만약 n을 나누어 떨어지게 하는 수가 있다면,
            lost = whoLost(n-i, not turn) #누가 졌는지 n-i를 상대방에게 넘겨서 확인합니다.
            if lost != turn: #상대방이 무조건 지게되는 경우가 있다면 나는 optimally 그 방법을 택하면 됩니다.
                return not turn
            if i > 1: #i=1인 경우 몫은 n이 되므로 이 경우만 제외합니다.
                lost = whoLost(n-n/i, not turn) #위에서 상대방이 무조건 지게되는 경우가 없을 경우에 다시 n-n/i를 상대방에게 넘겨서 확인합니다.
                if lost != turn: #상대방이 무조건 지게되는 경우가 있다면 마찬가지로 optimally 그 방법을 택하면 되므로 상대방을 리턴합니다.
                    return not turn
    #만약 상대방이 지는 경우가 없다면.. 내가 지는거겠죠? ㅠ
    return turn

    여기서 사용된 팁 중의 하나가 주어진 수가 소수일까?에서 사용되었던 1에서 $N$까지 모두 나눠보는 것이 아니라 1에서 $\sqrt{N}$까지만 체크해 보는 센스가 재활용되었습니다 :)

    결과가 잘 나오는지 확인해 보겠습니다.

    >>> print whoLost(1, True)
True
>>> print whoLost(2, True)
False
>>> print whoLost(3, True)
True

    잘 동작하네요 :) 그런데 가만히 잘 생각해 보시면 어디서 익숙한 패턴이 보이지 않나요!? 짐작하셨겠지만, 결국 n과 turn이 같은 경우의 수가 꽤 많이 발생하게 된다는 점입니다! 따라서 Dynamic programming이 이 경우에도 큰 힘을 발휘할 수 있겠죠? 그럼 dynamic programming을 잘 접목시켜보겠습니다.

    def whoLost_dynamic(n, turn, cache=dict()): #중요한 것은 memory기능을 하는 cache변수죠!
    if n == 1:
        return turn

    #이 부분이 추가되는데, 이미 메모리에 가지고 있다면 더 recursive call을 하지 않고 바로 값을 찾아서 리턴합니다.
    if (n, turn) in cache:
        return cache[(n, turn)]

    #나머지 부분에서 유의할 점은 리턴하기 전에 값을 저장하고 리턴해야 한다는 점입니다.
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            lost = whoLost_dynamic(n-i, not turn, cache)
            if lost != turn:
                cache[(n, turn)] = not turn
                return not turn
            if i > 1:
                lost = whoLost_dynamic(n-n/i, not turn, cache)
                if lost != turn:
                    cache[(n, turn)] = not turn
                    return not turn
    cache[(n, turn)] = turn
    return turn

    그럼 이제 성능 비교를 해 볼까요?

    >>> from time import time
>>> t0 = time()
>>> print [whoLost(i, True) for i in range(1, 60)]
[True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True]
>>> print "걸린시간 : %.2e" % (time()-t0)
걸린시간 : 1.29e+00

>>> t0 = time()
>>> print [whoLost_dynamic(i, True) for i in range(1, 60)]
[True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True]
>>> print "걸린시간 : %.2e" % (time()-t0)
걸린시간 : 7.56e-04

    와우.. 결과가 또 1000배 이상 벌어지네요. 그렇게 많은 작업을 시킨 것도 아닌데 말이죠! ^^

    그런데 마지막으로 한가지 더 언급할 것이 있습니다. 이 게임에는 간단한 수학적 법칙이 숨어있습니다. 바로 짝수를 가진 사람이 무조건 이길 수 있다는 법칙이죠 :) 왜 그렇게 될까요?

    • 먼저 짝수를 가진 사람은 상대방에게 무조건 홀수를 줄 수 있습니다. (예를 들면 무조건 1을 빼서 주면 상대방은 홀수겠죠?)
    • 그런데 상대방이 홀수를 받게 되면 홀수는 홀수로밖에 나누어 떨어지지 않습니다.
    • 결국 상대방은 ‘홀수-홀수’를 하게 되기 때문에 상대방에게 짝수를 줄 수 밖에 없겠죠?
    • 그럼 결국 내가 2를 가지게 되기 때문에 상대가 무조건 지게 됩니다.

    이것은 함수로 딱 한줄로 표현할 수 있습니다.

    def whoLost_theoretic(n, turn):
    return turn if n%2==1 else not turn

>>> t0 = time()
>>> print [whoLost_theoretic(i, True) for i in range(1, 60)]
[True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True, False, True]
>>> print "걸린시간 : %.2e" % (time()-t0)
걸린시간 : 2.42e-04

    Dynamic programming보다 3배정도 빠르네요. 역시 수학적 이론은 이래서 중요하다는 것을 다시 한번 확인하실 수 있겠죠? :)