Special Effects FX 스스로를 감동시켜야 최선을 다 한 것이다.

순회의 세 가지 방법

이진 트리를 대상으로 하는 대표적인 순회의 세 가지 방법은 다음과 같다.

# 전위 순회(Preorder Traversal) : 루트 노드를 먼저 방문.

# 중위 순회(Inorder Traversal) : 루트 노드를 중간에 방문.

# 후위 순회(Postorder Traversal) : 루트 노드를 마지막에 방문.

이렇듯 이진 트리를 순회하는 대표적인 방법은 다음 내용을 기준으로 세 가지로 나뉜다.

즉, Root Node 를 언제 방문하느냐에 따라 달라진다.

Left -> Root -> Right

루트 노드는 중간에 방문이 이뤄지기 때문에 이러한 방식의 순회를 가리켜 '중위 순회' 라 한다.

Left -> Right -> Root

루트 노드는 마지막에 방문을 하게 되므로, 이러한 방식의 순회를 가리켜 '후위 순회' 라 한다.

Root -> Left -> Right

루트 노드는 첫 번째로 방문을 하게 되므로, 이러한 방식의 순회를 가리켜 '전위 순회' 라 한다.

루트 노드와 이를 부모로 하는 두 자식 노드를 놓고, 한쪽 방향으로 순서대로 방문을 하면 된다.

※ 이진 트리는 그 구조가 재귀적이다.

리눅스 분할 압축

ex) tar cvfz - /home/temp | split -b 100m - temp.tar.gz

- /home/temp : 압축할 디렉토리

- 100 : 분할 압축 단위 (100 Mega byte)

- temp.tar.gz 파일명

위와 같이 명령하면 아래와 같이 파일이 나뉘어 생성된다.

temp.tar.gzaa

temp.tar.gzab

temp.tar.gzac

리눅스 분할 압축된 것 해제

ex) cat temp.tar.gz* | tar xvfz -

cat temp.tar.gz* 은 파일 이름이 temp.tar.gz로 시작되는 파일을 합쳐서 콘솔로 출력하는 명령이다.

tar xvfz - 는 콘솔로부터 받은 파일의 압축 해제하는 명령이다. 

※ 명령행에서 - 는 표준 입출력(화면, 키보드) 를 의미한다.

트리의 개요

트리는 계층적 관계(Hierarchical Realationship) 를 표현하는 자료구조이다.

트리는 가지를 늘려가며 뻗어나가는 자료구조이다.

※ 자료구조는 무엇인가를 '표현'하는 도구이다. 표현을 위해서 저장과 삭제라는 기능이 제공되는 것으로 이해하는 것이 옳다.

트리가 표현할 수 있는 것들

컴퓨터의 디렉토리 구조, 집안의 족보나 기업 및 정부의 조직도 등등

트리 관련 용어

노드:  node

- 트리의 구성요소에 해당하는 요소

간선: edge

- 노드와 노드를 연결하는 연결선

루트 노드: root node

- 트리 구조에서 최상위에 존재하는 노드

단말 노드: terminal node

- 아래로 또 다른 노드가 연결되어 있지 않은 노드

내부 노드: internal node

- 단말 노드를 제외한 모든 노드

참고로 '단말 노드'는 나무의 구조상 잎에 해당한다 하여 '잎사귀 노드(leaf node)' 라고도 불리며, '내부 노드'는 단말 노드가 아니라 하여 '비단말 노드(non-internal node)' 라 불린다.

그리고 노드간에는 부모(parent), 자식(child), 형제(sibling)의 관계가 성립이 된다. 

# 노드 A는 노드 B, C, D의 부모 노드이다.

# 노드 B, C, D는 노드 A의 자식 노드이다.

# 노드 B, C, D는 부모 노드가 같으므로, 서로가 서로에게 형제 노드이다.

그런데 부모와 자식의 관계는 상대적이다. 따라서 노드 B는 노드 A의 자식 노드이지만, 동시에 노드 E와 F의 부모 노드도 된다.

조금 더 나아가서 조상(Ancestor), 후손(Descendant)의 관계도 있다. 특정 노드의 위의 위치한 모든 노드를 가리켜 '조상 노드' 라 하고, 특정 노드의 아래에 위치한 모든 노드를 가리켜 '후손 노드' 라 한다. 

즉 노드 A와 B는 노드 E의 조상 노드이다. 반면 노드 B, C, D, E, F는 모두 노드 A의 후손 노드이다.

이진 트리(Binary Tree)와 서브 트리(Sub Tree)

서브 트리: 큰 트리에 속하는 작은 트리를 가리켜 '서브 트리(sub tree)' 라 한다.

이진 트리: 이진 트리는 다음 두 조건을 만족해야 한다.

1) 루트 노드를 중심으로 두 개의 서브 트리로 나뉘어진다.

2) 나위어진 두 서브 트리도 모두 이진 트리이어야 한다.

※ 이진 트리의 조건 자체가 재귀적이다.

이진트리가 되려면, 루트 노드를 중심으로 둘로 나뉘는 두 개의 서브 트리도 이진 트리이어야 하고, 그 서브 트리의 모든 서브 트리도 이진 트리이어야 한다.

공집합(empty set)

노드가 위치할 수 있는 곳에 노드가 존재하지 않는다면, 공집합(empty set) 노드가 존재하는 것으로 간주한다. 물론 공집합 노드도 이진 트리의 판단에 있어서 노드로 인정한다.

포화 이진 트리(Full Binary Tree)와 완전 이진 트리(Complete Binary Tree)

레벨(level): 트리에서는 각 층별로 숫자를 매겨서 리르 트리의 '레벨'이라 한다.

높이(height): 트리의 최고 레벨을 가리켜 '높이'라 한다.

포화 이진 트리: 모든 레벨이 꽉 찬 이진 트리를 가리켜 '포화 이진 트리'라 한다.

완전 이진 트리: 포화 이진 트리처럼 모든 레벨이 꽉 찬 상태는 아니지만, 차곡차곡 빈 큼 없이 노드가 채워진 이진 트리를 뜻한다. 

즉, 노드가 위에서 아래로, 그리고 외쪽에서 오른쪽으로 순서대로 채워진 트리를 말한다.

bisect : 리스트를 정렬된 상태로 유지

     목적: 리스트에 아이템이 추가될 때마다 정렬 함수를 호출하지 않고 리스트를 정렬된 상태로 유지

bisect 모듈은 리스트가 정렬된 상태를 유지하면서 아이템을 넣을 수 있게 구현돼있다. 

커다란 리스트에 아이템이 들어올 때마다 반복적으로 정렬하는 것보다 이 방식이 더 효율적일 수 있다.

정렬된 상태로 아이템 추가

insort() 를 사용해 리스트가 정렬된 상태를 유지하면서 아이템을 추가하는 예제

결과

위의 예제는 매우 간단하고 리스트의 크기도 작기 때문에 리스트를 생성한 후에 정렬하는 방식이 더 빠를 것이다. 하지만 리스트의 길이가 매우 길어지면 위와 같은 방식을 사용하는 편이 시간과 메모리 낭비를 비약적으로 줄여줄 수 있다.

multiprocessing : 프로세스를 스레드처럼 관리

목적: 프로세스 관리를 위한 API 제공

버전: 파이썬 2.6 이상

multiprocessing 모듈은 threading API에 기반을 두고 여러 프로세스 간 작업을 나누는 API를 제공한다.

multiprocessing은 threading 대신 사용해 멀티 코어 CPU의 장점을 누리고 파이썬의 글로벌 인터프리터 락(GIL) 의 병목현상을 피하게 할 수 있다.

multiprocessing 모듈은 threading 모듈과 비슷한 API를 가지고 있는 process 기반의 병렬처리 알고리즘이다 python은 Global Interpreter Lock 을 이용하여 병행처리 과정에서 발생할 수 있는 문제를 방지한다. GIL 은 간단한 구현 때문에 계속 사용되어 있지만, CPU 하나만을 사용하는 것을 가정하였기 때문에 현재 처럼 CPU 안에 코어가 여러개 있다고 하더라도, 실제로 병렬처리 되지 않고 한번의 하나의 thread 밖에 처리하지 않는다. 

multiprocessing 모듈은 이러한 문제를 회피하기 위해 process 기반으로 병렬처리를 지원하는 모듈이다

멀티프로세싱 기본

두 번째 프로세스를 생성하기 가장 쉬운 방법은 Process 객체를 인스턴스화하며, 목표 함수를 전달하고 start를 호출하는 것이다.

결과

단어worker가 다섯 번 출력되지만, 각 프로세스가 출력 스트림에 접근하기 위해 경쟁하기 때문에 실행 순서에 따라 결과물이 완전히 깨끗하지 않을 수 있다.

대부분 프로세스를 생성할 때 어떤 작업을 수행해야하는지 인자에 명시하는 편이 더 유용하다. threading 과는 다르게 multiprocessing Process에 인자를 저너달하려면 인자는 pickle을 사용해 직렬화할 수 있어야 한다. 

이 예제는 각 워커 프로세스에 출력할 숫자를 전달한다.

결과

임포트 가능한 목표 함수

threading과 multiprocessing 의 차이점 중 하나는 multoprocessing이 사용하는 __main__에 보호 장치가 더 있다는 점이다. 

새로운 프로세스가 생성되는 방식 때문에 자식 프로세스는 목표 함수를 포함하는 스크립트를 임포트할 수 있어야 한다. 애플리케이션의 메인을 감싸서 모듈이 임포트돼도 각 자식 프로세스에서 __main__ 이 재귀적으로 호출되지 않을음 확인해야 한다.

혹은 또 다른 스크립트에서 목표 함수를 임포하는 방식도 있다. 

예를 들어 mutiprocessing_import_main.py는 두 번째 모듈에서 정의한 워커 함수를 사용한다.

현재 프로세스 판별

인자를 사용해 프로세스를 구별하거나 이름을 붙이는 방식은 번거롭고 필요치도 않다. 각 Process 인스턴스는 기본 값으로 이름이 있고 생성될 때 변경할 수 있다.

프로세스에 이름을 붙이면 추적하기 쉬워지고, 여러 프로세스가 동시에 실행되는 애플리케이션에서 특히 유용하다.

결과

디버그 출력의 각 줄마다 현재 프로세스의 이름이 포함돼 있다. Process-3 이 붙어있는 줄은 이름이 없는 프로세스 worker_1에 대응한다.

데몬 프로세스

메인 프로그램은 기본적으로 모든 자식이 종료될 때까지 끝나지 않는다. 하지만 프로세스를 간섭하기 쉬운 방법이 없는 서비스나, 작업 도중에 죽어도 데이터를 잃거나 훼손하지 않는 프로그램의 경우엔 메인 프로그램이 종료되는 것을 막지 않고 백그라운드에서 실행되는 프로세스가 필요하기도 하다.

프로세스를 데몬으로 지정하려면 daemon 속성을 True로 설정한다. 기본 값은 데몬이 되지 않게 설정돼 있다.

결과

프로그램을 실행하면 데몬 프로세스에게 'Exiting' 메시지가 출력되지 않는데, 이는 데몬 프로세스가 2초간 잠들었다ㅏ 깨어나기 전에 모든 넌데몬 non-daemon 프로세스(메인 프로그램 포함) 가 종료되기 때문이다.

데몬 프로세스는 메인 프로그램이 끝나기 전에 자동으로 종료돼 고아가 되는 것을 방지한다. 

데몬 프로세스가 남아있지 않은지는 실행 중인 프로세스 아이디를 화면에 출력하는 ps 같은 명령어로 확인 할 수 있다.

프로세스간 객체 전달

multiprocessing 은 프로세스간에 객체를 전달하기 위한 두가지 방법을 제공한다.

Queue

Queue 클래스는 Queue.Queue 와 비슷하다.

Queue는 안전하게 thread와 process에서 처리 가능하다.

프로세스 각각의 ID를 보여주는 예제

결과

과

파이썬은 1.5버전부터 re 모듈을 통해 정규 표현식을 지원한다. 

파이썬에 지원하는 정규 표현식은 펄을 대상으로 삼지만, 다음 사항들은 조심해야 한다.

# 조건 달기는 지원하지 않는다.

# \E, \1, \L, \u, \U 를 통한 대소문자 변환은 지원하지 않는다.

# \z 는 지원하지 않는다.

파이썬은 보통 re 모듈에서 정규 표현식을 컴파일 하면 RegexObject 객체를 반환한다. 

이 객체의 match() 메소드나 search() 메소드에 찾고자 하는 문자열을 넘겨주면 다시 MatchObject 객체를 반환하는데, 이 객체에 일치한 텍스트 정보가 포함되어 있다.

RegexObject 객체와 MatchObject 객체에는 다음과 같은 메서드들이 있다.

* match() - 문자열의 시작 부분에서 정규 표현식과 일치하는지 검사한다.

* search() - 문자열의 전체를 훑어서 정규 표현식과 일치하는 부분이 있는지 검사한다.

* findall() - 정규 표현식과 일치한 텍스트를 모두 찾아 리스트 형태로 반환한다.

* finditer() - 정규 표현식과 일치한 텍스트를 모두 찾아 열거자 형태로 반환한다.

* group() - 정규 표현식과 일치한 텍스트를 반환한다.

* start() - 정규 표현식과 일치한 텍스트의 시작 위치를 반환한다.

* end() - 정규 표현식과 일치한 텍스트의 마지막 위치를 반환한다.

* span() - 정규 표현식과 일치한 텍스트의 시작 위치와 마지막 위치를 튜플(tuple) 형태로 반환한다.

※ match() 메소드는 시작 부분부터 찾으므로, 일치에 성공했을 때 시작 위치는 항상 0인 반면, search() 메소드는 문자열 전체를 훑으며 찾기 때문에, 시작 위치가 일정하지 않다는 점을 기억해야 한다.

TIP

정규 표현식을 컴파일하지 않고 re 모듈의 메소드에 직접 정규 표현식을 전달해 원하는 결과를 얻을 수 있다. 이는 match(), search(), findall(), finditer() 메소드에 모두 적용할 수 있다.

정규 표현식에서 역슬래시(\)를 일치시키려면 문자 그대로 일치하도록 역슬래시 문자를 이스케이프 해야 한다. 하지만 파이썬에서도 역슬래시가 특별한 의미를 지니고 있기 때문에, 정규 표현식에 역슬래시를 문자 그대로 전달하려면 역슬래시를 이스케이프 하고 이 두 역슬래시에 각각 다시 한번 역슬래시를 추카해야 한다.

즉, 역실래시 문자를 일치시키기 위해서는 정규 표현식 문자열을 \\\\로 표현해야 한다.

이 문제를 해결하려면 파이썬에서 제공하는 raw 문자열을 사용하면 된다. 문자열 앞에 알파벳 r을 붙이는 형식으로 위와 같은 상황에서 정규 표현식 문자열을 r'\\' 와 같이 표현한다.

위치 지정

패턴의 수를 지정하는 것뿐만 아니라 입력된 텍스트에서 패턴이 어느 곳에 위치하는지 지정해줄 수도 있다.

정규 표현식 앵커 부호

결과 값

예제에서 문자열의 시작부분에 위치한 단어를 찾는 방법과 문자열이 끝나는 부분에 위치한 단어를 찾는 방법이 다르다. 그 이유는 문자열의 마지막에 있는 punctuation 이란 단어의 뒤에 마침표가 붙어있기 때문이다. 단순히 \w+$ 패턴을 사용하면 이 단어를 찾아 낼 수 없다. 마침표는 \w 가 의미하는 '숫자나 문자' 범주에 포함되지 않기 때문이다.

패턴에 플래그 넣기

패턴을 라이브러리 함수에 인자로 넘긴다거나 할 때는 표현식에 플래그를 더할 수 없다. 이런 경우에는 표현식 자체에 플래그를 끼워 넣는 방식을 사용한다. 

예를 들어 대소문자를 구별하지 않는 플래그를 켜기 위해선 표현식 앞에 (?i) 를 더한다. 

전체 표현식이 평가되거나 파싱되는 방식을 옵션이 조절하기 때문에 이 옵션은 표현식 앞에 와야 한다.

플래그는 같은 그룹에 조합해서 사용할 수 있다. 예를 들어 (?imu) 는 다중 라인, 유니코드, 대소문자 무시 플래그를 동시에 켠다.

탐욕적 수량자(Greedy Quantifier) & 게으른 수량자(Lazy Quantifier)

과하게 일치하는 상황 방지하기

RegEx: /<[Bb]>.*<\/[Bb]>

원하는 텍스트를 포함하긴 하지만, 찾으려 하지 않은 텍스트도 포함됐다. 그 이유는, 바로 별표(*)와 더하기(+) 같은 메타 문자가 탐욕적(greedy)이기 때문이다.

이는 가능한 한 가장 큰 덩어리를 찾으려 한다는 뜻이다. 이런 메타 문자는 찾으려는 텍스트를 앞에서부터 찾는 게 아니라, 텍스트 마지막에서 시작해서 거꾸로 찾는다. 의도적으로 수량자(quantifier)를 탐욕적으로 설계했기 때문이다.

하지만 만약 탐욕적 일치를 원하지 않는다면 어떻게 해야 할까? 

탐욕적 수량자를 게으른(lazy) 수량자로 바꾸면 된다. '게으른' 이라고 부르는 이유는 문자가 최소로 일치하기 때문이다. 게으른 수량자는 가존 수량자 뒤에 물음표(?) 를 붙여서 표현한다.

탐욕적 수량자에는 모두 각각 대응되는 게으른 수량자가 있다.

탐욕적 수량자와 게으른 수량자

게으른 수량자를 이용

RegEx: /<[Bb]>.*?<\/[Bb]>

게으른 수량자인 *? 를 사용해 먼저 AK만 일치시켰고, 뒤이어 나머지도 찾아 두 부분을 따로 일치시켰다.