[ Project Euler With Python ] 4. Largest palindrome product

원문 : Largest palindrome product

---

A palindromic number reads the same both ways. The largest palindrome made from the product of two 2-digit numbers is 9009 = 91 × 99.

Find the largest palindrome made from the product of two 3-digit numbers.

대칭수( 회문수 )는 양방향으로 동일하게 읽힙니다. 두개의 두 자리 수들을 곱해서 나오는 가장 큰 대칭수는 9009 = 91 x 99 입니다.

세 자리 숫자들을 곱해서 나오는 가장 큰 대칭수를 찾으십시오.

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, 3, 79, 83

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 )

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