프로젝트 오일러 006
1부터 100까지의 '제곱의 합'과 '합의 제곱'의 차이는?
문제
6번 문제
1부터 100까지 ”제곱의 합”과 ”합의 제곱”의 차는?
초급 중의 초급 문제입니다. 첫 문제에서 소개한 list comprhension으로 간단히 표현할 수 있습니다. 두 수의 차를 구할 때에 둘 중 어느 것이 큰 지 알 수 없다면 abs() 함수를 써서 절대값을 구할 수 있습니다.
근데 사실 우리는 제곱의 합보다 합의 제곱이 훨씬 더 크다는 것을 미리 알 수도 있습니다. (그 이유는 곰곰히 생각해 봅시다.)
a1 = sum( n**2 for n in range(1, 101))
a2 = sum(range(1, 101)) ** 2
print(abs(a1 - a2))연속한 자연수의 합과 자연수의 제곱의 합
물론 교과과정에서는 이 경우의 공식도 배울 겁니다. 합의 제곱 공식을 제곱하고 두 차를 구해서 정리하면 아래와 같이 공식이 만들어집니다.
a1 = (n(n + 1) / 2)^2
a2 = n(n + 1)(2n + 1) / 6
a1 - a2 = n(n-1)(n+1)(3n+2) / 12읽기의 편의를 위해서 실제 파이썬 문법은 아닌 방식으로 씁니다.
어떻게 하더라도 공식의 속도를 이길 수는 없겠죠.
💡
사실 1~100까지로 범위가 매우 적기 때문에 범위가 매우 좁습니다. 그래서 어떻게 구현하더라도 사실 눈깜짝할 사이에 답이 나옵니다.
프로젝트 오일러가 출범할 당시에는 32비트 정수는 그 당시 컴퓨터가 한 번에 계산하고 표현할 수 있는 가장 큰 수였습니다. 그래서 숫자가 커지면 마지막 7자리만 요구한다거나 하는 문제들도 있습니다.
일부 문제들은 시간이 지남에 따라 그 범위를 늘려나가기도 합니다. (예를 들어 8번 문제는 정수 5개의 곱에서 정수 13개의 곱을 사용하는 것으로 문제가 조정되었어요)
이 문제 역시 2024년 기준으로 답이 32비트 이내의 답입니다. 하지만 범위를 1~1,000으로 잡으면 역시 32비트 범위를 넘어설 수 있어서 문제의 범위가 조정될 수 있습니다. 그렇지만 이렇게 공식으로 계산한다면 반복 횟수는 동일하게 한 번입니다.
그리고... 파이썬의 경우 자리 수에 구애받지 않는 큰 정수 연산을 기본적으로 지원합니다. 따라서 일부 문제들은 파이썬에서 '너무 쉬운' 문제인 경우도 종종 있습니다.
프로젝트 오일러가 출범할 당시에는 32비트 정수는 그 당시 컴퓨터가 한 번에 계산하고 표현할 수 있는 가장 큰 수였습니다. 그래서 숫자가 커지면 마지막 7자리만 요구한다거나 하는 문제들도 있습니다.
일부 문제들은 시간이 지남에 따라 그 범위를 늘려나가기도 합니다. (예를 들어 8번 문제는 정수 5개의 곱에서 정수 13개의 곱을 사용하는 것으로 문제가 조정되었어요)
이 문제 역시 2024년 기준으로 답이 32비트 이내의 답입니다. 하지만 범위를 1~1,000으로 잡으면 역시 32비트 범위를 넘어설 수 있어서 문제의 범위가 조정될 수 있습니다. 그렇지만 이렇게 공식으로 계산한다면 반복 횟수는 동일하게 한 번입니다.
그리고... 파이썬의 경우 자리 수에 구애받지 않는 큰 정수 연산을 기본적으로 지원합니다. 따라서 일부 문제들은 파이썬에서 '너무 쉬운' 문제인 경우도 종종 있습니다.
부록
교과과정에서 이 문제를 다루는 지는 모르겠습니다. 왜냐하면 이 계산은 연속한 자연수들의 분산을 계산하는 공식이거든요. 즉 평균을 구하고 그 편차들을 모두 제곱하여 평균을 내는 것보다 어쩌면 각 값의 합의 제곱에서 제곱의 합을 빼면 분산과 같은 값이 됩니다.
