프로젝트 오일러 6번

문제를 먼저 보자.

Sum square difference

Problem 6

The sum of the squares of the first ten natural numbers is,

1² + 2² + ... + 10² = 385

The square of the sum of the first ten natural numbers is,

(1 + 2 + ... + 10)² = 55² = 3025

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is 3025 − 385 = 2640.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

처음 열 번째까지 자연수들의 제곱의 합은 385, 합의 제곱은 3025다. 이 둘의 차이는 3025 - 385 = 2640인데, 그렇다면 처음 백 번째까지의 

합의 제곱과 제곱의 합의 차이는 몇인지 찾으시오. 

 ..쉽다. 그다지 큰 수도 아닌 이상 특별한 알고리즘은 필요하지 않을 것 같다. 

생각나는대로 구현해보자면 

from time import time

start_t = time()
sums = 0
s_sum = 0
for num in range(101):
    sums += num
    s_sum += num**2

print(sums**2 - s_sum)
print(time()-start_t)

1 ~ 100 까지의 수를 sum에 더해주고, s_sum에는 수의 제곱을 더해준다. 이에 더해 최종 식은 sum**2 - s_sum 하면 답이 나온다.

걸린 시간은 0.015608549118041992초. 짧은 시간이다.

하지만 시간은 내 맘에 드는 것과는 별개의 문제다. 범위가 짧기도 하고, 이런 코드를 짜봤자 실력이 늘겠는가? Pythonic한 방법은 뭐가 있지?

우선 생각나는 건 문제에서 준 수를 이용하는 것과, 수식을 이용하는 것이다. 

제곱의 합과 합은 수식을 이용하면 for문을 돌지 않고도 구할 수 있다는 것은 중학교 수학 시간에 배운 것 같다.

그냥 수의 합은 공식으로 기억이 난다. 시그마 (k = 1 ~n) = n(n+1)/2 이다.

제곱의 합은 공식을 이용해 유도해 내는데 자세한 것은 학창시절 애용하던 수학 블로그를 참고했다.

https://mathbang.net/628

얻은 식은 n(n+1)(2n+1)/6.

그렇게 얻은 수식을 파이썬 코드에 적용해봤다.

from time import time
sums = lambda n: n*(n+1)/2
s_sum = lambda n: n*(n+1)*(2*n+1)/6
start_t = time()

print(sums(100)**2 - s_sum(100))
print(time()-start_t)

그 와중에 람다식을 사용해보고 싶어서 써봤다.

정확한 결과값을 얻었으며 0.016989946365356445초 걸렸다. 하고보니 주목할만한 시간 차이가 보이지 않는다.

하지만 100이 아닌 100000을 넣어보면 어떨까?

• for로 돌린 코드는 0.1239774227142334초

• 수식을 이용한 코드는 0.027147531509399414초.

이 정도면 만족할만 한 수치다.

쉬운 문제라 그런지 문제 푸는 속도가 아주 빨랐다. 프로젝트 오일러의 선배님들의 코드를 둘러봤다.

수식을 이용하진 않지만 충분히 Pythonic하고 빠른 코드다.

from time import time
def sum_squares(x):
    return x**2

start_t = time()
lst100=list(range(1,101))

q=list(map(sum_squares,lst100))
w=sum(q)
e=sum(lst100)
r=e**2
result=r-w

print (result)
print(time() - start_t)

list와 map함수, sum함수를 이용하여 깔끔하게 문제를 해결했다.

위 코드에 100000을 넣고 돌려 답을 구한 시간은 0.1172645092010498초. 수식이 압도적이긴 하나 배울점이 있는 코드다.

아직 이런 파이썬 스킬에 익숙하지 않기 때문이다.

재귀 함수 형태로 구현한 사람도 있었는데, 100000 이 수를 넣어보니 RecursionError: maximum recursion depth exceeded in comparison

가 뜨며 프로그램이 뻗었다. 재귀에는 속도 뿐 아니라 이런 위험성도 있다. stack 공간에 제약이 있기 때문일 것이다.