[ Project Euler With Python ] 1. Multiple of 3 and 5

원문 :  Multiples of 3 and 5.

---

If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6, and 9. The sum of these multiples is 23.

Find the sum of all multiples of 3 or 5 below 1000.

3 이나 5 의 배수인 10 보다 작은 자연수를 열거하면, 3, 5, 6, 9 가 나옵니다. 이것들의 합은 23 입니다.

1000 보다 작은 자연수 중에서 3 이나 5 의 배수인 수들의 합을 구하십시오.

가장 쉽게 생각해 볼 수 있는 것은 루프를 돌면서 3 이나 5 의 배수이면 더하는 겁니다. 사실 이거 말고는 별 생각이 안 나더군요.

sum = 0 for i in range( 1000 ): if ( 0 == i % 3 ) | ( 0 == i % 5 ) : sum += i print( sum )

결과는 233168 입니다. 이것을 빅오 표기법으로 하면 O( N ) 이겠죠( 빅오 표기법에 대해서 더 자세히 알고자 하신다면, [ 강의노트 25. 자료구조, 알고리즘 - 성능측정 (Big-O ) ] 를 참조하시면 좋을 것 같네요 ).

 

다른 방식으로 푸는 사람이 있는지 확인해 봤습니다.

제가 푼 방법은 "brute-force" 방식이더군요. "geometric/arithmetic approach" 로 스마트하게 푸는 사람들이 있었습니다.

[ Project Euler - Problem 1 ] 에 의하면, 3 의 배수를 더한 것과 5 의 배수를 더한 것을 합하는 방식으로 문제 해결을 하더군요. 단순하게 생각해 봐도 전체 값에 대한 루프를 도는 것 보다는 훨씬 효율적인 것을 알 수 있었습니다.

거기에 더 나아가서 수학적인 기법을 이용해서 문제를 풀고 있었습니다. 아래는 우리가 많이 봤던 정수 덧셈에 대한 식이죠( 여러 가지 방법으로 생각해 볼 수 있는데, 궁금하다면 [ 정수의 합 공식 ] 을 참조하세요 ).

 

 

이걸 좀 변형해서 K 의 배수를 더한다고 해 보죠.

 

그럼 3 의 배수의 합과 5 의 배수의 합은 다음과 같습니다.

 

 

하지만 여기에서 끝이 아닙니다. 3 의 배수와 5 의 배수에는 두개의 최소 공배수인 15 의 배수가 겹쳐서 들어 가고 있습니다. 그러므로 15 의 배수를 빼 쭤야 정상적인 결과가 나옵니다.

 

 

 

def sum_of_multiples( base_value, max_value ) : num_values = int( max_value / base_value ) return int( base_value * num_values * ( num_values + 1 ) / 2 ) solution = sum_of_multiples( 3, 999 ) + sum_of_multiples( 5, 999 ) - sum_of_multiples( 15, 999 ) print( solution )

 

어떤 숫자든간에 sum_of_multiples 는 상수시간에 문제를 해결합니다. 한 마디로 어떤 값을 넣어도 일정한 시간이 걸린다는거죠. 빅오 표기법으로 하면 O( 1 ) 입니다.

 

역시 알아야 면장이라도 한다고.... 어떻게 하느냐에 따라서 성능에 큰 영향을 줄 수 있군요. 공부를 더 열심히 해야겠습니다.

 

p.s. 형변환 없이 다음과 같이 코드를 쓸 수도 있습니다.

 

def sum_of_multiples( base_value, max_value ) : num_values = max_value // base_value return base_value * num_values * ( num_values + 1 ) // 2 solution = sum_of_multiples( 3, 999 ) + sum_of_multiples( 5, 999 ) - sum_of_multiples( 15, 999 ) print( solution )

 

파이썬에서 "//" 연산자는 소수점을 버리는 나누기 연산자더군요.