컴퓨터를 다루다

함수는 총 세 가지로 작성하였습니다.

getDivisors(int) : 약수를 구하는 함수

perm(number list) : 숫자 배열의 모든 가능한 배열을 추출하는 함수

Decrypt(암호문, 암호문길이, 키) : 암호문을 각각의 키 배열로 브루트 포싱 공격하여 문자열을 얻어내는 함수

main함수에서는 단순히 Decrypt 함수를 불러내는 역할만 하면 되기 때문에 공격 이전에 암호문을 입력받고, 암호문의 길이와 가능한 키 블록의 크기를 알려주도록 하였습니다.

코드는 아래와 같습니다.

import sys

#Get Divisors, if 28 ==> 1,2,4,7,14,28
def getDivisors(num):
	half = int(num/2)
	divisors = []
	
	while half > 0:
		if num % half == 0:
			divisors.append(half)
		half -= 1
			
	divisors.append(num)
	
	return sorted(divisors)


#numlist_a is like [1,2,3,4]
def perm(numlist_a):
	length = len(numlist_a)
	if length == 1:
		return [numlist_a]
	else:
		result = []
		for i in numlist_a:
			numlist_b = numlist_a.copy()
			numlist_b.remove(i)
			numlist_b.sort()
			for j in perm(numlist_b):
				j.insert(0, i)
				if j not in result:
					result.append(j)
					
	return result
	
#Decryption Module
def Decrypt(encString, encLen, U_Key):
	F = open(Your_Directory, 'w') # Your_Directory is not Defined... Please Define your own directory
	msgsize 	= encLen
	keysize 	= len(U_Key)
	ret 		= ''
	
	blocksize 	= int(msgsize/keysize)
	buffer 	= [''] * keysize
	d_buffer	= [''] * keysize
	pos 		= 0
	
	U_Key 		= perm(U_Key)

	for i in range(keysize):
		decString	= encString[pos:pos + blocksize]
		buffer[i]	= decString
		pos 		+= blocksize
	
	for each_key in U_Key:
		for num, d_num in enumerate(each_key):
			d_buffer[d_num-1] = buffer[num-1]
		F.write(''.join(d_buffer))
		F.write("\n")
		
	F.close()
			


if __name__ == "__main__":
	EncryptedMessage	= input("Input Encrypted Message : ")
	EncryptedLen		= len(EncryptedMessage)
	KeyLenSeries		= getDivisors(EncryptedLen)
	
	print("\nYour Key Lengths are : ", KeyLenSeries)
	
	KeyLen			= int(input("\nSelect your key length : "))
	
	if KeyLen not in KeyLenSeries:
		print("Please Check Your Key Length Again.\nProcess Exit.")
		sys.exit(0)
	
	UseKey			= []
	for i in range(1,KeyLen+1):
		UseKey.append(i)
		
	Decrypt(EncryptedMessage, EncryptedLen, UseKey)

동작 구조는 다음과 같습니다.

초기 키 값은 처음 생성된 키 배열을 의미합니다.

키 길이 약수가 만약 4로 선택되었다면, [1,2,3,4]가 되겠죠.

Perm은 모든 배열의 가짓수를 구하는 함수이며, 해당 함수에서 나오는 값은 [1,2,3,4], [1,2,4,3], [1,3,2,4], [1,3,4,2] ..... [4,3,2,1]과 같은 모든 가짓수를 한 배열에 저장하게 됩니다.

그리고 이를 이용하여 각각 복호문을 만들게 되는 것입니다.

[그림 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이라는 모듈은 찾을 수가 없더군요...

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

Iterator(반복자)를 먼저 알아보기 전에 Iterable이 무엇인지 알아야 하겠죠?

먼저 Python doc의 Iterable 정의를 보도록 합시다.

 Iterable

  An object capable of returning its members one at a time. Examples of iterables include all sequence types (such as list, str, and tuple) and some non-sequence types like dict and file and objects of any classes you define with an __iter__() or __getitem__() method. Iterables can be used in a for loop and in many other places where a sequence is needed (zip(), map(), ...). When an iterable object is passed as an argument to the built-in function iter(), it returns an iterator for the object. This iterator is good for one pass over the set of values. When using iterables, it is usually not necessary to call iter() or deal with iterator objects yourself. The for statement does that automatically for you, creating a temporary unnamed variable to hold the iterator for the duration of the loop. See also iterator, sequence, and generator.

iterable을 정리해보면 member를 하나씩 반환할 수 있는 object를 말합니다.

iterable의 예로는 sequence type인 list, str, tuple이 있습니다. 

데이터 타입에 상관 없이 순회를 구현하고자 하는 필요성은 파이썬에만 있었던 것은 아니었다고 합니다. Iterator Pattern은 이미 하나의 디자인 패턴으로 정형화 되어 있는 것 중 하나입니다. 데이터 타입의 내부 구현을 노출하지 않고 포함하고 있는 요소들을 순회할 수 있는 방법을 제공하는 패턴을 이터레이터 패턴이라고 합니다.

※ 대부분 언어에서 이터레이터 패턴을 콜렉션 라이브러리의 구현 방식이나 문법 요소로 제공하고 있기는 하지만 파이썬 만큼 언어 자체에 자연스럽게 녹아 있는 경우는 많지 않다록 합니다.

사실 단순한 for문의 range도 iterable할 수 있는 list가 생성되었기 때문에 차례대로 사용할 수 있었던 것입니다.

for i in range(0,3):
	print(i)
#0
#1
#2

즉, range로 생성된 list가 iterable 할 수 있기 때문에 차례대로 member를 불러와 쓸 수 있다는 것입니다.

그리고 dictionary의 type인 dict도 iterable 할 수 있습니다. 그래서 다음과 같은 결과를 가지고 옵니다.

x = ['a':1, 'b':2, 'c':3]

for i in x:
	print(i)
	
#a
#b
#c

그리고 __iter__()나 __getitem__() 메소드로 정의된 class는 모두 iterable 할 수 있다고 합니다. 

iterable은 for loop말고도 zip(), map()과 같이 sequence 한 특징을 필요로 하는 작업을 하는 데 유용합니다.

zip([iterable, ...])

  This function returns a list of tuples, where the i-th tuple contains the i-th element from each of the argument sequences or iterables.

map(function, iterable, ...)

  Apply function to every item of iterable and return a list of the results.

zip()과 map()을 보면 argument를 iterable로 받는 것을 알 수 있습니다.

그리고 이제 iterator를 보도록 합시다.

iterator를 보기 앞서 먼저 Python docs의 정의를 살펴보도록 하지요.

Iterator

  An object representing a stream of data. Repeated calls to the iterator’s next() method return successive items in the stream. When no more data are available a StopIteration exception is raised instead. At this point, the iterator object is exhausted and any further calls to its next() method just raise StopIteration again. Iterators are required to have an __iter__() method that returns the iterator object itself so every iterator is also iterable and may be used in most places where other iterables are accepted. One notable exception is code which attempts multiple iteration passes. A container object (such as a list) produces a fresh new iterator each time you pass it to the iter() function or use it in a for loop. Attempting this with an iterator will just return the same exhausted iterator object used in the previous iteration pass, making it appear like an empty container.

iterator는 next()함수로 데이터를 순차적으로 호출 가능한 object입니다. 만약 마지막 데이터를 불러오고도 next()를 하거나 next()함수로 데이터를 가져올 수 없는 경우는 StopIteration exception을 발생시킵니다.

그렇다면 Iterable한 object는 iterator일까요?

결론부터 말씀드리자면, iterable하다고 해서 무조건 iterator라고 할 수는 업습니다.

저는 처음 iterator를 공부할 때, list를 iter()함수를 통해 iterable하게 만들어서 object를 생성해보았었습니다.

list는 iterable이지만 next()함수로는 순차적으로 불러올 수 없었습니다. list로 선언된 것은 보통 a[0], a[1] ...등으로 불러오지요.

list는 순회 가능한(iterable) 오브젝트이지만 __getitem__() 함수를 IndexError가 발생할 때까지 0부터 차례로 호출하기 때문에 개념이 약간 다르다고 할 수 있습니다.

Iterator의 자세한 원리

 만약 iterable하더라도 iterator가 아닙니다.

x = [1,2,3,4,5]
next(x)
Traceback (most recent call last):
	File .....
	
iterx = iter(x)
next(iterx)
#1

그리고 이제 list를 통해 예시를 설명하도록 하겠습니다.

아래의 소스를 보면 type이 어떻게 정의도는 지를 알 수 있습니다.

x = [1,2,3,4,5]
type(x)

#<class 'list'>

iterx = iter(x)
type(iterx)

#<class 'list_iterator'>

그리고 이제 python 3.x, python 2.7.x의 기준으로 next()를 사용하는 법을 보도록 하겠습니다.

x = [1,2]
type(x)

#<class 'list'>

iterx = iter(x)
type(iterx)

#<class 'list_iterator'>

#=-=-=-=-=-=-=-=-=-=-=- python 2 version
iterx.next()
#1
iterx.next()
#2
iterx.next()
#Traceback (most recent ...
#StopIteration
#=-=-=-=-=-=-=-=-=-=-=- python 3 version
next(iterx)
#1
next(iterx)
#2
#Traceback (most recent ...
#StopIteration

list는 1, 2로 이루어져 있으니, 3번째를 가져올 때 StopIteration을 하도록 되어 있습니다.

[그림 01]을 보면 더 확실하게 알 수 있겠습니다. ㅎㅅㅎ

[그림 01] python 2.7.x 와 python 3.x의 next()함수 사용법 비교

자, 그렇다면 next()함수를 통해 다음을 가져온다는 것은 알았는데, 살짝 더 들여다봅시다.

다음 소스는 4개의 list를 iterable한 list(list_iterator)를 구현하고 출력하는 프로그램입니다.

#iterator Test
#python 3 version source

List_first		= [1,2,3,4,5]
List_second 	= ['a','b','c','d']
List_third		= ["Third String", "Is", "List_Third~~"]
List_forth		= [10]

List_sum 		= []

List_sum.append(List_first)
List_sum.append(List_second)
List_sum.append(List_third)
List_sum.append(List_forth)


print("print List_sum : ", List_sum)

iterList = iter(List_sum)

print("\nmake it iterable!!!=-=-=-=-=-=-=-=-\n")

for i in range(4):
	print("print List_next()", next(iterList))

위의 소스를 실행시키면 [그림 02]와 같은 결과를 볼 수 있습니다.

[그림 02] list내의 list를 하나의 iterator로 생성

단순히 list를 가져온다는 것이 아니라 하나의 요소를 가져오는 것으로 이해하시면 더 좋을 것 같아 예시를 넣었습니다.

이러한 iteration은 [그림 03]과 같은 구조로 표현할 수 있습니다.

[그림 03] Iteration 구조

참고 URL : bluese05 님의 글

참고 URL : friberry 님의 글

Yield란 일종의 생성자(Generator)와 같습니다.

이더레이터(iterator)와는 비슷한 결과값을 가져오지만, 다른 것입니다.

이더레이터는 공부하다보니 알게 되었습니다. 일단 먼저 yield를 살펴보도록 하겠습니다.

먼저 Python docs에서 Generator의 정의를 보도록 합시다.

generator

  A function which returns an iterator. It looks like a normal function except that it contains yield statements for producing a series of values usable in a for-loop or that can be retrieved one at a time with the next() function. Each yield temporarily suspends processing, remembering the location execution state (including local variables and pending try-statements). When the generator resumes, it picks-up where it left-off (in contrast to functions which start fresh on every invocation).

Generator는 Iterator를 생성해주는 함수라고 간단하게 설명할 수 있겠습니다. iterator는 next()함수를 통해 순차적으로 값을 가져오는 object를 말합니다.

(LINK : Iterator & Iterable에 대한 설명)

Generator는 일반함수릉 크게 다를 것은 없지만 yield라는 가장 큰 차이점을 가지고 있습니다. 

아래의 소스는 yield의 기본 예제입니다.

#python 3 version source
#yield generator test source
#yield_Basic_Test.py

def number_generator(n):
	print("Function Start")
	while n < 6:
		yield n
		n += 1
	print("Function End")
	
if __name__ == "__main__":
	for i in number_generator(0):
		print(i)
		

결과 값은 다음과 같습니다.

[그림 01] yield_Basic_Test.py 결과값

for문과 number_generator(n)함수의 합이 만나서 [그림 01]과 같은 결과값이 나옵니다.

number_generator()함수에는 return이 없는데 어떻게 저렇게 while문 내에서 돌아가는 n의 값이 출력이 되는 것일까요?

기존의 함수의 Call 모습과 yield가 포함된 함수의 Call 모습을 비교해보도록 하겠습니다.

[그림 02] Main에서 Normal_function으로의 함수 흐름

Main함수에서 Normal_function으로의 함수 흐름은 기존의 여타 함수의 흐름과 다를 게 없습니다.

Main을 실행하다가 Normal_function으로 가서 함수 내의 루틴을 실행시킨 후 Main으로 돌아가 남은 Main의 루틴이 실행됩니다.

그렇다면 이제 yield가 포함된 함수를 보도록 합시다.

[그림 03] Main에서 number_generator()으로의 함수 흐름

number_generator()으로의 함수 흐름이 일반 함수의 흐름과는 많이 다릅니다.

이 흐름은 yield라는 것 때문입니다. yield는 두 번째 흐름처럼 n의 값을 return 하고 다시 함수로 돌아가게끔해주는 것입니다.

그렇다면 다음 소스를 보겠습니다.

Python docs에서 정의된 yield의 정의를 보도록 합시다.

Yield

The yield statement is only used when defining a generator function, and is only used in the body of the generator function. Using a yield statement in a function definition is sufficient to cause that definition to create a generator function instead of a normal function.

When a generator function is called, it returns an iterator known as a generator iterator, or more commonly, a generator. The body of the generator function is executed by calling the generator’s next() method repeatedly until it raises an exception.

When a yield statement is executed, the state of the generator is frozen and the value of expression_list is returned to next()‘s caller. By “frozen” we mean that all local state is retained, including the current bindings of local variables, the instruction pointer, and the internal evaluation stack: enough information is saved so that the next time next() is invoked, the function can proceed exactly as if the yield statement were just another external call.

As of Python version 2.5, the yield statement is now allowed in the try clause of a try ... finally construct. If the generator is not resumed before it is finalized (by reaching a zero reference count or by being garbage collected), the generator-iterator’s close() method will be called, allowing any pending finally clauses to execute.

yield는 generator가 일반 함수와 구분되는 가장 핵심적인 부분입니다. yield를 사용함으로써 어떤 차이가 있는지는 위의 일반 함수와 yield가 포함된 함수의 흐름으로 설명 드렸습니다.

더 자세하게 설명드리자면, generator 함수가 실행 중 yield를 만날 경우, 해당 함수는 그 상태로 정지되며, 반환 값을 next()를 호출한 쪽으로 전달하게 됩니다. 이후 해당 함수는 일반적인 경우처럼 종료되는 것이 아니라 그 상태로 유지되게 됩니다. 즉, 함수에서 사용된 local 변수나 instruction pointer 등과 같은 함수 내부에서 사용된 데이터들이 메모리에 그대로 유지되는 것입니다.   [bluese05님 글 출처]

#python 3 version source
#yield test source
#yield_Routine_Test.py

def generator_test(n):
	print("-=-=-=-=-=-= Generator Start =-=-=-=-=-=-")
	
	while(n < 3):
		print("<< Before Yield >>")
		yield n
		n += 1
		print("<< After Yield >>")
		
	print("-=-=-=-=-=-= Generator End =-=-=-=-=-=-")
	
if __name__ == "__main__":
	print("---------- Main Function Start ----------")
	
	for i in generator_test(0):
		print("Start For))))))))))))")
		print("Yield i is : ", i)
		print("End For))))))))))))))")
		
	print("---------- Main Function End ----------")
		

이 소스는 Main 함수와 generator_test()함수의 흐름을 보기 위한 함수입니다.

결과 값을 보도록 합시다.

[그림 04] yield_Routine_Test.py

결과값을 보면 먼저 Main이 시작하고 끝은 Main으로 끝납니다.

그리고 Generator 함수의 시작과 끝도 양 끝에 있습니다.

그렇다면 루틴은 <Before yield> -> for문 시작 -> for문 내의 print 실행 -> for문 끝 -> <After yield>로 되어 있고 이렇게 3회 반복됩니다.

이 루틴을 그림으로 그려보면 [그림 05]와 같습니다.

[그림 05] Main에서 for문으로 된 generator 함수의 흐름

먼저 Main이 실행되면서 for문 내의 generator_test함수로 들어갑니다. 그리고 함수가 시작되면서 while문으로 들어가 쭈욱 실행하면서 yield에서 n이라는 변수에 저장된 값을 반환합니다. 그리고, for문 내의 루틴이 실행된 후(print함수를 실행), 다시 yield 함수의 아래의 루틴을 실행 후 다시 while문이 실행되면서 루틴이 반복됩니다.

설명을 겁나 어렵게 했네요. 가볍게 <Before yield> -> for문 시작 -> for문 내의 print 실행 -> for문 끝 -> <After yield>로 루틴이 이루어져 있고, 그 겉에 Main과 generator함수가 있다고 보시면 됩니다.

자 이제, Python docs에서 Generator expression을 살펴보도록 하겠습니다.

generator expression

  An expression that returns an iterator. It looks like a normal expression followed by a for expression defining a loop variable, range, and an optional if expression. The combined expression generates values for an enclosing function:

generator expression이란 generator 함수를 좀 더 쉽게 사용할 수 있도록 제공되는 표현형식입니다. list comprehension과 비슷하지만, [] 대신 ()를 사용하면 됩니다. 아래의 소스는 0 ~ 9 사이 정수 중 홀수를 list와 generator object로 생성한 예제입니다.

[i for i in range(10) if i % 2]
#[1,3,5,7,9]
(i for i in range(10) if i % 2)
#<generator object at 0x......>

활용해보면 다음과 같은 소스와 결과를 볼 수 있습니다.

#python 3 version source
#Yield_Test.py

def generator(wordList):
	wordListLength = 0
	print("Generator Start!!")
	while(wordListLength < len(wordList)):
		yield wordList[wordListLength]
		wordListLength += 1
		
	
if __name__ == "__main__":
	Main_wordList = ["TEST", "IS", "WORK", "GOOD"]
	for i in generator(Main_wordList):
		print(i)
		
	print("Done!!!")

[그림 06] yield_Test.py 결과값

generator를 사용하는 이유는 크게 두 가지로 구분할 수 있습니다.

1. Memory를 효율적으로 사용할 수 있음

list comprehension과 generator expression으로 각각 생성했을 때 메모리 사용 상태를 봅시다.

#python 3 version 기준
import sys

a = [i for i in range(100) if i % 2] # list 
sys.getsizeof(a)
#268

b = [i for i in range(1000) if i % 2]
sys.getsizeof(b)
#2140

c = (i for i in range(100) if i % 2) # generator
sys.getsizeof(c)
#48

d = (i for i in range(1000) if i % 2)
sys.getsizeof(d)
#48

list의 경우 사이즈가 커질 수록 그만큼 메모리 사용량이 늘어납니다. 하지만, generator의 경우는 사이즈가 커진다해도 차지하는 메모리 사이즈는 동일한 것을 볼 수 있습니다. list와 generator의 동작 방식의 차이가 있을 뿐입니다.

list는 list 안에 속한 모든 데이터를 메모리에 적재하기 때문에 list의 크기 만큼 차지하는 메모리 사이즈가 늘어나게 됩니다. 하지만 generator의 경우 데이터 값을 한 번에 메모리에 적재하는 것이 아니라 next() 함수를 통해 차례로 값에 접근할 때마다 메모리에 적재하는 방식입니다.  [bluese05님 글 출처]

2. Lazy evaluation 즉 계산 결과 값이 필요할 때까지 계산을 늦추는 효과가 있음

예제로써 설명하도록 하겠습니다.

먼저 함수는 sleep_function(x)라고 선언하도록 합시다.

def sleep_function(x):
	print("Sleep..")
	time.sleep(1)
	return x

sleep_function()함수는 1초간 sleep을 수행한 후 x값을 return하는 함수입니다. 만약 위 sleep_function()함수를 이용해 list와 generator를 생성하면 어떻게 동작될지를 다음의 예제로 설명하도록 하겠습니다.

import time

def sleep_function(x):
	print("sleep...")
	time.sleep(1)
	return x

# list 생성
list = [sleep_function(x) for x in range(5)]

# generator 생성
generator = (sleep_function(y) for y in range(5))

for i in list:
	print(i)
	
print("=-=-=-=-=-=-=-=-=-=-=-=-=-=")

for j in generator:
	print(j)

위의 소스를 실행시키면 list생성과 generator 생성을 통해 각각 다른 방법으로 결과값을 받아오는 것을 알 수 있습니다.

결과 값은 [그림 07]과 같습니다.

[그림 07] list와 generator의 실행 차이

list의 경우는 list comprehension을 수행할 때, list의 모든 값을 먼저 수행하기 때문에 sleep_function() 함수를 range()만큼 한 번에 수행하게 됩니다.

generator의 경우 생성 시 실제 값을 로딩하지 않고, for문이 수행될 때 하나씩 sleep_function()을 수행하며 값을 불러오게 됩니다. generator의 특징 중 하나는 "수행 시간이 긴 연산을 필요한 순간까지 늦출 수 있다는 점이 특징"이라고 할 수 있습니다.

간단하게 말하면, list는 실행되고 결과 값을 list에 반환되어 [0,1,2,3,4] 값을 가지고 있게 됩니다.

그러나 generator는 실행되지 않고 object로 선언이 되기 때문에 필요한 때마다 실행시킬 수 있게 된 것입니다.

[그림 08] list comprehension과 generator expression 차이

참고 URL : haerakai님의 글

참고 URL : bluese05님의 글

[그림 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

겁나게 굉장합니다.

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

Python으로 Windows OS의 프로세스를 체크하는 소스입니다.

먼저 소스를 봅시다.

import os, sys, time
from win32com.client import GetObject

WMI = GetObject('winmgmts:')

ProcessList = []

processes = WMI.instancesOf('Win32_Process')

for process in processes:
	 ProcessList.append(process.Properties_('Name').Value)

print ProcessList

소스에서 os, sys, time 이외의 win32com.client라는 패키지와 GetObject라는 모듈이 있습니다.

win32com.client는 Python 모듈을 따로 받아줘야 합니다.

win32com.client 다운로드 링크(Source Forge) : https://sourceforge.net/projects/pywin32/files/?source=navbar

각설하고, 소스를 설명하겠습니다.

WMI에는 GetObject('winmgmts:')를 선언합니다.

processes라는 변수에는 WMI.instancesOf('Win32_Process')를 통해 프로세스에 대한 데이터를 모두 긁어옵니다.

그리고 for 문에서는 processes에서 있는 정보를 하나씩 가져와서 Properties_('Name').Value를 통해 하나씩 ProcessList에 append 하도록 만들었습니다.

이후 ProcessList를 통해 확인합니다.

<<참고>>

GetObject()함수는 VB(Visual Basic)의 GetObject() 함수와 동일한 기능을 한다고 합니다.

GetObject(Class = "ProgramID") 혹은 GetObject(Class = clsid)로 쓰면, 이미 실행하고 있는 COM object에 연결합니다.

COM(Component Object Model) object란 마이크로소프트가 개발한 소프트웨어 구성요소들의 응용프로그램 이진 인터페이스를 말합니다.

Python 2.7.x로 작성한 shutdown.py입니다.

다음 소스는 랜덤한 시간으로 shutdown을 할 수 있도록 하는데, shutdown은 os.system 함수를 사용합니다.

아주 아주 간단한 소스입니다.

-r 옵션은 restart옵션이고, 만약 컴퓨터를 끄고 싶다면 -s를 사용하면 되겠습니다.

#python 2 version source
import os
import random

time = random.randrange(600,900)

os.system("shutdown -r -t %s" % str(time))

os.system을 통해 cmd 창에서 실행할 명령어를 작성하였습니다.

str(time)은 time을 랜덤값으로 600 ~ 900sec를 주어지도록 하였습니다.