그냥 그런 블로그

원문 : Highly divisible triangular number

삼각수

일단 삼각수라는 것이 무엇인지 찾아 봤습니다. 위키백과에 따르면 삼각수란 다음과 같습니다[ 1 ].

삼각수(三角數, triangular number), 또는 "삼각형 수" 는 일정한 물건으로 삼각형 모양을 만들어 늘어 놓았을 때, 그 삼각형을 만들기 위해 사용된 물건의 총 수가 되는 수를 말한다.

예를 들어 아래와 같이 네 줄에 걸쳐 삼각형을 만들었을 때 늘어 놓은 물건의 총 수는 10 개가 되며, 10 은 삼각수의 하나가 된다.

n 번째 삼각수 N 은 1 부터 n 까지의 자연수를 모두 합한 것이고, 여기서 삼각수의 정의로 인하여 n 은 반드시 자연수여야 한다. 삼각수의 수열은 1, 3, 6, 10, 15, 21, 28, 36, 45, 55, 66, 78, 91, 105, 230... 과 같고 n 번째의 삼각수 N 은 N = n( n + 1 ) / 2 로 나타낼 수 있다. 모든 자연수는 최대 3 개의 삼각수의 합으로 표현할 수 있다는 정리가 있으며, 이는 카를 프리드리히 가우스가 1796 년( 가우스의 일기에 따르면 7월 10일 )에 증명하였다. 이 정리는 모든 자연수는 최대 n 개의 n 각수의 합으로 표현할 수 있다는 페르마의 다각수정리의 한 경우이다.

Solution

일단 먼저 n 번째 삼각수를 찾아야 합니다. 위키백과를 보지 않았다면 어쩔 수 없이 무식하게 삼각수를 더하면서 찾았겠죠. 

이 문제는 일단 해결이 되었습니다. n 번째 삼각수를 n( n + 1 ) / 2 로 나눌 수 있다고 했기 때문에 n 을 증가시켜가면서 삼각수를 찾는 것이 가능합니다. 그래도 진짜 식이 맞는 건지 확인을 해 보도록 하겠습니다. 

일단 위의 그림에서 삼각형의 1, 3, 6, 10 은 삼각수를 구성합니다. 패턴을 보니 숫자의 개수가 1, 2, 3, 4 이런 식으로 증가하는군요. 결국 삼각형의 행을 구성하는 마지막 숫자는 이것은 1 부터 n 까지의 자연수의 합을 구하는 문제와 같습니다. 1 = 1, 3 = 1 + 2, 6 = 1 + 2 + 3, 10 = 1 + 2 + 3 + 4, N = n( n + 1 ) / 2 입니다.

다음 문제는 이것의 인수를 찾는 건데요, 안타깝게도 문제에 있는 28 의 경우를 보면 소인수가 아니라 그냥 인수입니다. 일단 소인수를 다 구한다음에 그것을 곱해가면서 5 개의 인수로 만들어낼 수 있는지 찾아야 합니다.

저는 여기에서 하나의 규칙을 찾았습니다.

N = a * b 라 했을 때, a 는 [ 1, N / 2 ) 범위의 자연수입니다. 왜냐하면 a 가 1 일 때 b 가 N 이니까, a 가 2 일 때 가장 큰 b 가 나오기 때문이죠.

그리고 a 와 b 는 가능한 몫들을 나열했을 때 아래 그림처럼 대칭을 이루며 몫의 개수가 짝수가 됩니다.

하지만 28 의 경우를 보면 a 의 범위가 [ 1, 14 ) 가 되는데 그 범위에 7 이 들어 있습니다. 이렇게 되면 대칭이 안 되기 때문에 b 가 이미 a 로 선정이 된 경우에는 배제해야 합니다. 이를 자연스럽게 배제할 수 있는 방법을 생각해 봤습니다.

인수의 관점에서 생각해 봤습니다. b <= N / a 입니다. 그리고 a <= N / b 입니다. 여기에서 a == b 일 때가 a 의 최대값입니다. 그렇다면 N = a² or b² 이므로, a 는 다음과 같은 범위를 가진다고 할 수 있습니다: [ 1, root( N ) ]. 매우 간단한 사실인데 이상한 고민을 했군요.

마지막으로 몫의 개수에도 예외가 있습니다. N 이 제곱수일 경우입니다. 이 경우에는 몫이 홀수개가 나옵니다. 왜냐하면 제곱이니 a 와 b 가 동일하기 때문이죠. 위에서 1 의 몫도 홀수이고 36 의 몫도 홀수입니다. 그러니 N 이 제곱수라면 계산할 필요도 없겠죠. 문제에서 500 개의 몫을 가진다고 했기 때문에 몫의 개수가 짝수입니다. 그러므로 N 이 제곱수일 경우를 배제해야 합니다.

import math i = 0 while( True ) : tn = int( i * ( i + 1 ) / 2 ) # make triangulr number i += 1 # increase number for next loop root = math.sqrt( tn ) # get square-root nroot = int( root ) # get natural number of square-root if root == nroot : # if root is natural number continue # goto next number if( nroot < 250 ) : # if root is less than 250 continue # goto next number count = 0 # reset factor count for factor in range( 1, nroot + 1 ) : # for each number if 0 == ( tn % factor ) : # check if remainder is 0 count += 2 # add 2 factors if 500 == count : # if number of fa-ctors is 500 print( tn ) # print it break # break while

하지만 10 분이 지나도록 답이 없었습니다. 이렇게 해결하는 것은 좋은 답이 아닐 것 같다는 생각이 들더군요. 좀 더 규칙을 찾아 보기로 했습니다.

n 번째 삼각수가 n( n * 1 ) / 2 라고 하지만, 이것을 잘 살펴 보면 결국 n 번째 삼각수는 기존의 n 번째 삼각수에서 n 개 만큼 더한 것이라는 것을 알 수 있습니다.

그렇다면 다음과 같이 구현할 수 있습니다.

prev_tn = 0 i = 1 while( True ) : tn = prev_tn + i # make triangulr number prev_tn = tn # set previous triangular number i += 1 # increase number for next loop root = math.sqrt( tn ) # get square-root [ ... ] [ ... ]

그런데 아무래도 몫의 종류가 500 개라는 것을 최적화할 수 있는 방법이 떠 오르지 않더군요.

결국 다른 사람의 구현( Jason's code blog )을 찾아 봤습니다.

n 과 n + 1 의 소인수 분해를 알고 있다고 하면 그것을 다음과 같이 작성할 수 있습니다.

n 과 n + 1 은 어떤 소인수도 공유할 수 없다는 것에 주목하십시오( 왜냐하면 그것들은 연속적인 숫자이기 때문입니다 ). 그리고 우리는 pi 와 qi 가 구별되는 소수임을 알고 있습니다. 또한 n 이나 n + 1 은 둘 중에 하나만 2 로 나눠집니다. 그러므로 지수 ei 와 fi 만이 T( n ) 을 나누는 숫자를 결정하기 위해서 고려할 필요가 있는 것들입니다. T( n ) = ( n( n + 1 ) )/2 는 n 이나 n + 1 의 인수분해에서 두 숫자의 제곱을 배제할 필요가 있다는 것을 의미합니다( 둘중의 하나만의 짝수라는 것을 기억하세요 ). 일관성을 지키기 위해서 n 이 짝수이고 p = 2 라고 가정해 봅시다. 그러면 T( n ) 의 전체 인수의 개수는 다음과 같은 조합으로 표현될 것입니다:

더 개선하자면, 삼각수를 증가시킬 때, 이전의 n 은 이미 계산했기 땜누에 n + 1 만 계산해도 됩니다. 이는 실시간 비용을 조금이라도 줄여줄 것입니다.

그래서 다음과 같이 하더군요.

import time def num_divisors(n): if n % 2 == 0: n = n/2 divisors = 1 count = 0 while n % 2 == 0: count += 1 n = n/2 divisors = divisors * (count + 1) p = 3 while n != 1: count = 0 while n % p == 0: count += 1 n = n/p divisors = divisors * (count + 1) p += 2 return divisors def find_triangular_index(factor_limit): n = 1 lnum, rnum = num_divisors(n), num_divisors(n+1) while lnum * rnum < 500: n += 1 lnum, rnum = rnum, num_divisors(n+1) return n start = time.time() index = find_triangular_index(500) triangle = (index * (index + 1)) / 2 elapsed = (time.time() - start) print "result %s returned in %s seconds." % (triangle,elapsed)

결과는 76576500 입니다.

참고자료

[ 1 ] 삼각수. 위키백과.

원문 : Largest product in a grid.

Brute-Force

이 문제를 가시화하면 다음과 같습니다. ( i, j ) 요소를 중심으로 살펴 보시다. 그러면 아래 그림에서 검은색을 중심으로 색칠해져 있는 부분들의 곱을 구해서 가장 큰 숫자들을 찾으면 됩니다.

그런데 딱 봐도 루프를 돌 때 중복되는 부분이 많을 것 같다는 생각이 듭니다. 특정 방향은 다른 좌표를 중심으로 하는 셸을 계산할 때 서로 겹치므로 배제될 수 있습니다( 예를 들어 왼쪽과 오른쪽, 위쪽과 아래쪽, 위쪽 대각선과 아래쪽 대각선 ).

이 정도로 최적화라고 부르긴 좀 뭐해서 여기까지 Brute-Force 라 생각하도록 하겠습니다.

str_num = ( "08 02 22 97 38 15 00 40 00 75 04 05 07 78 52 12 50 77 91 08 " "49 49 99 40 17 81 18 57 60 87 17 40 98 43 69 48 04 56 62 00 " "81 49 31 73 55 79 14 29 93 71 40 67 53 88 30 03 49 13 36 65 " "52 70 95 23 04 60 11 42 69 24 68 56 01 32 56 71 37 02 36 91 " "22 31 16 71 51 67 63 89 41 92 36 54 22 40 40 28 66 33 13 80 " "24 47 32 60 99 03 45 02 44 75 33 53 78 36 84 20 35 17 12 50 " "32 98 81 28 64 23 67 10 26 38 40 67 59 54 70 66 18 38 64 70 " "67 26 20 68 02 62 12 20 95 63 94 39 63 08 40 91 66 49 94 21 " "24 55 58 05 66 73 99 26 97 17 78 78 96 83 14 88 34 89 63 72 " "21 36 23 09 75 00 76 44 20 45 35 14 00 61 33 97 34 31 33 95 " "78 17 53 28 22 75 31 67 15 94 03 80 04 62 16 14 09 53 56 92 " "16 39 05 42 96 35 31 47 55 58 88 24 00 17 54 24 36 29 85 57 " "86 56 00 48 35 71 89 07 05 44 44 37 44 60 21 58 51 54 17 58 " "19 80 81 68 05 94 47 69 28 73 92 13 86 52 17 77 04 89 55 40 " "04 52 08 83 97 35 99 16 07 97 57 32 16 26 26 79 33 27 98 66 " "88 36 68 87 57 62 20 72 03 46 33 67 46 55 12 32 63 93 53 69 " "04 42 16 73 38 25 39 11 24 94 72 18 08 46 29 32 40 62 76 36 " "20 69 36 41 72 30 23 88 34 62 99 69 82 67 59 85 74 04 36 16 " "20 73 35 29 78 31 90 01 74 31 49 71 48 86 81 16 23 57 05 54 " "01 70 54 71 83 51 54 69 16 92 33 48 61 43 52 01 89 19 67 48" ) strs = str_num.split() count = 0 arr = [] for str in strs : arr.append( int( str ) ) def max_value( left, right ) : return left if ( left > right ) else right product = 0 for j in range( 20 ) : for i in range( 20 ) : index = j * 20 + i if i > 2 and j < 17 : current_product = arr[ index ] * arr[ index + 19 ] * arr[ index + 38 ] * arr[ index + 57 ] product = max_value( product, current_product ) if i < 17 : current_product = arr[ index ] * arr[ index + 1 ] * arr[ index + 2 ] * arr[ index + 3 ] product = max_value( product, current_product ) if j < 17 : current_product = arr[ index ] * arr[ index + 20 ] * arr[ index + 40 ] * arr[ index + 60 ] product = max_value( product, current_product ) if i < 17 and j < 17 : current_product = arr[ index ] * arr[ index + 21 ] * arr[ index + 42 ] * arr[ index + 63 ] product = max_value( product, current_product ) print( product )

답은 70600674 입니다.

Other's solution

다른 사람들의 구현을 살펴 봤는데, 루프를 도는 방식에 조금 차이가 있을 뿐이고 크게 다르지는 않더군요.

그런데 파이썬에서 동적으로 자료구조를 만드는 편리한( 코드가 짧은 ) 방법들이 있는데, 꽤 어렵네요. [ JASON'S CODE BLOG ] 에서는 다음과 같이 2 차 배열을 만듭니다.

M = [i.split() for i in L] M = [[int(j) for j in i] for i in M]

파이썬은 문법이 뭔가 살짝 괴랄하지만 익숙해지면 편하게 쓸 수 있을 것 같아 보이네요.

원문 : Summation of primes

계속해서 나오는 소수 문제네요. [ 3. Largest prime factor ] 에서는 가장 큰 소인수를, [ 7. 10001 st pime ] 에서는 n 번째 소수를, 이 번에는 일정 이하의 소수의 합을 구하는 겁니다.

Brute-Force

def sum_primes_until( max ) : primes = list() primes.append( 2 ) primes.append( 3 ) primes.append( 5 ) i = 7 # second prime number, and odd number. sum = 2 + 3 + 5 while( i < max ) : is_prime = True for p in primes : # for each prime number if 0 == ( i % p ) : # i is evenly divided by prime number is_prime = False # i is not prime number break if is_prime : primes.append( i ) sum += i i += 2 # select next odd number if 0 == ( i % 5 ) : # if next odd number is multiple of 5 i + 2 # select next odd number return sum print( sum_primes_until( 2000000 ) )

일단 답은 142913828922 입니다.

나름대로 최적화를 한다고 했지만 O( mn ) 의 시간 복잡도를 가집니다. m 과 n 의 크기가 크므로 비용이 장난이 아닙니다. 한 10 분은 걸린 것 같군요.

소수와 관련해서 점점 더 극악한 조건을 제시하면서 결국에는 최적화를 더 하게 만드는군요.

Others Optimization

[ 7. 10001 st pime ] 의 공식 [ PDF ] 에서 최적화를 위해 사용한 전제들은 다음과 같습니다.

• 1 은 소수가 아님.
• 2 를 제외한 모든 소수는 홀수임.
• 3 보다 큰 모든 소수는 6k+/-1 로 작성될 수 있음.
• 어떤 수 n 은 루트 n 보다 큰 소수를 하나만 가지고 있을 수 있음.
• 어떤 수 n 에 대한 소수 테스트를 하기 위한 수열은 : n 을 나누는 루트 n 보다 작거나 같은 숫자 f 를 발견하지 못한다면, n 은 소수임 : n 의 유일한 소인수는 n 자체임.

뭔가 최적화의 여지가 상당히 많군요.

import math def isprime( n ) : if 1 == n : # 1 is not prime. return False elif n < 4 : return True # 2, 3 elif 0 == ( n % 2 ) : return False # even is not prime. elif n < 9 : return True # even is excluded, reamins 5, 7, 9. elif 0 == ( n % 3 ) : return False # multiple of 3 is excluded else : r = math.floor( math.sqrt( n ) ) f = 5 while f <= r : # check if n is divided by other prime( form of 6k+/-1 ) if 0 == ( n % f ) : return False if 0 == ( n % ( f + 2 ) ) : return False f += 6 return True sum = 2 for n in range( 3, 2000001, 2 ) : if isprime( n ) : sum += n print( sum )

실행해 보니 정상적인 결과가 나왔고, 무진장 빠르군요. 이것도 사실 O( mn ) 의 비용이 듭니다만, Brute-Force 방식보다는 m 과 n 의 크기가  작으므로 매우 빠릅니다. 거의 20 초 정도면 끝나는군요.

원문 : Special Pythagorean triplet

Brute-Force

일단 연립방정식으로 풀 수 있는지 확인을 해 봤습니다만, 방정식이 하나가 부족해서 풀수가 없네요. 어떻게든 하나의 변수값은 알아야 나머지를 풀 수 있는 형태입니다.

결국 삼중 루프를 도는 수밖에 없습니다. 

다음을 만족하는 값들을 찾아야 합니다. 그런데 a 와 b 를 알면 c 를 구할 수 있으므로, 이중 루프만 돌아도 됩니다.

def find_pythagorean_product( sum ) : for b in range( 1, sum ) : b_2 = b * b for a in range( 1, b ) : # a < b a_2 = a * a c = sum - a - b # a + b + c = sum if ( b < c ) and ( ( c * c ) == ( a_2 + b_2 ) ) : # b < c, a^2 + b^2 = c^2 print( "a = {0}, b = {1}, c = {2}".format( a, b, c ) ) return a * b * c print( find_pythagorean_product( 1000 ) )

답은 31875000 입니다.

Others Solution

Math Blog 의 [ A 1000 Pythagorean triplets – Problem 9 ] 에 수학적인 접근이 있더군요. 궁금하면 확인해 보시기 바랍니다.

원문 : Largest product in a series

일단 간단하게 생각하면 그냥 루프를 돌면서 15 개씩 묶어서 곱해보는 것이 가장 단순합니다. 먼저 하나의 1000 자리 숫자를 여러 개의 1 자리 숫자로 나누는 작업이 필요하겠죠.

그런데 이 작업을 하려면 1000 자리가 들어 갈 수 있는 자료형이 필요합니다. 컴퓨터는 데이터를 이진수로 저장하기 때문에, 이를 표현하기 위해서는 얼마나 큰 비트가 필요할까요?

계산을 해 보도록 하겠습니다.

이진수로 자리수를 올리는 것은 한 비트씩 옮기는 겁니다. 아래 첨자가 2 라고 되어 있으면 이진수를 그렇지 않으면 십진수를 의미합니다.

그렇다면 십진수는 어떨까요( 아래에서 왼쪽 항을 볼 때 주의할 점은 십진수 표현이라는 것입니다. 줄을 맞추려고 앞에 0 을 넣었습니다. 아래 첨자가 없다는 점에 주의하세요 ).

그럼 10 의 멱승을 이진수로 표현해 보죠.

뭔가 규칙이 있을까요? 십진수가 1 자리 올라갈 때마다, 이진수는 3 자리나 4 자리가 올라가는 것을 알 수 있습니다. 이렇게 볼 때 십진수로 표현했을 때 1000 자리가 되려면 이진수로 고쳤을 때 최대 4000 자리( 즉 4000 비트 )가 필요함을 알 수 있습니다.

즉 1000 자리 숫자는 현재의 이진수 컴퓨팅 환경에서 표현하는 것이 불가능한 숫자입니다.

Brute-Force

그래서 이를 그냥 문자열로 표현하기로 했습니다. 그리고 계산할 때마다 형변환하는 것을 피하기 위해서 미리 형변환해서 리스트에 넣었습니다. 계산 방식 자체는 단순합니다. 그냥 처음부터 13 개씩 계산하면 됩니다.

str_num = ( "73167176531330624919225119674426574742355349194934" "96983520312774506326239578318016984801869478851843" "85861560789112949495459501737958331952853208805511" "12540698747158523863050715693290963295227443043557" "66896648950445244523161731856403098711121722383113" "62229893423380308135336276614282806444486645238749" "30358907296290491560440772390713810515859307960866" "70172427121883998797908792274921901699720888093776" "65727333001053367881220235421809751254540594752243" "52584907711670556013604839586446706324415722155397" "53697817977846174064955149290862569321978468622482" "83972241375657056057490261407972968652414535100474" "82166370484403199890008895243450658541227588666881" "16427171479924442928230863465674813919123162824586" "17866458359124566529476545682848912883142607690042" "24219022671055626321111109370544217506941658960408" "07198403850962455444362981230987879927244284909188" "84580156166097919133875499200524063689912560717606" "05886116467109405077541002256983155200055935729725" "71636269561882670428252483600823257530420752963450" ) nums = list() for c in str_num : nums.append( int( c ) ) max_product = 0 offset = 0 num_adjacency = 13 max_offset = len( nums ) - num_adjacency - 1 while( offset < max_offset ) : product = 1 for i in range( offset, offset + num_adjacency ) : product *= nums[ i ] max_product = max( max_product, product ) offset += 1 print( max_product )

답은 23514624000 입니다.

Optimization

하지만 다른 문제들처럼 뭔가 다른 빠른 방법이 있을 것이라는 강박관념이 들더군요.

MathBlog 의 [ Solution to Problem 8 of Project Euler ] 의 댓글을 보니, 마지막 곱들을 저장해 놓는 것에 대한 이야기가 있었습니다. 

그렇다면 이전의 곱셈 결과에서 이전의 시작값을 나누고 다음에 올 값을 곱한다면, 문제가 해결될 수 있겠다는 생각이 들더군요. 그런데 실제 해 보니 안 됐습니다. 중간에 0 이 있으면 모든 값이 무산된다는 것을 고려하지 않은거죠. 만약 0 인 숫자가 하나도 없다면 가능할 것 같네요.

Other's Solution

[ Project Euler 8: Find the largest product of 13 consecutive digits ] 에서는 파이썬의 언어특성을 잘 이용해서 매우 짧은 코드를 작성하고 있습니다.

#Project Euler Problem 8 from operator import mul d = map(int, ''.join(line.rstrip() for line in open('pe8.txt'))) L = 13 print 'Greatest product of', L, 'consecutive \ndigits =', print "None." if L>len(d) else \ max(reduce(mul, d[i:i+L]) for i in xrange(len(d)-L+1))

솔직히 파이썬 자료구조와 알고리즘에 대한 공부를 많이 안해서 이해하기가 힘드네요.

원문 : Smallest multiple

일단 특정 범위의 숫자로 나눴을 때 나머지가 없다는 이야기는 그 숫자들이 곱해져있다는 의미일 겁니다.

예를 들어 1 부터 10 까지의 숫자로 곱해진 숫자라면 어떤 수로 나눠도 나머지가 없는 수가 나오겠죠.

그런데 여기에서 우리는 규칙을 하나 알 수 있습니다. 합성수는 소수의 곱으로 되어 있기 때문에, 소수가 중복된다는 겁니다. 

예를 들어 10 은 2 * 5 로 구성되었기 때문에 2 와 5 가 중복됩니다. 그러면 2 와 5 를 한 번씩 빼도 2, 5, 10 으로 나누어 떨어질 수 있죠.

소인수 분해를 해 보도록 하겠습니다. 1 은 소수가 아니고 곱셈에 영향을 주지 않으므로 배제합니다.

여기에서 우리는 일련의 규칙을 발견할 수 있습니다. 소인수 분해를 했을 때 합성수를 만들기 위해서 필요한 최대 소수의 개수를 알 수 있다는 것입니다.

예를 들자면 4 로 나누기 위해서는 적어도 2 가 2 개가 존재해야 합니다. 6 으로 나누기 위해서는 적어도 2 가 1 개, 3 이 1 개가 존재해야 합니다. 8 로 나누기 위해서는 적어도 2 가 3 개가 존재해야 합니다. 9 로 나누기 위해서는 적어도 3 이 2 개는 존재해야 합니다. 10 으로 나누기 위해서는 적어도 2 가 1 개, 5 가 1 개가 존재해야 합니다. 그 이외의 소수들( 여기에서는 7 )은 1 개씩만 존재하면 되죠.

정리하면 2 가 3 개, 3 이 2 개, 5 가 1 개, 7 이 1 개가 필요합니다.

위의 문제와 동일한 답이 나오는군요.

Brute-Force

이제 알고리즘을 세워 보도록 하겠습니다.

• 2 부터 20 까지의 모든 수를 돌면서 소인수 분해를 합니다.
• 소인수 분해를 했을 때, 각 소인수의 개수를 세서, 소수의 최대 횟수를 구합니다.
• 소수의 최대 횟수만큼 곱합니다.

일단 소인수들을 구하는 함수는 [ 3. Largest prime factor ] 에서 가지고 왓습니다.

def get_prime_factors( target ) : quotient = target prime_factors = list() append_factors = prime_factors.append i = 2 while( 1 != quotient ) : remainder = quotient % i if 0 == remainder : quotient /= i append_factors( i ) else : i += 1 if 0 == ( i % 2 ) else 2 return prime_factors

이제 각 factor 의 카운트를 세서 곱하는 구현을 합니다.

total_max_count = dict() for i in range( 2, 21 ) : max_count = dict() prime_factors = get_prime_factors( i ) for p in prime_factors : if p in max_count : max_count[ p ] += 1 else : max_count[ p ] = 1 max_count_keys = max_count.keys() for key in max_count_keys : if key in total_max_count : total_max_count[ key ] = max( total_max_count[ key ], max_count[ key ] ) else : total_max_count[ key ] = max_count[ key ] smallest_number = 1 total_max_count_keys = total_max_count.keys() for key in total_max_count_keys : for c in range( total_max_count[ key ] ) : smallest_number *= key print( smallest_number )

조금 코드가 길지만 첫 번째 최상위 루프를 통해서 소인수들을 얻어서 최대 카운트를 셉니다. 그리고 두 번째 루프에서는 최대 카운트만큼 소인수들을 곱해줍니다.

결과는 232792560 입니다.

Other's solution

다른 해법이 있는지 찾아 봤습니다. 공식 PDF 에서는 뭔가 엄청 단순한 형태로 푸는군요. 뭔 sqrt 와 log 가 나오고 난리입니다. 기본적으로 반복횟수를 이용해서 푸는 것은 동일한데, 위의 식을 다음과 같이 표현하는데서 알고리즘을 시작합니다.

i 번째 소수를 pi 라고 하고 지수를 ai 라 할 때 N 은 다음과 같습니다.

여기에서 pi^ai 을 k 라고 하면, ai 는 다음과 같습니다.

예를 들어, k = 20 이라고 하면, 첫 번째 소수인 p1 = 2 입니다. 그러면 다음과 같이 a1 을 구할 수 있습니다.

정수여야 하므로 floor 를 사용합니다. 최적화를 위해서 pi <= sqrt( k ) 인 경우의 ai 만을 계산한다고 합니다.

이것을 일반화해서 다음과 같이 계산한다고 합니다.

자세한 건 pdf 에서 확인해 보시기 바랍니다.

원문 : Largest palindrome product

Brute-Force

일단 제가 생각한 알고리즘은 다음과 같습니다.

• 세 자리 수의 곱으로 표현할 수 있는 수들을 검색합니다.
• 그 중에서 대칭수를 찾습니다.
• 가장 큰 대칭수로부터 내림차순으로 소인수분해를 해서 세 자리 수의 곱으로 표현된다면 그것이 가장 큰 대칭수입니다.

세 자리 수 중에서 가장 큰 것은 999 이고 가장 작은 것은 100 입니다. 그러므로 대상이 될 수 있는 수의 범위는 [ 100 * 100, 999 * 999 ] 입니다; [ 10,000, 998,001 ].

일단 가장 먼저 할 일은 어떤 숫자를 자리수로 쪼개는 함수를 만드는 거겠죠. 만드는 김에 두 번째 인자로 진법( numeral_system )을 넣도록 해 봤습니다.

def split_value( value, numeral_system ) : values = list() quotient = value while( 0 != quotient ) : remainder = quotient % numeral_system values.append( int( remainder ) ) quotient = quotient // numeral_system values.reverse() return values

15 부터 25 까지 십진법과 이진법으로 출력해 보면 결과는 다음과 같습니다.

이제 해당 숫자가 대칭수인지 확인하는 함수가 필요하겠죠. 어떤 숫자가 있을 때 중심이 되는 인덱스를 구하고 하나는 오름차순으로 하나는 내림차순으로 인덱싱하면서 값을 비교합니다. 만약 홀수개로 구성된 숫자가 있다면, 중간값은 항상 한 개이므로 비교할 필요가 없겠죠.

def is_palindrome_number( value ) : values = split_value( value, 10 ) num_values = len( values ) count = num_values // 2 for i in range( count ) : a = values [ i ] b = values [ num_values - 1 - i ] if a != b : return False return True

이제 루프를 돌면서 대칭수를 전부 출력해 보겠습니다. 

for i in range( 10000, 998002 ) : if( is_palindrome_number( i ) ) : print( i )

엄청나게 많군요... 그래서 여기에 올리지는 않았습니다. 어쨌든 가장 큰 대칭수는 997799 입니다. 물론! 이것이 답은 아닙니다. 왜냐하면 세 자리 수의 곱으로 표현될 수 있어야 하기 때문입니다.

성능을 고려하면 이것을 큰 수부터 내림차순으로 해야 합니다. 파이썬의 for 는 이런 부분에서 참 불편하군요. 범위가 헷갈립니다.

for i in range( 998001, 9999, -1 ) :

자 이제 [ 3. Largest prime factor ] 에서 만들었던 소인수분해해서 소인수 리스트를 반환하는 함수를 가지고 와서 사용할 겁니다.

def get_prime_factors( target ) : quotient = target prime_factors = list() append_factors = prime_factors.append i = 2 while( 1 != quotient ) : remainder = quotient % i if 0 == remainder : quotient /= i append_factors( i ) else : i += 1 if 0 == ( i % 2 ) else 2 return prime_factors

리스트로 받은 소인수들을 곱해가지고 두 개의 세 자리 수를 만들어야 합니다. 여기가 가장 어려운데요...

• 일단 세 자리수가 나오는 경우의 수를 모두 찾습니다. 앞에서부터 곱해도 되고 뒤에서부터 곱해도 되겠죠. 아마도 뒤에서부터 곱하는 것이 빠를 겁니다. 왜냐하면 리스트의 뒤쪽으로 갈 수록 큰 소인수이기 때문입니다.
• 하나의 세 자리 수가 나오면 나머지 소인수들을 모두 곱했을 때, 그 결과가 세 자리 수가 아니면 실패입니다.

저는 뒤에서부터 숫자를 곱해 봤습니다.

def can_make_3_digit_product( val, factors ) : temp = factors.copy() factor_1 = 1 factor_2 = 1 while( 0 < len( temp ) ) : factor_1 *= temp.pop() if 99 < factor_1 < 1000 : break while( 0 < len( temp ) ) : factor_2 *= temp.pop() if ( 99 < factor_1 < 1000 ) and ( 99 < factor_2 < 1000 ) : print( "%d = %d * %d" % ( val, factor_1, factor_2 ) ) return True return False

물론 이렇게 하는 건 잘못된 결과를 산출합니다. 왜냐하면 다음과 같은 경우를 생각해 보죠.

2 * 79 = 158 이고 3 * 83 = 249 로 해야지 세 자리 수의 곱이 나옵니다. 결국 모든 경우의 수를 찾지 않으면 정확한 결과를 구할 수가 없습니다. 결국 세 자리를 만들수 있는 경우의 수를 모두 구해야 합니다.

친구( 햄짱 )에게 이걸 해결할 쌈박한 아이디어가 있는지 물어 봤습니다. 그런데 "경우의 수를 모두 구하는 건 너무 복잡하니 세 자리 수를 모두 곱해서 대칭수가 나오는 것을 찾는 게 낫지 않겠냐"는 대답을 들었습니다. 

생각해 보니, 문제가 "특정 수를 대칭으로 만드는 세 자리 수의 곱을 찾아라" 가 아니기 때문에, 그렇게 하는 게 낫겠다는 생각이 들었습니다.

result = 0 for i in range( 999, 99, -1 ) : for j in range( 999, 99, -1 ) : number = i * j if is_palindrome_number( number ) : result = max( number, result ) print( result )

답은 906609 입니다.

Optimization

그런데 제가 만든 식은 성능에 문제가 있습니다. 왜냐하면 코드를 보면 알 수 있겠지만, 중간에 break 를 하지 않습니다. 그 이유는 이중 루프를 사용했을 때 먼저 나오는 수가 가장 큰 수라고 보장할 수 없기 때문입니다.

예를 들면, 가장 먼저 나오는 수는 995 * 583 = 580085 입니다. 이것은 993 * 913 = 906609 보다 작습니다. 그래서 루프를 다 돌 수 밖에 없는데요, 이를 최적화할 수 있는 방법이 필요합니다. 

문제를 풀고 나면 나오는 Lster 이라는 사람이 작성한 PDF 를 보면, 다음과 같이 일반식을 찾습니다.

세 자리 수를 곱했을 때 나오는 대칭수는 최대 xyzzyx 형태의 여섯자리 수가 됩니다. 이를 식으로 정리하면 다음과 같습니다.

즉 11 의 배수 형태가 나온다는 것입니다. 그러므로 둘 중의 하나는 소인수분해를 했을 때 반드시 11 을 포함해야 합니다.

그러면 아래와 같이 코드를 작성해 볼 수 있습니다.

result = 0 for i in range( 999, 99, -1 ) : for j in range( 999, 99, -1 ) : if ( 0 == ( i % 11 ) ) or ( 0 == ( j % 11 ) ) : number = i * j if is_palindrome_number( number ) : result = max( number, result ) print( result )

해당 문서에서는 조금 더 복잡한 최적화를 하고 있는데, 관심이 있으면 살펴 보시기 바랍니다.

원문 : Largest prime factor

Prime factor

일단 소인수가 뭔지 알아야 합니다. 일단 제가 알고 있는있는 소인수의 정의는 다음과 같습니다.

자신과 1 을 제외하고는 나눠지지 않는 않는 수.

실제 정의를 찾아 보았습니다만, 위에서 제가 한 정의는 "소수( prime number )" 에 대한 정의군요. 그리고 자연수여야 한다는 조건도 빠졌구요.

소수(素數, 발음: [소쑤], 문화어: 씨수, 영어: prime number)는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수이다. ( 중략 ) 1보다 큰 자연수 중 소수가 아닌 것은 합성수라고 한다. 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수로 정의하기도 한다.

출처 : [ 1 ].

구글 사전에서는 소인수를 다음과 같이 정의하더군요.

어떤 정수(整數)를 소수(素數)만의 곱으로 나타낸 때의 각 인수(因數).

구글 사전에서는 인수를 다음과 같이 정의하고 있습니다.

정수 또는 정식(整式)을 몇 개의 곱의 형태로 하였을 때, 그것의 각 구성 요소. 인자(因子).

즉 소인수는 "소수인 인수" 를 의미하는 거군요.

Generate prime numbers

그럼 가장 먼저 생각해 봐야 할 부분은 소수를 검사할 수 있는 방법이겠네요. 일단 소수값들을 나열해 봤습니다.

2 가 유일한 짝수이고 나머지는 홀수입니다. 그렇다면 계산의 시작은 더 이상 2 로 나눠질 수 없을 때까지 2 로 나누는 거겠죠.

예를 들어 60 이라는 수는 2 * 2 * 15 로 구성됩니다. 그러면 15 라는 수가 남네요. 이제 다음 소수인 3 으로 같은 작업을 반복할 수 있을 것입니다. 그러면 15 는 3 * 5 로 구성됩니다. 그러면 5 라는 수가 남네요. 이제 다음 소수인 5 로 같은 작업을 수행합니다. 그러면 5 * 1 이 되고, 1 은 나눌 수 없으니 계산이 종료될 겁니다. 결국 2, 3, 5 가 60 을 구성하는 소인수들이 됩니다. 

그런데 이건 합성수의 소인수를 찾는 것( 소인수분해 )이지 소수 자체를 구하는 것이 아닙니다. 그런데 이 소인수분해를 하는 과정자체가 소수를 찾는 과정이 아닐까라는 생각이 들었습니다.

왜냐하면 "자신과 1 을 제외한 자연수로 나눌 수 없는 자연수" 라는 정의를 생각하면 다음과 같은 가정을 깔 수 있을 것이기 때문입니다.

자신보다 작은 소수로 나눠봤을 때 나누어 떨어지면 그것은 소수가 아니다.

그러면 아래와 같이 소수를 생성해 볼 수 있습니다.

prime_numbers = [ 2 ] def generate_prime_numbers( max ) : for i in range( 3, max + 1) : is_prime_number = True for p in prime_numbers : if 0 == ( i % p ) : is_prime_number = False break if is_prime_number : prime_numbers.append( i ) generate_prime_numbers( 100 ) print( prime_numbers )

대충 살펴 보니 맞는 것 같군요.

그런데 여기에서 우리가 목표로 하는 600,851,475,143 을 넣고 generate_prime_factors() 를 호출하면 상상도 못할 시간이 걸리게 됩니다. 아무리 기다려도 끝날 생각을 하지 않습니다.

왜냐하면 이것의 시간복잡도는 O( i * p ) 이기 때문입니다; 여기에서 i 는 max 이고 p 는 i 보다 작은 소수의 개수입니다. 그러므로 최악의 경우라도 O( i^2 ) 보다는 작습니다만 max 가 워낙 크기 때문에 답이 없습니다.

그러므로 이건 적어도 이 문제를 풀기 위해서는 사용할 수 없는 함수입니다. 물론 언젠가는 계산이 끝나기는 하겠죠.

최적화를 위해서 병렬화를 고민해 볼 수도 있겠지만, 그건 너무 나간 것 같구요, 알고리즘적으로 해결할 수 있는 방법을 찾아 봐야 합니다.

Optimization : Only odd numbers

일단 단순하게 생각했을 때 2 의 배수인 숫자들( 즉, 짝수 )를 배제하면 대상이 절반이 줄어듭니다.

3 에서 시작한 것이니 for 문의 증가값을 2 로 하면 홀수만 나오게 되죠.

for i in range( 3, max + 1, 2 ) :

Optimization : Reduction

하지만 여전히 검사해야 할 숫자의 개수가 많습니다. 그런데 더 생각나는 방법은 없더군요. 그래서 참고자료를 찾아 봤습니다. [ 1 ] 에서는 다음과 같이 언급하고 있더군요.

그렇군요. 대상을 아예 없애 버리면 됩니다. 하지만 두 가지 문제가 있습니다.

• 메모리 문제 : 메모리가 버텨 줄 것인가?
• list operation : append, remove 등의 연산의 비용은 어떻게 할 것인가?

일단 메모리 문제를 검증해 봤습니다. 2 의 배수만을 배제한다고 가정했을 때, 배열의 크기는 1 GB 정도입니다. 5 의 배수까지 배제한다면 더 줄어들 수 있겠죠. 이 정도는 크게 문제가 없을 것이라는 판단을 했습니다.

두 번째로 list 관리 문제인데요, 소수가 아닌 것들에는 -1 값을 넣어 두면 되기 때문에 별 문제는 없을 것으로 보입니다. 게다가 저는 대상을 배제하는 기법을 사용하는 것이 아니라 소수인지 여부를 검사하는 기법을 사용하고자 합니다. 왜냐하면 대상을 배제하는 기법은 자신보다 큰 값들에 대해서 루프를 검사하는 비용이 들기 때문입니다. 결국에는 소수의 루프를 돌면서 검사하는 것과 크게 다르지 않은 비용이 나올 것이라고 생각합니다. 둘다 이중 루프로 시간복잡도는 거의 동일하기 때문입니다.

def generate_prime_numbers( max ) : prime_numbers = [ 2 ] # gather target numbers except multiples of 2 or 5 targets = list() for i in range( 3, max + 1, 2 ) : if 1 == ( i % 5 ) : targets.append( i ) # check if each item is not a prime number for i in targets : is_prime_number = True for p in prime_numbers : if 0 == ( i % p ) : is_prime_number = False break if is_prime_number : prime_numbers.append( int( i ) ) # return result. return prime_numbers

꽤 많이 배제한 상태임에도 불구하고, i7-4770K 에서 2 분이 지나도록 끝이 안 나더군요. 이것이 list 의 append() 에 드는 비용이 아닌가라는 의심이 들기 시작했습니다. 찾아 보니까, [ 간단한 구문 변경으로 속도를 향상시키기 ] 에서 백만개를 돌리는데 109 ms 를 소비하더군요. 물론 2015 년 자료니 머신의 성능이 어떤지는 모르겠지만, 시간이 많이 걸리는 건 사실입니다. 우리의 목표는 6000 억개이기 때문에 홀수만 따져도 3000 억개입니다. 단순하게 산술계산을 하면 60 만배이고 1000 ms 가 1 초이므로, 6 만초( 16.6 시간 )가 걸립니다. 그러므로 절대 append() 를 많이 사용해서는 안 되는 상황인 것입니다.

링크의 문서에 나온 것처럼 루프 밖에서 append 함수를 미리 선언하는 방식을 사용해 봤습니다( 마치 함수 포인터같은 녀석입니다 ).

target_append = targets.append for i in range( 3, max + 1, 2 ) : if 1 == ( i % 5 ) : target_append( i )

비용이 30 % 정도 줄어든다고 하니 기대시간은 약 11.62 시간입니다. 이것도 용납할 수 없는 수치입니다.

이걸 빠르게 할 수 있는 방법이 있으면 누군가 공유해 줬으면 좋겠군요.

추가 : [ 7. 10001st Euler ] 를 풀면서, 2 의 배수, 5 의 배수를 배제하고 소수를 뽑아 봤는데, 예상한 것과는 다르게 1 ~ 2 분 정도밖에 안 걸리더군요. 그러므로 위에서 예측한 비용은 잘못된 것으로 보입니다.

Prime Factorization

뭐 굳이 소수의 리스트가 없어도 문제를 해결할 방법은 있습니다.

원래 값을 2 부터 시작해서 나눕니다. 그리고 나머지가 0 이 아니면 다음 숫자로 넘어 갑니다. 나머지를 0 으로 만드는 수는 소인수라 생각할 수 있습니다.

def get_prime_factors( target ) : quotient = target prime_factors = list() append_factors = prime_factors.append i = 2 while( 1 != quotient ) : remainder = quotient % i if 0 == remainder : quotient /= i append_factors( i ) else : i += 1 return prime_factors prime_factors = get_prime_factors( 600851475143 ) print( prime_factors ) print( prime_factors[ len( prime_factors ) -1 ] )

답은 6857 입니다.

다른 사람들은 어떻게 풀었는지 확인해 봤는데 별 차이는 없네요. 단지 MathBlog 에서는 0 ms 에 가까운 대안을 소개하고 있습니다( 앞에서 소개했던 짝수배제 기법입니다 ). 

근데 컴퓨터가 좋아서인지 최적화를 안 해도 저는 0.0107 ms 가 나오는군요. 어쨌든 빠르면 좋은거니 저도 홀수를 배제해 봤습니다. 

i += 1 if 0 == ( i % 2 ) else 2

그랬더니 0.0058 ms 로 반쯤 줄어드는군요. 여기에서 5 의 배수도 배제해 봤습니다.

next = i + 1 i += 2 if ( 0 == ( next % 2 ) ) or ( 0 == ( next % 5 ) ) else 1

그런데 조건문이 두 개가 되지 비용만 더 올라갑니다( 0.0068 ms ). 너무 작은 비용에 대한 부적절한 최적화는 오히려 해가 된다는 사실을 알게 되네요.

전체 소인수 리스트를 수집하기 위해서 append() 를 사용하고 있습니다. 이를 배제하고 마지막 소인수만 반환한다면 더 빠른 결과를 볼 수 있습니다( 0.0048 ms ). 하지만 기본 while 비용이 있으므로 여기에서 드라마틱하게 내려가지는 않네요.

def get_last_prime_factor( target ) : quotient = target last_prime_factor = -1 i = 2 while( 1 != quotient ) : remainder = quotient % i if 0 == remainder : quotient /= i last_prime_factor = i else : i += 1 if 0 == ( i % 2 ) else 2 return last_prime_factor

참고자료

[ 1 ] 소수 ( 수론 ), 위키피디아.

[ 2 ] 소인수분해, 위키피디아.

원문 : Even Fibonacci numbers

문제 의도 해석

피보나치 수열에서 어떤 항은 앞의 두 수를 더해서 나온 것입니다.

• 3 = 1 + 2
• 5 = 2 + 3
• 8 = 5 + 3
• ...

문제에서는 짝수값만 더하라는 것이죠. 위의 예에서는 2 + 8 + 34 = 44 가 됩니다.

print_fibonacci function

일단 피보나치 수열의 값을 출력하는 함수를 만들어 보았습니다. 재귀적으로 호출하는 형식입니다. 단 100 을 넘지 않는 값을 출력하도록 했죠.

def print_fibonacci( a, b, max_term ) : if b > max_term : print( a ) return print( a ) print_fibonacci( b, a + b, max_term )

이를 실행하면 다음과 같은 결과가 나오죠.

물론 재귀 함수가 아니라 for 문을 통해서 구현하는 것도 가능합니다.

def print_fibonacci_with_while( a, b, max_term ) : a_val = a b_val = b while( b_val <= max_term ) : print( a_val ) temp = a_val a_val = b_val b_val = temp + b_val print( a_val )

sum_fibonacci function

이제 이 결과를 합쳐 보겠습니다. 결과를 더하는 건 결국 출력하는 순서와 동일하게 더해 가는 겁니다. 그런데 문제는 함수 내에서 a + b 가 발생하면, 다음 재귀 함수에서 b + next_term 를 하기 때문에( a' 로서 b, b' 로서 next_term, 그러므로 b 누적 ) 요소가 한 번씩 누적될 수 있다는 겁니다. 이에 주의해야 합니다.

def sum_fibonacci( a, b, max_term ) : if b > max_term : return a return a + sum_fibonacci( b, a + b, max_term )

sum_even_fibnoacci function

이제 문제의 의도대로 짝수값만 더하는 함수를 만듭니다. 임시 변수를 만들어서 홀수인 경우에는 0 취급을 해 주면 기존의 함수의 형태에서 크게 달라지지 않습니다.

def sum_even_fibonacci( a, b, max_term ) : a_val = 0 if ( a % 2 ) else a # a_val = ( a % 2 ) ? 0 : a if b > max_term : return a_val return a_val + sum_even_fibonacci( b, a + b, max_term )

파이썬 삼항 연산자가 좀 맘에 안 들기는 하지만, 어쨌든 비슷한 형태가 나옵니다.

4,000,000 까지의 피보나치 수열의 짝수항들을 더한 결과는 4613732 입니다.

More Efficient Method?

근데 재귀함수의 복잡도는 O( n ) 보다는 무조건 크게 나오는 것으로 보입니다; O( logn ), O( n^2 ), O( n^3 ). 그러므로 가급적이면 O( n ) 이 나오는 whlie 문을 사용하는 것이 좋을 것같습니다.

그런데 O( 1 ) 상수복잡도를 가지는 식은 없을까요? 왠지 불가능할 것 같습니다. 혹시 알고 계시다면 제보를 부탁드립니다.

우리는 짝수가 "홀수와 홀수" 혹은 "짝수와 짝수"를 더했을 때 나온다는 것을 알고 있습니다. 그래서 이를 이용해서 뭔가 간단한 규칙을 만들어 보려고 했습니다만, 어떻게 해야 할지 모르겠더군요. 그런데 이미 이걸 하신 분이 있더군요( F3 부터 세 번째 항들( F6, F9, ... )이 짝수라는 겁니다 ). 

"홀수 + 홀수 = 짝수" 이고 짝수 앞뒤에는 항상 홀수가 오니까 세 번째마다 반복되는 것으로 보입니다. 물론 이분은 "1, 1" 에서 시작하는 피보나치 수열을 가지고 계산한 것입니다.

이 분의 최종 코드는 다음과 같습니다( C# 으로 구현한 겁니다. 정확한 방식에 대해 알고자 하신다면 MathBlog 의 [ Project Euler - Problem 2 ] 를 참조하시기 바랍니다 ).

long[] fib = {2,0}; int i = 0; long summed = 0; while (fib[i] < 4000000) { summed += fib[i]; i = (i + 1) % 2; fib[i] = 4 * fib[(i + 1) % 2] + fib[i]; }

Where is Fibonacci Sequences?

피보나치 수열은 황금비를 형성한다고 합니다. [ 왜 자연은 피보나치 수열과 황금비를 택했을까 ] 를 읽어 보시면 재밌습니다. 엄청나게 세부적인 설명을 보려면 [ Fibonacci Numbers and Nature ] 라는 글을 참고하시면 좋습니다.

원문 :  Multiples of 3 and 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 )

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