[문제출처 : Codechef] 이번에 살펴볼 문제는 굉장히 심플한 문제입니다. 하지만 지금 이 문제를 봤을 때는 간단해서 쉽게 넘어가지만, 실제로 조금만 복잡한 코딩을 해도 이런 간단한 원리를 잊은 채 비효율적으로 코딩하는 저의 모습을 보게 됩니다. 어찌됐건 기초를 다잡는 마음에서 한번 풀어봅시다 :)

한 학교의 선생님께서 학생들을 위해 N개의 사탕을 가지고 있습니다. 선생님께서 다음의 방식으로 사탕을 나눠준다고 합니다:
K명의 학생들에게 1개씩 나눠줍니다. 만약 남은 사탕 수가 K개가 안되면 그만 두고 선생님께서 나머지 사탕을 가지시고, 그렇지 않으면 계속 1개씩 나눠줍니다.
그럼 각 학생과 선생님께서 가지시게 될 사탕의 수는 어떻게 될까요?

먼저 문제를 있는 그대로 코드로 작성하는 경우입니다.(비효율적이겠죠?)

def splitCandies_complex(n, k):
	if k==0: #반드시 division by 0의 케이스를 고려해야합니다!!
        return k, n
    eachStudent = 0
    while n >= k: #사탕이 k개 이상 남아있으면 계속해서
        n -= k #각 학생들에게 1개씩 나눠주고,
        eachStudent += 1
    teacher = n #나머지는 선생님이 갖습니다.
    return eachStudent, teacher

>>> print splitCandies_complex(10, 2)
(5, 0)
>>> print splitCandies_complex(100, 3)
(33, 1)

결과는 잘 출력함을 확인할 수 있습니다 :) 이제 다들 아시겠지만, 효율적인 코드를 짜 봅시다.

def splitCandies_simple(n, k):
    if k==0:
        return k, n
    eachStudent = n/k #단순히 각 학생들은 몫만큼의 사탕을 갖고
    teacher = n%k #선생님은 나머지를 갖습니다.
    return eachStudent, teacher

>>> print splitCandies_simple(10, 2)
(5, 0)
>>> print splitCandies_simple(100, 3)
(33, 1)

그럼 도대체 얼마나 효율적이길래 이런 것들을 고려해야 할까요?

>>> from time import time
>>> t0 = time()
>>> print splitCandies_complex(10000000, 10)
(1000000, 0)
>>> print "걸린시간 : %.2e" % (time()-t0)
걸린시간 : 1.39e-01
>>> t0 = time()
>>> print splitCandies_simple(10000000, 10)
(1000000, 0)
>>> print "걸린시간 : %.2e" % (time()-t0)
걸린시간 : 9.99e-05

와, 1000배 가까이 차이가 나네요 ;) 간단하지만 N이 커짐에 따라서 급격하게 비효율적이 되겠죠?