코드노예

Combination 은 다음 식으로 계산이 가능합니다.

nCr = n! / ((n-r)! * r!)

n, r 숫자가 커지면 결과가 너무 커져서 계산이 힘들어 집니다.

대신 계산을 끝까지 하지 않고도, 소인수 분해는 가능합니다.

아래 코드를 이용하면 됩니다.

def findPrimeFactors(n, k):
    tPrimeFactorsMap = {}
    
    # 소수인지 합성수인지 체크하기 위한 배열 - 최대 소수는 n 보다 작거나 같음
    tCompositeChecker = [True] * 2 + [False] * n
    
    for p in xrange(n + 1):
    
    	# 합성수인 경우 다음으로 넘김
        if tCompositeChecker[p]:
            continue
        
        q = p
        m = 1
        
        # 현재 소수 p가 몇 번 나오는지 체크하기 위한 변수
        tPrimeCnt = 0
        
        # 현재 체크 중인 q에 대해서 해당 소수 p가 몇 번 들어 있는지 체크하기 위한 리스트
        tPrimePowers = [0] * (n + 1)
        
        while True:
            tPrimePowers[q] = tPrimePowers[m] + 1
            
            # q 가 k 보다 작거나 같으면 분모, 해당 개수 만큼 빼줌
            if q <= k:
                tPrimeCnt -= tPrimePowers[q]
            # q 가 n - k 보타 크면 분자, 해당 개수 만큼 더해줌
            if q > n - k:
                tPrimeCnt += tPrimePowers[q]
                
            q += p
            m += 1
            if q > n:
                break
            
            # q는 p의 배수이므로 합성수
            tCompositeChecker[q] = True
            
        tPrimeFactorsMap[p] = tPrimeCnt
        
    return tPrimeFactorsMap

* 이 포스트는 "파이썬 프로그래밍으로 지루한 작업 자동화하기" 의 내용을 참조해서 작성하였습니다.

* 파이썬 3.3을 기준으로 작성하였습니다.

정규표현식으로 텍스트 패턴 검색

정규식 객체 만들기

re 패키지를 import 합니다.

>>> import re

정규표현식을 나타내는 문자열 값을 re.compile()에 전달하여 Rebex 패턴 객체 (혹은 Regex 객체)를 생성합니다.

>>> phoneNumRegex = re.compile(r'\d\d\d-\d\d\d-\d\d\d\d')

(참고로 미국 전화번호 포맷은 000-000-0000 형식입니다.)

Regex 객체를 이용한 패턴 검색

위에서 생성한 패턴 객체에 search 매써드를 이용해서 match 객체를 돌려 받습니다.

>>> mo = phoneNumRegex.search('My number is 212-555-1234.')

Match 객체에 group 매써드를 이용해서 결과를 확인합니다.

>>> print (mo.group())

212-555-1234

정규표현식을 사용한 더 많은 패턴 검색

괄호로 묶기

패턴 중의 일부를 분리해서 사용하는 경우 (전화번호에서 지역 코드를 나머지 번호로부터 분리하고 싶은 경우)

>>> phoneNumRegex = re.compile(r'(\d\d\d)-(\d\d\d-\d\d\d\d)')

>>> mo = phoneNumRegex.search('My number is 212-555-1234.')

>>> print (mo.group(1))

212

>>> print (mo.group(2))

555-1234

>>> print (mo.group(0))

212-555-1234

>>> print (mo.group())

212-555-1234

>>> print (mo.groups())

(212, 555-1234)

파이프로 여러 그룹 검색하기

'|' 글자를 파이프라고 합니다.

여러 가지 표현 중 하나만 일치해도 되는 곳에 사용 (or)

처음으로 일치하는 텍스트가 Match 객체로 반환됩니다.

>>> testRegex = re.compile(r'AAA|BBB')

>>> mo1 = testRegex.search('AAA and BBB')

>>> mo1.group()

'AAA'

>>> mo2 = testRegex.search('BBB and AAA')

>>> mo2.group()

'BBB'

물음표와 선택적 검색

해당 부분이 없거나 한 번만 나타나는 경우

>>> testRegex = re.compile(r'Super(wo)?man')

>>> mo1 = testRegex.search('The world of Superman')

>>> mo1.group()

'Superman'

>>> mo2 = testRegex.search('The world of Superwoman')

>>> mo2.group()

'Superwoman'

* 및 + 를 이용한 선택적 검색

* 표시는 0개 또는 그 이상과 일치를 의미

+ 표시는 1개 또는 그 이상과 일치를 의미

>>> testRegex = re.compile(r'Super(wo)*man')

>>> mo1 = testRegex.search('The world of Superman')

>>> mo1.group()

'Superman'

>>> mo2 = testRegex.search('The world of Superwoman')

>>> mo2.group()

'Superwoman'

>>> mo3 = testRegex.search('The world of Superwowowoman')

>>> mo3.group()

'Superwowowoman'

>>> testRegex = re.compile(r'Super(wo)+man')

>>> mo1 = testRegex.search('The world of Superman')

>>> print mo1

None

>>> mo2 = testRegex.search('The world of Superwoman')

>>> mo2.group()

'Superwoman'

>>> mo3 = testRegex.search('The world of Superwowowoman')

>>> mo3.group()

'Superwowowoman'

중괄호를 이용하여 특정 횟수 반복 패턴 검색

(A){3} # A가 정확하게 3회 반복

(A)(A)(A)

(A){3,5} # A가 3회 ~ 5회 반복

((A)(A)(A)|(A)(A)(A)(A)|(A)(A)(A)(A)(A))

>>> aRegex = re.compile(r'(A){3}')

>>> mo1 = aRegex.search('AAA')

>>> mo1.group()

'AAA'

최대 일치와 최소 일치

(A){3,5} 정규식은 'AAAAA' 문자열에서 'AAA', 'AAAA', 'AAAAA' 와 일치할 수 있다. 최대 일치는 'AAAAA', 최소 일치는 'AAA" 인데, 파이썬의 정규표현식은 기본적으로 최대 일치되는 값을 돌려줍니다. 최소 일치되는 값을 돌려받고 싶다면, 중괄호 뒤에 '?' 기호를 적어주면 됩니다.

>>> aRegex = re.compile(r'(A){3,5}')

>>> mo1 = aRegex.search('AAAAA')

>>> mo1.group()

'AAAAA'

>>> aRegex = re.compile(r'(A){3,5}?')

>>> mo2 = aRegex.search('AAAAA')

>>> mo2.group()

'AAA'

전체 패턴 검색

findall() 매써드 사용

>>> phoneNumRegex = re.compile(r'(\d\d\d)-(\d\d\d-\d\d\d\d)')

>>> phoneNumRegex.findall('Cell: 212-555-1234 Work: 212-555-5678')

문자 클래스

사용자 정의 문자 클래스 만들기

대괄호를 이용하여 사용자 정의 문자 클래스를 정의할 수 있습니다. 

예를 들어 대소문자 구분없이 영어의 소문자 하나를 매치시키고 싶다면, 아래와 같이 정의하면 됩니다.

>>> vowelRegex = re.compile(r'[aeiouAEIOU]')

하이픈을 사용하면 범위를 포함시킬 수 있습니다. 

>>> alnumRegex = re.compile(r'[a-zA-Z0-9]')

캐럿과 달러 기호 글자

^ - 텍스트의 시작

$ - 텍스트의 끝

>>> beginsWithHello = re.compile(r'^Hello')

와일드카드 문자

정규식에서 '.' 은 와일드카드라고 하며 줄바꿈을 제외한 모든 문자와 일치한다.

>>> atRegex = re.compile(r'.at')

>>> atRegex.findall('The cat in the hat sat on the flat mat.')

['cat', 'hat', 'sat', 'lat', 'mat']

대소문자를 구분하지 않고 일치시키기

>>> regex = re.compile(r'test', re.I)

문자열 매치해서 치환하기

>>> namesRegex = re.compile(r'Agent \w+')

>>> namesRegex.sub('CENSORED', 'Agent Alice gave the secret documents to Agent Bob')

'CENSORED gave the secret documents to CENSORED'

일치하는 텍스트 그 자체를 대체할 텍스트의 일부로 사용해야 하는 경우에는 \1, \2, \3 등과 같이 입력하면 Match 객체의 그룹 1, 2, 3 등으로 대체 됩니다.

>>> namesRegex = re.compile(r'Agent (\w)\w*')

>>> namesRegex.sub(r'\1****', 'Agent Alice gave the secret documents to Agent Bob')

'A**** gave the secret documents to B****'

* 이 포스트는 "파이썬 프로그래밍으로 지루한 작업 자동화하기" 의 내용을 참조해서 작성하였습니다.

* 파이썬 3.3을 기준으로 작성하였습니다.

문자열 리터럴

문자열은 ' 로 시작해서 ' 로 끝난다. 혹은 " 로 시작해서 " 로 끝난다.

이스케이프 문자

문자열 안에 넣을 수 없는 글자를 사용하기 위해서 사용한다.

백슬래시(\) 다음에 문자열에 넣고 싶은 글자를 두는 방식으로 구성된다.

원시 문자열

문자열을 시작하는 따옴표 앞에 r을 사용하면 문자열을 원시 문자열로 만들 수 있다.

원시 문자열은 모든 이스케이프 문자를 완전히 무시하고 문자열에 나타나는 백슬래시를 인쇄한다.

세겹 따옴표를 사용하는 여러 줄에 걸친 문자열

문자열에 줄바꿈을 넣으려면 \n 이스케이프 문자를 사용할 수도 있지만 여러 줄 문자열을 사용하는 것이 더 편할 때가 많다. 파이썬에서 여러 줄 문자열은 세 개의 홑따옴표로 시작하고 끝난다.

여러 줄 주석

여러 줄 주석은 세 개의 겹따옴표로 시작하고 끝난다.

문자열 인덱스와 슬라이스

문자열은 리스트처럼 인덱스와 슬라이스를 사용한다.

문자열을 리스트로 생각하고 문자열의 각 글자는 인덱스에 상응하는 아이템으로 생각할 수 있다.

문자열에 in 또는 not in 연산자 사용하기

in 또는 not in 연산자는 리스트 값과 마찬가지로 문자열에서도 쓸 수 있다.

쓸모 있는 문자열 메소드

* 이 포스트는 "파이썬 프로그래밍으로 지루한 작업 자동화하기" 의 내용을 참조해서 작성하였습니다.

* 파이썬 3.3을 기준으로 작성하였습니다.

* 이 포스트는 "파이썬 프로그래밍으로 지루한 작업 자동화하기" 의 내용을 참조해서 작성하였습니다.

* 파이썬 3.3을 기준으로 작성하였습니다.

리스트 

- 순서를 가진 여러 가지 값의 배열

- [] (대괄호) 로 표기

- 쉼표를 구분자로 하여 리스트에 아이템들을 초기화 할 수 있음

- 아이템들의 타입이 달라도 상관 없음

>>> [1, 2, 3]

>>> ['a', 'b', 'c']

>>> [1, True, 'A', [1, 2, 3]]

인덱스를 이용해서 리스트의 개별 아이템 얻기

리스트 이름에 대괄호를 사용해서 0부터 시작하는 정수로 순차적인 접근이 가능하다.

>>> test = ['a', 'b', 'c']

>>> test[0]

'a'

>>> test[1]

'b'

>>> test[2]

'c'

리스트 값의 개수를 초과하는 인덱스를 사용하면 IndexError 오류가 발생한다.

인덱스는 정수값만 가능하며, 그 이외의 타입에는 TypeError 오류가 발생한다.

음수 인덱스도 사용이 가능하며, -1은 리스트의 마지막 값을 뜻하고, -2는 리스트의 끝에서 두 번째 값을 의미힌다.

부분 리스트

- 슬라이스를 이용해서 부분 리스트를 얻을 수 있다.

- 리스트 이름 [시작 인덱스 : 포함하지 않는 마지막 인덱스] 으로 정의 한다.

>>> test = ['a', 'b', 'c']

>>> test[0:3]

['a', 'b', 'c']

>>> test[0:2]

['a', 'b']

>>> test [1:3]

['b', 'c']

>>> test [0:-1]

['a', 'b', 'c']

콜론(:)을 기준으로 앞의 값을 비워두면 앞의 값은 0으로 처리된다.

콜론(:)을 기준으로 뒤의 값을 비워두면 뒤의 값은 리스트 길이 혹은 -1로 처리된다.

리스트 변경

인덱스를 지정해서 할당을 하면 값이 변경된다.

>>> test = [1, 2, 3]

>>> test[0] = 'a'

>>> test

['a', 2, 3]

리스트 병합

>>> [1, 2, 3] + ['a', 'b', 'c']

[1, 2, 3, 'a', 'b', 'c']

>>> ['a', 'b'] * 2

['a', 'b', 'a', 'b']

리스트 값 제거

del 명령어를 사용한다.

>>> test = [1, 2, 3]

>>> del test[1]

>>> test

[1, 3]

다중 할당

한 줄의 코드로 리스트 안에 있는 값을 여러 변수에 할당한다.

>>> test = [1, 2, 3]

>>> a, b, c = test

>>> a

1

>>> b

2

>>> c

3

리스트 메소드

메소드는 함수와 기능은 같지만 객체 내에 정의되어 있는 멤버 함수를 메소드라고 한다.

튜플 (tuple)

- 리스트와 비슷하지만 한 번 정의되면 변경이 불가능하다.

- () 로 표기

리스트와 튜플의 전환

list() 함수를 이용하면 튜플에서 리스트를 생성해 준다.

>>> list(('a', 'b', 'c'))

['a', 'b', 'c']

tuple() 함수를 이용하면 리스트에서 튜플을 생성해 준다.

>>> tuple([1, 2, 3])

(1, 2, 3)

참조 전달

정수형, 숫자형, 문자열 값을 매개 변수로 함수를 호출하는 경우, 해당 값은 파라미터 변수로 복사된다.

그 외의 타입을 매개 변수로 함수를 호출하면, 해당 타입의 참조가 파라미터로 전달된다. 

(참조 값은 복사되어도 같은 실제 값을 가리키게 된다.)

copy() vs deepcopy()

리스트 등의 데이터의 사본을 만들기 위해서는 copy 라이브러리에 있는 copy() 혹은 deepcopy() 명령어를 사용할 수 있다.

리스트의 모든 아이템이 정수형, 숫자형, 문자열 값으로만 되어 있다면 copy() 를 쓰는 것으로 충분하지만, 아이템에 다른 리스트나 튜플 등이 들어 있다면 deepcopy() 를 사용해야 제대로 사본이 생성된다. 

* 이 포스트는 "파이썬 프로그래밍으로 지루한 작업 자동화하기" 의 내용을 참조해서 작성하였습니다.

* 파이썬 3.3을 기준으로 작성하였습니다.

함수

파이썬에서는 여러 가지 내장 함수를 제공하지만, 필요한 함수를 직접 만들어 쓸 수도 있다.

함수를 사용하는 목적은, 코드의 묶음을 여러 차례 실행시키는 것이다. 함수를 사용하지 않으면 필요할 때마다 매번 코드를 복사해서 써야 하는데, 중복되는 부분이 많아지면, 코드의 가독성이 떨어지고, 디버깅도 어려워진다. 중복을 제거하면 프로그램은 짧아지고, 읽기 쉽고, 고치기 쉬워진다.

함수 정의 하기

def 구문을 이용해서 함수를 정의한다.

def hello():
    print ('Hello')

함수에 매개변수 추가하기

def hello(name):
    print ('Hello', name)

반환값과 return 문

def hello(name):
    return 'Hello ' + name

None 값

파이썬에는 None 이라는 값이 있다. 이는 값이 없음을 의미한다. 

키워드 매개변수와 print()

print() 함수에 다음과 같은 매개 변수 사용이 가능하다.

print ('Hello', end='')            # 출력 후 줄바꿈을 하지 않음
print ('a', 'b', 'c', sep=',')     # 출력시 구분자로 ',' 로 사용

지역 및 전역 범위

- 전역 범위의 코드는 지역 변수를 사용할 수 없다.

- 지역 범위는 전역 변수를 사용할 수 있다.

- 함수의 지역 범위 안에 있는 코드는 다름 지역 범위의 변수를 사용할 수 없다.

- 범위가 서로 다르다면 같은 이름의 지역 변수를 사용할 수 있다.

global 문

함수 안에서 전역 변수를 수정해야 하는 경우 사용

예외 처리

try: ~ except: 구문을 이용하여 예외를 처리한다.

def test(div):
    try:
        return 100 / div
    except ZeroDivisionError:
        print ('Error')

수학에서 에라토스테네스의 체는 소수를 찾는 방법입니다. 고대 그리스 수학자 에라토스테네스가 발견하였습니다.

방법은 다음과 같습니다.

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열합니다.

2. 2는 소수이므로 소수 리스트에 적어두고,

3. 자기 자신을 제외한 2의 배수를 모두 지웁니다.

4. 남아 있는 수 가운데 3은 소수 이므로 소수 리스트에 적어두고,

5. 자기 자신을 제외한 3의 배수를 모두 지웁니다.

6. 위의 과정을 반복하면 구하는 구간의 모든 소수를 찾을 수 있습니다.

다음은 파이썬을 이용한 예시이며, 소수인지를 체크할 수 있는 배열 정보와 소수 리스트를 리턴해 줍니다.

def findPrimes(n):
        tPrimes = [2]
        tArr = [True] * (n+1)
        tArr[0], tArr[1] = [False] * 2

        for i in xrange(4, n+1, 2):
                tArr[i] = False

#        for i in xrange(3, n+1, 2):
#                j = 3
#                while True:
#                        tmp = i * j
#                        if (tmp > n):
#                                break
#                        tArr[tmp] = False
#                        j += 2

        for i in xrange(3, int(n**0.5)+1, 2):
            if (tArr[i]):
                for j in xrange(i**2, n+1, 2*i):
                    tArr[j] = False

        for i in xrange(3, n+1, 2):
                if (tArr[i]):
                        tPrimes.append(i)

        return tArr, tPrimes