컴퓨터를 다루다

[그림 01] Problem 012 문제

문제 설명

문제 이름 : 많이 나누어지는 삼각수

문제 내용 : 삼각수는 자연수를 더해서 생성되는 숫자입니다. 예로 7번째의 삼각수를 구해보면 1 + 2 + 3 + 4 + 5 + 6 + 7을 계산하여 28이라는 숫자가 나옵니다. 그리고 28은 1, 2, 4, 7, 14, 28 이라는 6개의 약수를 가집니다. 그렇다면, 5개 이상의 약수를 가지는 숫자 중 가장 작은 삼각수는 28이라는 말이 됩니다. 이러한 조건으로 500개 이상의 약수를 가지는 가장 작은 삼각수를 구하십시오.

문제의 내용을 자세히 읽어보고 조건을 보도록 합시다.

1. 계산을 할 때마다 삼각수를 구해야 합니다.(ex> n번째 삼각수는 1+2+3+4+.....+n-1+n 임)

2. 약수를 구하는 알고리즘을 적용해야 합니다.

제가 처음에 소스코드를 작성할 때 계산할 때마다 삼각수를 구하여 계산하지 않고 1씩 증가시키는 바람에 굉장히 난해한 문제인가... 했습니다. 흑흑...

다음부터는 문제를 좀 더 자세히 읽어보고 해야겠습니다. 좋은 경험을 했습니다.

자 이제 본격적으로 소스코드를 보도록 합시다.

소스코드

- vol 01

첫번째 소스는 매우 단순하게 작성해보았습니다.

#Problem 012 Highly divisible triangular number
#python 3 version source

#the first triangle number to have over five hundred divisors

def getTriangleNum():
	triangleNum = 28
	next = 8
	count = 0
	
	while True:
		for i in range(1, triangleNum+1):
			if triangleNum % i == 0:
				count += 1
		
		if count >= 500:
			break
			
		count = 0
		triangleNum += next
		next += 1
	
	return triangleNum
	

if __name__ == "__main__":
	Main_triangleNum = getTriangleNum()
	print(Main_triangleNum)

위의 소스는 7번째부터 구해진 삼각수의 약수를 구하는 알고리즘입니다.

아주 단순하게 이루어진 소스코드로써, 1 ~ 삼각수 만큼 나눠보고 약수를 구합니다.

그리고 triangleNum에는 다음 삼각수가 되기 위한 next를 더하고, next는 += 1을 해주어 그 다음의 삼각수를 기약합니다.

위의 소스는 계산이 매우 많이 이루어지기 때문에 비효율적입니다... 계산을 엄청 많이 하게 될 것이고, 아마 하루종일 해도 답이 나오지 않을 것으로 예상됩니다.

- vol02

두번째 버전의 소스는 첨부하지 않겠습니다.

위의 소스에서 소수를 모두 제외한 계산을 해보도록 하기 위해 sieve를 첨가하였습니다. 그러나 계산의 가지수는 조금 줄어들 뿐 달라지는 건 거의 없었습니다.

- vol03

세번째 버전의 소스는 다음과 같은 알고리즘을 적용했습니다.

좀 더 효율적인 계산을 위해 미리 약수를 구하는 좋은 수학을 적용시켜 보았습니다.

알고리즘에 대한 설명은 [그림 02]와 같습니다.

[그림 02] 약수 구하는 효율적인 알고리즘

이제 이 알고리즘을 이용하여 소스코드를 작성하면 다음과 같습니다.

#Problem 012 Highly divisible triangular number
#python 3 version source

#the first triangle number to have over five hundred divisors

import math

def getTriangleNum():
	triangleNum = 28
	next = 8
	divisor = []
	
	while True:
		for i in range(1, int(math.sqrt(triangleNum))+1):
			if triangleNum % i == 0:
				divisor.append(i)
			
		if len(divisor) >= 250:
			break
		
		divisor = []
		triangleNum += next
		next += 1
	
	return triangleNum, divisor
	

if __name__ == "__main__":
	Main_triangleNum, d = getTriangleNum()
	print(Main_triangleNum, d)

소스를 설명하자면, 기존의 1 ~ 삼각수까지 range로 잡았다면 범위를 1 ~ log(n)까지 잡았습니다.

그리고 약수의 개수가 500개 이상임을 체크하기 위해서는 그의 절반인 250개 이상으로 보면 됩니다.

vol03의 소스는 5.54초 가량 걸렸습니다.

vol03과 vol01의 계산 효율은 n과 log(n)의 차이입니다.... 훨씬 차이 많이 납니다.

아, 그리고 이번에는 s-anand에서 소스코드를 첨부하지 않을 생각입니다.

이전의 소스코드에도 있었듯이, prime이라는 모듈을 첨부하여 계산하였습니다. prime이라는 모듈은 찾을 수가 없더군요...

그래서 어차피 설명도 이해도 할 수 없는 소스코드니깐 첨부하지 않을 것입니다.

[그림 01] Problem_011 문제

문제 설명

문제 이름 : 격자무늬의 근접한 숫자의 곱 중 가장 큰 값

문제 내용 : 20 x 20의 격자무늬로 이루어진 숫자열 중 빨간색으로 되어 있는 4개의 숫자의 곱은 26 x 63 x 78 x 14 = 1788696입니다. 그렇다면 근접한 4개의 숫자의 곱 중 가장 큰 값은 무엇입니까?(가로, 세로, 위, 아래, 대각선 모두 포함)

매우 힘들었습니다...

특히 대각선...

문제에서 필요한 내용은 일단 각설하고 소스코드로 넘어가도록 하겠습니다.

소스코드

#Problem 011 Largest product in a grid
#Python 3 version source

def getDiagonallyRight(List):
	DiagonallyRight = []
	num = 1
	
	for k in range(0,17):
		for j in range(0,17):
			for i in range(0,4):
				num *= int(List[k+i][j+i])
			DiagonallyRight.append(num)
			num = 1 
	
	return DiagonallyRight
	

def getDiagonallyLeft(List):
	DiagonallyLeft = []
	num = 1
	
	for k in range(0,17):
		for j in range(3,20):
			for i in range(0,4):
				num *= int(List[k+i][j-i])
			DiagonallyLeft.append(num)
			num = 1
			
	return DiagonallyLeft
	
def getRow(List):#Left to Right
	RowList = []
	num = 1
	
	for i in range(0, 17):
		for j in range(0, 17):
			for k in range(0, 4):
				num *= int(List[i][j+k])
			RowList.append(num)
			num = 1
	
	return RowList
	
def getCol(List):#Up to Down
	ColList = []
	num = 1
	
	for i in range(0, 17):
		for j in range(0, 17):
			for k in range(0, 4):
				num *= int(List[i+k][j])
			ColList.append(num)
			num = 1
			
	return ColList
			
if __name__ == "__main__":
	Main_grid = """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"""
	Main_gridsplit = Main_grid.split()
	Main_gridint	= []
	for i in Main_gridsplit:
		Main_gridint.append(int(i))
	
	Main_gridList = []
	for i in range(0, 400, 20):
		Main_gridList.append(Main_gridsplit[i:i+20])
		
	#Main_gridList ==> 2 degree Array~~!!
	
	Main_List = []
	
	Main_List += getRow(Main_gridList)
	Main_List += getCol(Main_gridList)
	Main_List += getDiagonallyLeft(Main_gridList)
	Main_List += getDiagonallyRight(Main_gridList)
	
	Main_sort = sorted(Main_List)
	print(Main_sort[-1])
	

Main_grid는 격자무늬 숫자열을 가져온 값입니다.

Main_gridsplit --> Main_gridint --> Main_gridList까지 해서 숫자 2차원 배열을 만들었습니다.

Main_List는 4개의 함수에서 구해진 곱을 모두 더할 리스트입니다.

getRow함수는 가로로 되어 있는 곱을 모두 구하는 함수입니다.

getCol함수는 세로로 되어 있는 곱을 모두 구하는 함수입니다.

getDiagonallyLeft함수는 오른쪽 위에서 왼쪽 아래로 향한 대각선으로 되어 있는 곱을 모두 구하는 함수입니다.

getDiagonallyRight함수는 왼쪽 위에서 오른쪽 아래로 향한 대각선으로 되어 있는 곱을 모두 구하는 함수입니다.

 소스코드가 매우매우 개판이지만, 먼저 나름의 자부심을 가지고 잘하는 분의 소스코드를 가져와 비교해보도록 하겠습니다.

nums = (
    ( 8, 2,22,97,38,15, 0,40, 0,75, 4, 5, 7,78,52,12,50,77,91, 8,),
    (49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48, 4,56,62, 0,),
    (81,49,31,73,55,79,14,29,93,71,40,67,53,88,30, 3,49,13,36,65,),
    (52,70,95,23, 4,60,11,42,69,24,68,56, 1,32,56,71,37, 2,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, 3,45, 2,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, 2,62,12,20,95,63,94,39,63, 8,40,91,66,49,94,21,),
    (24,55,58, 5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72,),
    (21,36,23, 9,75, 0,76,44,20,45,35,14, 0,61,33,97,34,31,33,95,),
    (78,17,53,28,22,75,31,67,15,94, 3,80, 4,62,16,14, 9,53,56,92,),
    (16,39, 5,42,96,35,31,47,55,58,88,24, 0,17,54,24,36,29,85,57,),
    (86,56, 0,48,35,71,89, 7, 5,44,44,37,44,60,21,58,51,54,17,58,),
    (19,80,81,68, 5,94,47,69,28,73,92,13,86,52,17,77, 4,89,55,40,),
    ( 4,52, 8,83,97,35,99,16, 7,97,57,32,16,26,26,79,33,27,98,66,),
    (88,36,68,87,57,62,20,72, 3,46,33,67,46,55,12,32,63,93,53,69,),
    ( 4,42,16,73,38,25,39,11,24,94,72,18, 8,46,29,32,40,62,76,36,),
    (20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74, 4,36,16,),
    (20,73,35,29,78,31,90, 1,74,31,49,71,48,86,81,16,23,57, 5,54,),
    ( 1,70,54,71,83,51,54,69,16,92,33,48,61,43,52, 1,89,19,67,48,),
)

def seqs(nums, row, col):
    if row + 4 <= len(nums):                                yield list(nums[i][col] for i in xrange(row, row+4))
    if col + 4 <= len(nums[row]):                           yield list(nums[row][i] for i in xrange(col, col+4))
    if row + 4 <= len(nums) and col + 4 <= len(nums[row]):  yield list(nums[row+i][col+i] for i in xrange(0,4))
    if row + 4 <= len(nums) and col >= 3:                   yield list(nums[row+i][col-i] for i in xrange(0,4))

def product(seq):
    n = 1
    for x in seq: n = n * x
    return n

def list_seqs(nums):
    for row in range(0, len(nums)):
        for col in range(0, len(nums[row])):
            for seq in seqs(nums, row, col):
                yield seq
				
print max(product(seq) for seq in list_seqs(nums))

아쉽게도 실행이 안 되네요.

위의 소스는 python2.7.x버전의 소스이기 때문에 2.7.13으로 실행해봤는데... 안 되네요.

일단 Yield라는 게 있네요. 파이썬을 공부하면서 필요한 요소가 하나하나 떠오릅니당 헤헤

이번에 Yield를 공부해서 업로드해야겠습니다.

[그림 01] Problem 010 문제

문제 설명

문제 이름 : 소수의 합

문제 내용 : 10 이하의 소수들의 합을 보면 2 + 3 + 5 + 7로 17이 나옵니다. 그렇다면 2,000,000 미만의 소수들의 합은 무엇입니까?

우리는 조건이 매우 간단하다는 것을 알 수 있습니다. 저도 그렇게 생각했습니다.

그러나... 저는 이 간단함에 여유를 부리고 시간을 매우 소비할 뻔 했습니다.

1. 소수 리스트를 구해야 함

2. 구해진 소수 리스트를 통해 모든 합을 구함

이제 소스를 작성해보도록 합시다.

소수를 구하는 방법이 이 문제의 핵심이라고 생각됩니다.

먼저 제가 가장 빠르다고 생각했던 소수 구하는 방법으로 작성해보았습니다.

소스코드

- vol01

#Problem 010
#Python 3 version source

#Get the sum of all the primes below 2,000,000

def getPrime(Number):
	primeList = [2]
	num = 3
	count = 100000
	
	while(num < Number):
		for x in primeList:
			if num % x == 0:
				break
			elif x == primeList[-1]:
				primeList.append(num)
				break
		if num == count:
			print(primeList)
			count += 100000
		
		num += 1
		
	return primeList
	
if __name__ == "__main__":
	Main_primeList = getPrime(2000000)
	sum = 0
	
	for i in Main_primeList:
		sum += i
	
	print(sum)

간단하게 getPrime으로 작성해보았습니다. 지금까지 제가 애용하던 소수 구하기입니다.

count는 그냥 100,000씩 끊어서 체크해보기 위함입니다. 하하..

시간은 1시간 정도 걸리려나요..? 1분동안 돌려보았지만 400,000까지는 해보았습니다. 그 이상은 하지 못했지요.(너무 오래걸려서..)

저는 여기서 getPrime함수의 한계를 느꼈습니다. 

이제 진정한 에라스토테네스의 함수로 넘어가볼까요???

먼저 다음 소스를 확인해주시기 바랍니다.

#Sieve Test
import time

def sieve(Limit):
	prime = set()
	not_prime = set()

	for i in range(2, Limit+1):
		if i not in not_prime:
			prime.add(i)
			for j in range(i*i, Limit+1, i):
				not_prime.add(j)
				
	return prime

start_time = time.time()	
primeList = sieve(2000000)
print(len(primeList))
end_time = time.time()

print("Time : ", end_time - start_time)

위의 소스는 에라스토테네스의 체를 시험한 것입니다.

참고 URL : http://ledgku.tistory.com/61

위의 URL은 에라스토테네스의 정리를 프로그램적으로 잘 설명해주셨습니다.

시간은 엄청 짧습니다!!

제 태블릿, limit == 2,000,000을 기준으로 1.27초 가량 걸렸습니다.

그렇다면 저 함수를 이용하여 온전한 primeList를 가져오면 좋을 것 같습니다.

- vol 02

두번째 버전의 소스입니다.

#Problem 010
#Python 3 version source

def sieve(Limit):
	prime = set()
	not_prime = set()

	for i in range(2, Limit+1):
		if i not in not_prime:
			prime.add(i)
			for j in range(i*i, Limit+1, i):
				not_prime.add(j)
				
	return prime
	
if __name__ == "__main__":
	Main_primeList = sieve(2000000)
	sum = 0
	
	for i in Main_primeList:
		sum += i
	
	print(sum)

이 함수를 이용하면 2초 가량 걸립니다용. 이번에는 나름 뿌듯합니다.

물론 sieve라는 건 살짝 답안지를 볼까 하는 욕구에서 비롯된 것이지만, 힌트를 얻고 답안지를 안 봤으니 나름 스스로 토닥토닥해줄 수 있지용.

이제 제가 답안지라고 생각하는 소스를 참고해봅시다.

참고 URL : http://www.s-anand.net/euler.html

sieve = [True] * 2000000    # Sieve is faster for 2M primes

def mark(sieve, x):
    for i in range(x+x, len(sieve), x):
        sieve[i] = False

for x in range(2, int(len(sieve) ** 0.5) + 1):
    if sieve[x]: mark(sieve, x)
print(sum(i for i in range(2, len(sieve)) if sieve[i]))

sieve 전역 변수는 True로 2,000,000개를 초기화해놓은 배열입니다.

mark함수는 초기화된 sieve와 배수로 지정할 소수를 넘겨줍니다.

그리고 모두 종료되면 모든 합을 구합니다.

일단 대단하다고 느껴집니당. 대단하지만, 이제는 조금 경쟁심이 생기네요 *^^*

[그림 01] Problem 009 문제

문제 이름 : 특별한 피타고라스 정리

문제 내용 : 피타고라스 정리의 삼각형에서 세 개의 자연수에 대한 설정은 a < b < c이며, a^2 + b^2 = c^2입니다. 예를들면 3^2 + 4^2 = 9 + 16 = 25 = 5^2라고 할 수 있습니다. 그렇다면, a + b + c = 1000일 때 위의 정의에 맞는 a, b, c를 구하고 그의 곱인 a*b*c를 구하시오.

우리는 다음과 같은 조건이 있다는 것을 알 수 있습니다.

1. a < b < c가 성립되어야 함

2. a^2 + b^2 = c^2이 되어야 함

3. a + b + c = 1000이 되어야 함

무작정 소스코드를 작성함에 있어서 많은 어려움이 있습니다...

먼저 손으로 구해본 결과 어떻게 해야할지 몰라서... BruteForcing을 해야 하나 하며 고민한 결과 정말로 BruteForcing을 하기로 했습니다. ㅎㅎ

첫번째 버전의 소스는 다음과 같습니다.

#Problem 009
#Python 3 version source

#a + b + c = 1000

def findPythagorean(Limit):
	a = 3
	b = 4
	c = 5
	
	for i in range(a, Limit):
		for j in range(b, Limit):
			for k in range(c, Limit):
				if k**2 == (i**2 + j**2):
					print("A : ", i, " B : ", j, " C : ", k, "A+B+C == ", i+j+k)
					if i+j+k == 1000:
						print(i, " ", j, " ", k) 
						break

첫번째 버전의 소스로 하면 겁나 오래걸립니다. 나오기는 합니다만, 중복되는 계산이 많아서 꽤 걸립니다.

두번째 버전의 소스로 넘어가 보면 조건을 하나 더 걸어보았습니다.

#Problem 009
#Python 3 version source

#a + b + c = 1000

def findPythagorean(Limit):
	a = 3
	b = 4
	c = 5
	
	for i in range(a, Limit):
		for j in range(b, Limit):
			if j > i:
				for k in range(c, Limit):
					if k > j:
						if k**2 == (i**2 + j**2):
							print("A : ", i, " B : ", j, " C : ", k, "A+B+C == ", i+j+k)
							if i+j+k == 1000:
								print(i, " ", j, " ", k)
								break

두번째 버전의 소스는 a < b < c 의 조건을 성립시켜주었습니다. 사실 첫번째 소스를 작성할 때 이 조건을 깜빡하고 했습니다. ㅎㅎ

그러나 이렇게 해도 시간은 어어어엄청 걸립니다. a + b + c 의 값이 1000이 되지 않으면 무한 반복이지요...(정확히는 a가 1000이 될 때까지 계속 반복됩니다.)

그렇다면 우리는 시간을 대폭 줄일 필요가 있습니다.

세번째 소스로 보겠습니다.

#Problem 009
#Python 3 version source

#a + b + c = 1000

def findPythagorean(Limit):
	half = Limit / 2
	a = 0
	b = 0
	c = 0
	
	while(a < half):
		a += 1
		b = half - a
		
		while(b < half):
			c = Limit - (a + b)
			if c < (a+b) and a**2 + b**2 == c**2:
				print("A : ", a, " B : ", b, " C : ", c, " A*B*C : ", a*b*c)
				b = Limit + 1
				a = b
				
			b += 1

if __name__ == "__main__":
	Main_LimitNumber = 1000
	
	findPythagorean(Main_LimitNumber)
		

반복구간을 결정할 필요가 있습니다.

먼저 a, b, c를 선언하고 초기화 해주고 다음으로 넘어갑시다.

a의 검색 구간을 전체의 반으로 줄여서 1부터 500으로 만들어서 그 반복을 설정합니다.

또한 b는 설정구간을 (절반 - a)로 지정해줍니다.

그 다음 while문으로 넘어가 b가 절반보다 작을 때 조건문을 실행합니다.

<조건문>

1. 삼각형의 기본적인 조건인 가장 큰 변이 두 변의 합보다 작아야 함.

2. 주어진 조건인 a^2 + b^2 = c^2

위의 두 조건이 만족할 때 a, b, c를 각각 출력합니다. 그리고 적절하게 빠져나갈 수 있도록 길을 만들어놓습니다.

만약 위의 조건문이 실행되지 않을 시 b += 1을 실행해주고, while문을 반복합니다.

이렇게 되면 a의 범위 b의 범위 c의 범위 1000 * 1000 * 1000이 아닌 (500 * 501) / 2 * 500으로 빠르게 해결할 수 있습니다.

물론 그 사이사이의 조건 계산과 값 계산을 뺀다면 더욱 빠르게 할 수 있다는 것을 의미합니다.

1초에 할 것을 0.062초만에 하는 것입니다.

저보다 겁나 뛰어난 분의 소스를 가져와보도록 합시다.

for a in range(1, 1000):
     for b in range(a, 1000):
         c = 1000 - a - b
         if c > 0:
             if c*c == a*a + b*b:
                 print(a*b*c)
                 break

겁나게 굉장합니다.

범위를 절반이 아닌 전체로한 것 이외에 조건은 똑같습니다.... 우왕...

[그림 01] Problem 008 문제

문제 이름 : 가장 큰 곱(product)

문제 내용 : 네 개의 가장 인접한 숫자들로 이루어진 천의 자리 가장 큰 곱은 9 * 9 * 8 * 9 = 5832입니다. 즉, 위의 숫자 나열 중에 9989라고 연속되어 있는 숫자가 있고, 이 숫자들의 곱이 4개의 숫자 중 가장 큰 것이라는 의미입니다. 그렇다면, 열 세 개의 숫자가 나열되어 있는 것들 중 가장 큰 곱을 가지고 있는 것은 무엇입니까?

그렇다면 우리는 13개의 연속된 숫자 중 가장 큰 곱이 나올 숫자를 찾아 그 값을 출력해야 합니다.

우리는 다음과 같은 조건이 부여된 것입니다.

1. 13자리 자리씩 끊어서 가장 큰 곱이 나오는 것을 찾도록 해야 함

1. 13자리를 각각 곱해야 함

#Problem 008
#Python 3 version source
 
import operator
 
Number = """7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450"""
 
NumberList  = list(Number) #Number List
ProductDict = {}           #New dictionary type
position    = 0
num         = 1
 
while(position+13 < len(NumberList)):
  for i in range(position, position+13):
    num *= int(NumberList[i])
  ProductDict[num] = Number[position:position+13]
  num = 1
  position += 1
   
sorted_ProductDict = sorted(ProductDict.items(), key=operator.itemgetter(1)) #key 값으로 정렬
#sorted_ProductDict = sorted(ProductDict.items(), key=operator.itemgetter(0)) #value 값으로 정렬
print(sorted_ProductDict)

이제 소스코드를 작성해보도록 하겠습니다.

위와 같이 Number에 숫자를 모두 넣어주고 13칸 씩 이동하면서 각 숫자를 모두 더하여, 가장 큰 숫자를 프린트하도록 합니다.

ProductList는 13개의 숫자를 곱하여 나온 값을 하나하나 List로 저장하는 것이고, 이를 sort()함수로 정렬한 뒤, 가장 큰 숫자를 출력하도록 했습니다.

메모리적 이득을 보기 위해서는 set()을 쓰는 것도 괜찮은 방법이라고 생각합니다.

또한 소스에서 21번째 라인을 보시게 되면 key 값으로 정렬하지 않고 value 값으로도 정렬할 수 있습니다.

이제 저보다 겁나 잘하는 사람의 소스를 가져와서 비교해보도록 할 것입니다.

마음의 준비를 해야겠네요..

s = '7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450'
n = 0
for i in range(0, len(s)-4):
    p = 1
    for j in range(i,i+5):
        p = p * int(s[j])
    if p > n: n = p
 
print(n)

이 소스는 13개의 숫자가 아니라 5개의 숫자를 곱한 값을 구하는 공식입니다.

확실히 더 효율적으로 보입니다.

굳이 List에 저장할 필요 없이 더 크면 저장하고 크지 않으면 저장하지 않는 알고리즘이 더 메모리를 아낄 수 있는 것 같습니다.

[그림 01] Problem 007 문제

문제 이름 : 10001번째 소수

문제 내용 : 처음 6개의 소수가 2, 3, 5, 7, 11, 13이라고 할 때, 6번째 소수는 13이라는 걸 알 수 있습니다. 그렇다면 10001번째의 소수는 무엇입니까?

우리는 간단하게 다음과 같은 조건을 만족하는 소스를 작성해봅시다.

1. 소수를 구하는 함수

2. 소수 리스트의 길이가 10001이 될 때까지 반복

3. 마지막 소수를 출력

이제 소스를 작성해봅시다.

#Problem 007
#Python 3 version source

#By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
#What is the 10 001st prime number?

def getPrime():    #소수 구하는 함수
	primeList = [2]  #소수 첫번째 리스트
	num = 3          #두 번째 소수 비교하는 수
	
	while(len(primeList) < 10001):    #primeList가 10001번째보다 작으면 계속 반복
		for x in primeList:        
			if(num % x == 0):
				break
			elif(x == primeList[-1]):
				primeList.append(num)
				break
		num += 1
		
	return primeList

if __main__ = "__name__":
	Main_primeList = getPrime()
	
	print(Main_primeList[-1]) #마지막 소수 리스트의 숫자를 출력

getPrime 함수는 소수를 구하는 함수이고, 이 함수는 primeList의 길이가 10001번째가 아니면 계속 반복하여 구하는 구조입니다.

그리고 모두 구한 후, main에 있는 변수로 리턴해주고, 이 중 마지막 리스트를 출력합니다.

이제 저보다 잘하는 사람의 소스를 참고해봅시다.

두근두근...!!

#python 2 version source
import prime
print prime.prime(10000)

오... 신이시여... 이럴수가...

위의 소스는 prime이라는 모듈을 다운받아야 실행이 되는 것 같습니다.

저는 다운받는데 실패했습니다.

흑흑.... 그냥 저 위의 소스를 활용하렵니다.

[그림 01] Problem 006 문제

문제 이름 : 합해서 제곱과 제곱해서 합하는 것의 차이

문제 내용 : 1,2,3,4 ... 10을 각각 제곱해서 더하면 385입니다. 그리고 1,2,3,4 ... 10을 미리 더한 후 제곱을 하면 55의 제곱이고 이는 3025입니다. 그리고 그 차이는 2640입니다. 그렇다면 이 범위를 100으로 넓히고 그 차이는 얼마입니까?

우리는 여기서 다음과 같은 조건을 알 수 있습니다.

1. 1~100의 각각의 제곱을 더해야 하는 값이 필요함

2. 1~100을 모두 더한 후 제곱을 하는 값이 필요함

3. 위의 둘의 차이를 구함

굉장히 간단합니다.

다짜고짜 소스를 작성했습니다.

#Problem 006
#Python 3 version source

def getSquaresOfFirstHundred(Range_Num):
	#1**2 + 2**2 + 3**2 + 4**2 + 10**2 = 385
	num = 0
	for i in range(1, Range_Num+1):
		num += i**2
	return num
	
def getSumOfTheFirstHundred(Range_Num):
	#(1+2+3+...10)**2 = 55**2 = 3025
	num = 0
	for i in range(1, Range_Num+1):
		num += i
	return num**2

if __name__ == "__main__":
	Main_Range = 100
	Main_SquaresOfFirstHundred = getSquaresOfFirstHundred(Main_Range)
	Main_SumOfTheFirstHundred  = getSumOfTheFirstHundred(Main_Range)
	
	print(Main_SumOfTheFirstHundred - Main_SquaresOfFirstHundred)

위의 소스는 단순합니다.

getSquareOfTheFirstHundred와 getSumOfTheFirstHundred함수를 각각 선언하고, 두 값을 구합니다.

그리고 이 둘을 뺀 값을 출력합니다.

저보다 굉장히 잘하는 분이 작성하신 소스코드는 다음과 같습니다.

r = range(1, 101)
a = sum(r)
print a * a - sum(i*i for i in r)

이런 간단한 문제에서도 격이 느껴지네요.

저는 아직까지 Python의 장점을 제대로 활용하고 있지 않은 것 같습니다.

좀 더 활용할 수 있도록 간단한 소스를 작성할 수 있도록 해야 할 것 같습니다. ㅎㅎ

[그림 01] Problem 005 문제

문제 제목 : 가장 작은 최소공배수

문제 내용 : 2520은 1이상 10이하로 모두 나누어지는 숫자 중 가장 작은 값(최소공배수)입니다. 그렇다면, 1이상 20이하의 최소공배수(모두 나누어지는 가장 작은 수)

※ evenly divisible : 고르게, 골고루 나누어 질 수 있는

우리는 다음과 같은 조건을 알 수 있습니다.

1. 최소공배수가 되는 녀석을 알아내야 함

2. 소수는 다 들어 있을 것임

위의 조건으로 먼저 손으로 풀어보니(노가다가 좀 있었습니다), 5 * 7 * 9 * 11 * 13 * 16 * 17 * 19이 정답이 되었습니다.

그런데 이걸 어떻게 규칙으로 만들어야 하나.... 손으로 많은 고민을 해본 결과 다음과 같은 규칙을 알게 되었습니다.

일단 소수를 모두 구한 후, 소수가 아닌 녀석들을 한 번 보았습니다.

소수 : 2, 3, 5, 7, 11, 13 ,17, 19

소수가 아닌 값 : 4, 6, 8, 9, 10, 12, 14, 15, 16, 18, 20

그리고 정답의 9와 16을 보니, 20보다 작은 소수의 제곱이었습니다.

9는 3^2, 16은 2^4입니다.

그리고 나머지 소수는 제곱만 해도 20을 넘기 때문에 제외되는 것이었습니다.

이제 위의 내용을 통해 소스 코드를 작성해보도록 합시다.

#Problem 005
#Python 3 version source

#answer = 5*7*9*11*13*16*17*19

def getPrime(primeRange):
	primeList = [2] #소수 리스트
	number = 3      #소수 시작 숫자
	
	while(number <= primeRange):
		for i in primeList:
			if(number % i == 0):      #기존의 소수로 나누어지면 소수가 아님
				break
			elif(i == primeList[-1]): #마지막 소수로도 안 나눠지면 소수 
				primeList.append(number)
				break
		number += 1
	
	return primeList
	
if __name__ == "__main__":
	Main_Smallest_Num_Range = 20
	Main_primeList = getPrime(Main_Smallest_Num_Range)
	Main_elseList = list()
	Main_Answer = 1
	Main_Exception = set([2,3])
	
	#Main_Smallest_Num_Range를 넘지 않을 때까지 제곱을 함
	for i in Main_primeList:
		num = i
		while True:
			if num * i > Main_Smallest_Num_Range:
				break
			num *= i
			
		Main_elseList.append(num)
	
	#Main_Set은 최소공배수에 들어갈 최종 리스트들임
	#Main_primeList : 소수들의 리스트
	#Main_elseList  : 소수가 아닌 것들의 제곱 리스트
	#Main_Exception : 2와 3은 제외되기 때문에 제외시킬 리스트
	#Main_Answer    : 최소공배수 값(답)
	Main_Set = set(Main_elseList + Main_primeList) - Main_Exception
	
	#최소공배수를 만드는 함수
	for i in Main_Set:
		Main_Answer *= i
	
	print("Set List : ", Main_Set)
	print("Answer   : ", Main_Answer)

소스 못 쓸 줄 알았는데 다행이 써지네요.

신난다요.

이제 저보다 잘하는 사람의 답을 가져와보도록 합시다.

def gcd(a,b): return b and gcd(b, a % b) or a
def lcm(a,b): return a * b / gcd(a,b)

n = 1

for i in range(1, 21):
    n = lcm(n, i)
print(n)

아....!

[그림 02] 마...맞다....! gcd... lcm은 또 뭐지..!?

겁나 잘하네요... 저는 gcd, lcm의 존재를 모르고 있었습니다...

이번에는 나름 멋지게 짠 거라고 생각했거늘, 버젓이 gcd, lcm이라는 기능이 있었네요 헿.

gcd는 최대공약수 함수이며, lcm은 최소공배수 함수입니다.

gcd(a, b) : a와 b의 최대공약수를 구하여 return함

lcm(a, b) : a와 b의 최소공배수를 구하여 return함

gcd와 lcm을 만들어서 활용할 수 있는 방향도 있군요..!

P.S. python에서는 gcd와 lcm을 지원하지 않습니다. 때문에 두 번째 소스에서는 gcd와 lcm을 맞춤형으로 선언한 것을 알 수 있습니다.

[그림 01] Problem 004 문제

문제를 살펴보면 다음과 같습니다.

문제 이름 : 가장 큰 데칼코마니 숫자

문제 내용 : Palindromic 숫자란 앞으로 읽나 뒤로 읽나 같은 숫자를 의미합니다. 두 자리 숫자 두 개로 만들어진 가장 큰 Palindromic 숫자는 9009 = 91 x 99입니다. 그렇다면 세 자리 숫자 두 개로 이루어진 Palindromic 숫자 중 가장 큰 숫자를 찾으십시오.

※ palindrome 이란 앞에서부터 읽나 뒤에서부터 읽나 똑같은 것을 의미함(madam, nurse run 과 같은 것)

우리는 다음과 같은 조건을 가진다는 것을 알 수 있습니다.

1. 3자리 숫자 두 개를 곱해서 생성된 숫자를 Palindromic 숫자인지 구분해야 함

2. 범위는 999 * 999의 가지 수를 가짐

이제 소스코드를 작성해보도록 합시다.

뭔가 발코드인 느낌도 나고... 아니면 괜히 복잡하게 작성한 것 같을 수 있습니다.

def judgePalindromic(palinNum):
	palinNumList = list(str(palinNum))#palindromic 숫자를 확인하기 위한 숫자 구분
	palinNumLen  = len(palinNumList)  #palindromic 숫자의 길이
	
	for i in range(int(palinNumLen / 2)):
		#palindromic 숫자의 맨 앞과 맨 끝의 숫자를 비교함(길이가 홀수/짝수 상관 없음)
		if palinNumList[i] != palinNumList[-(i+1)]:
			return 0
	return palinNum
	
if __name__ == "__main__":
	Main_PalindromicNumber = 0
	Main_Digits = [999, 999]     #999 * 999의 가지 수
	Main_LimitRange = 0          #999 ~ LimitRange를 정해줌
	
	#Main_Digits[0] x Main_Digits[1]의 곱을 이중 for문으로 작성
	for i in range(Main_Digits[0], Main_LimitRange, -1):
		for j in range(Main_Digits[1], Main_LimitRange, -1):
			num = i * j
			
			#Palindromic숫자고, 이전의 Palindromic숫자보다 크면 Main_PalindromicNumber에 저장함
			if judgePalindromic(num) and Main_PalindromicNumber < num:
				Main_PalindromicNumber = num
	
	print(Main_PalindromicNumber)

judgePalindromic(숫자) 함수는 Palindromic 숫자임을 확인해주는 함수입니다.

main함수에서는 세 자리 숫자의 두 개를 곱하여 Palindromic 숫자임을 확인하는 이중 for문을 작성하였고, if를 통해 (0이 아닌 값이 반환) and (이전의 숫자보다 크면 Main_PalindromicNumber에 저장)합니다.

이 모든 것들이 완료되면 출력하게 됩니다.

저보다 잘하는 사람은 겁나 많습니다.

사실 이쯤되면 조금 분하기도 합니다. 저는 겁나 길게 작성했는데 이 소스는 겁나 짧네요.

출처 : http://www.s-anand.net/euler.html

n = 0
for a in range(999, 100, -1):
    for b in range(a, 100, -1):
        x = a * b
        if x > n:
            s = str(a * b)
            if s == s[::-1]:
                n = a * b
print(n)

맞다.... 그랬습니다. string값을 뒤집어서 그 값이랑 기존의 값이랑 비교하면 되는 것이었습니다.

굉장하다 이 소스...!!!

저는 바보같이 그것을 일일이 비교하였습니다.

s == s[::-1]은 기존의 string == 반대로 string입니다.