[문제출처 : Codechef] 지난번에 리진이와 도현이가 진행했던 숫자게임을 통해서 Dynamic programming의 위력과, 더더욱 수학적 이론의 중요성에 대해서 배울 수 있었는데요, 이번에 조금은 변화된 숫자게임의 rule을 통해서 또 한번 많은 것을 동시에 비교하고 배워볼 수 있는 시간을 갖겠습니다 :)
이번에 숫자게임의 룰은 아래와 같습니다.
- Bob이 먼저 게임을 시작하고(숫자 $N$으로) 교대로 진행합니다.
- 각자의 turn에 플레이어는 $N$보다 작은 소수들 중 하나($p$)를 선택해서 $N-p$를 한 다음 턴을 넘깁니다. (여기서 1은 소수는 아니지만 그래도 포함을 해 줍니다.)
- 결국 1을 가지는 사람이 지게 됩니다.
최종적으로 누가 지게 될까요?
먼저, $N$보다 작은 소수들은 어떻게 구할 수 있을까요? 앞서 우리가 주어진 수가 소수일까?에서 살펴봤듯이, 숫자 하나씩 하나씩 소수인지 판단하면서 리스트를 얻을 수 있습니다. 하지만, 이는 매우 비효율적인 방법이 될 수 있습니다. 왜냐면 2부터 $\sqrt{N}$까지 계속 루프를 돌려야 하기 때문입니다. 반면 이런 방법은 어떨까요?
- 1부터 $N-1$까지의 숫자 리스트를 만듭니다.
- 2부터 시작하면서 자신보다 다음의 있는 수들을 loop돌면서 자신으로 나눠지면 다 지워줍니다.
- 지워지지 않은 첫 다음 수(지금은 3)는 소수가 되고, 또 그 수로 자신보다 다음 수들을 나누면서 나눠지는 것들을 지워줍니다.
이런식으로 하면 쉽고 빠르게 소수들의 list를 얻을 수 있을 것입니다.
def prime_numbers_less_than_N(N):
primeNumbers = range(1, N) #일단 1~N-1까지의 숫자 리스트를 만듭니다.
i = 1
while i < len(primeNumbers): #2부터 한 숫자씩 pick하면서
j = i+1
while j < len(primeNumbers): #자신보다 다음 수들을 loop돌면서 나눠지면 지워줍니다.
if primeNumbers[j] % primeNumbers[i] == 0:
primeNumbers.pop(j)
else:
j += 1
i += 1
return primeNumbers #최종적으로 지워지지 않은 숫자들은 소수들입니다.
>>> prime_numbers_less_than_N(15)
[1, 2, 3, 5, 7, 11, 13]소수들의 리스트를 잘 구해낼 수 있네요 :) 그러면 이를 바탕으로 recursive하게 경기 결과를 알아보는 함수를 작성해 봅시다 ;)
def whoLost_bruteforce_naive(N, turn=True):
if N == 1:
return turn
primeNumbers = prime_numbers_less_than_N(N)
for p in primeNumbers: #각 리스트의 숫자들을 1부터 시작해서 하나라도 상대방이 지게 되는 경우가 있으면 자신이 이기는 것입니다.
if whoLost_bruteforce_naive(N-p, not turn) != turn:
return not turn
return turn #그렇지 않으면 자신이 지는 것입니다.
>>> from time import time
>>> t0 = time()
>>> print whoLost_bruteforce_naive(30)
False
>>> print "걸린시간 : %.3e" % (time()-t0)
걸린시간 : 3.931e+00역시나 많이 느리죠??(complexity가 exponential 함수이기 때문에 그렇습니다.) 그럼 이제 dynamic programming의 concept를 가져와서 프로그램을 짜보겠습니다.
def whoLost_dp_naive(N, turn=True, cache=dict()):
if N == 1:
return turn
if (N, turn) in cache:
return cache[(N, turn)]
primeNumbers = prime_numbers_less_than_N(N)
for p in primeNumbers:
if whoLost_dp_naive(N-p, not turn, cache) != turn:
cache[(N, turn)] = not turn
return not turn
cache[(N, turn)] = turn
return turn
>>> t0 = time()
>>> print whoLost_dp_naive(30)
False
>>> print "걸린시간 : %.3e" % (time()-t0)
걸린시간 : 1.024e-03와우.. 역시 3000배 이상의 엄청난 시간 단축이네요!! 이는 N이 커질수록 훨씬 더 심해지겠죠?? 다시 한 번 dynamic programming의 힘을 엿볼 수 있는 기회였네요 :)
BUT!! 이것이 다가 아닙니다! 이번에는 간단한 알고리즘적인 변화가 얼마나 큰 결과로 이어지는지 확인해 보겠습니다. 제가 착안한 점은 ‘큰 소수부터 빼가면 훨씬 더 빨리 결과를 파악할 수 있을 것이다’라는 점이었습니다. 따라서 소수 list의 순서를 반대로 해서 loop를 돌렸을 때 어떤 결과가 나타나는지 확인해 보시죠.
def whoLost_bruteforce_smart(N, turn=True):
if N == 1:
return turn
primeNumbers = prime_numbers_less_than_N(N)
for p in reversed(primeNumbers): #reversed를 통해 역순으로 진행합니다.
if whoLost_bruteforce_smart(N-p, not turn) != turn:
return not turn
return turn
>>> t0 = time()
>>> print whoLost_bruteforce_smart(300)
False
>>> print "걸린시간 : %.3e" % (time()-t0)
걸린시간 : 1.479e-03띠로리! 심지어 DP보다도 빠른 속도를 자랑하네요… ^^ 그러면 마찬가지로 DP에도 역순을 적용해서 다시 한번 결과를 확인해 보겠습니다.
def whoLost_dp_smart(N, turn=True, cache=dict()):
if N == 1:
return turn
if (N, turn) in cache:
return cache[(N, turn)]
primeNumbers = prime_numbers_less_than_N(N)
for p in reversed(primeNumbers):
if whoLost_dp_smart(N-p, not turn, cache) != turn:
cache[(N, turn)] = not turn
return not turn
cache[(N, turn)] = turn
return turn
>>> t0 = time()
>>> print whoLost_dp_smart(30)
False
>>> print "걸린시간 : %.3e" % (time()-t0)
걸린시간 : 1.169e-03앞서 DP를 사용하지 않은 경우와 큰 차이가 없네요. 이렇게 간단한 알고리즘적인 변화 하나가 상상을 초월하는 속도의 증가로 나타납니다! 따라서 이런 사고를 자주 연습해 볼 수 있으면 참 좋겠죠?
그러면 마지막으로 수학적 이론으로 어떻게 이 문제를 푸는지 확인해 봅시다. 착안점은, [1,2,3]이 모두 뺄 수 있는 수이기 때문에, 숫자 $N$을 4로 나누었을 때 나머지가 0, 1, 2, 3인 경우의 네가지 케이스로 나눠볼 수 있습니다. 만약 자신이 N%4 != 1인 수를 가지고 있다면, N%4 == 0일 때는 -3을, N%4 == 2인 경우 -1을, N%4 == 3인 경우 -2를 해서 상대방이 N%4 == 1인 수를 갖도록 만들 수 있습니다. 결국 N%4 == 1을 가지는 사람이 지는 것이 되겠죠.
def whoLost_theoretical(N, turn=True):
return turn if N%4==1 else not turn
>>> t0 = time()
>>> print whoLost_theoretical(300)
False
>>> print "걸린시간 : %.3e" % (time()-t0)
걸린시간 : 1.252e-04수학적 이론이 역시 더 빠르네요. 수학이 얼마나 중요한지 다시 한 번 느낄 수 있었습니다 :) 하지만 그래도 DP의 힘도 여전히 대단하구요, 특히나 알고리즘이 정말 중요하다는 생각이 많이 들었던 예제였습니다 :)