컴언

파이썬 객체를 파일로 저장하는 방법 - Serialization (직렬화)

공부/Python

파이썬 객체(Object)를 파일로 출력해서 필요할 때 마다 불러와 쓸 수 있는 방법을 소개한다. 진짜 간단함!


용어 정리: 직렬화와 역직렬화

쉽게 설명하면

직렬화 (Serialization) : 객체를 파일로 내보냄
역직렬화 (Deserialization) : 파일로 내보낸 객체를 다시 읽어들임


파이썬에서는 어떻게?

pickle 이라는 파이썬 표준 라이브러리를 사용하면 된다.


1. 직렬화 (파이썬에서는 pickling 이라고 주로 부른다.)

pickle.dump(내보낼 객체, 파일)



2. 역직렬화 (파이썬에서는 unpickling 이라고 주로 부른다.)

pickle.load(파일)



파이썬에서 Trie (트라이) 구현하기

자료구조

들어가며: "자동 완성" 기능에 대한 이야기


구글에서 어떤 단어를 검색창에 치면 그 단어로 시작하는 다른 키워드를 보여주는데요, 이런 걸 자동 완성(Autocomplete) 라고 합니다. 자동 완성을 구현 하려면 키워드들을 리스트에 담아서, 유저 인풋이 들어올 때 마다 인풋으로 시작하는 키워드를 리스트에서 빼오면 될 겁니다. 하지만, 만약 550만 개의 글을 갖고 있는 영어 위키백과의 제목들을 가지고 자동 완성을 구현하라고 한다면  (실제 일본 모 회사의 올해 인턴 모집 스크리닝 과제였음 ㅋㅋ) 리스트 따위로는 안 되고, 훨씬 더 효율적인 자료구조가 필요합니다. 오늘 배울 Trie 가 이럴 때 필요한 자료구조입니다.



Trie: 트라이? 트리? 기본적인 개념

우선 이름이 좀 특이한데요, Trie는 컴퓨터에서 검색을 뜻하는 retrieval 에서 온 단어라고 합니다. Prefix tree 라고도 하는데 직관적이고 부르기도 쉬워서 이렇게 부르는 사람도 꽤 있습니다. 아무튼 Retrieval 에서 왔으니 트리라고 불러야 하지 않냐!! 라고 하실 수도 있지만... 트리(Tree)와 혼동을 피하기 위해서 대부분은 그냥 트라이라고 부릅니다. 이런 논란에 휘말리기 싫어서 이 글에서는 Trie 라는 영어 명칭을 쓰기로 하겠습니다 큭큭

사실 Trie 는 트리(Tree) 자료 구조의 일종입니다. 미리 말씀드리자면 Trie 에서 어떤 문자열을 검색할 때의 시간 복잡도는 O(m) 밖에 안 됩니다. (m: 문자열의 최대 길이) 그래서 다른 자료 구조에 비해 문자열을 검색하는 데 특화된 자료 구조임을  알 수 있습니다. 


위 그림은 names = ['Joe', 'John', 'Johnny', 'Jane', 'Jack'] 을 Trie 에 삽입한 결과인데요.


각 Node 는 

(1) 글자를 갖는 key = 한 글자 (ex. J, A, C, K)

(2) 단어의 마지막 글자인지를 알려주는 flag (Terminal)

로 이루어져 있습니다. 


예를 들어 John 의 경우 J > O > H > N 으로 차례대로 Trie 에 삽입이 되었고 마지막 글자 N 의 노드에는 Terminal 이라는 flag 를 박아줍니다. 이 flag 때문에 John 이 한 단어임을 알 수 있습니다. 

Johnny 의 경우 John 까지는 이미 노드가 있으니 ( J > O > H > N )원래 있는 노드를 활용하고, John 뒤에 ny를 넣은 다음 y를 마지막 글자로 flag해주면 되는 겁니다.


파이썬에서 Trie 를 구현해볼까요?

첫번째. Node 구현



1. key 필드는 단어의 글자 하나를 담는 데 이용합니다. 영어라면 알파벳만 들어갈 수 있겠죠.

2. data 필드는 사실상 마지막 글자를 나타내주는 flag 입니다. 원래 boolean 형 으로 간단하게 true/false 로 구분할 수도 있지만

저는 마지막 글자인 경우에  단어 전체를 data 필드에 저장하고, 아닌 경우에는 그냥 널로 두려고 합니다. 그 이유는 밑에 구현할 starts_with 메소드 때문인데요, 곧 설명 드리겠습니다.

(즉, Jack 의 경우 J > A > C > K 에서 마지막 글자인 K 노드의 data 필드에만 "Jack" 이 들어가고, 그 외 노드의 data 필드는 널 (None) 으로 놔둡니다.)


두번째. Trie 구현

1. insert(string)

트라이에 문자열 삽입

2. search(string)

주어진 단어 string이 트라이에 존재하는지 여부 반환

3. starts_with(prefix)

주어진 prefix 로 시작하는 단어들을 BFS로 트라이에서 찾아 리스트 형태로 반환

마지막 글자 flag 를 boolean 으로 안하고 data 필드로 한 이유가 바로 이 메소드 때문인데요... 잘 생각해보세요. BFS 로 단어들을 찾을 때 결국 마지막에 우리에게 반환되는 것은 Terminal 노드, 즉 마지막 글자입니다. 그래서 단어 자체를 알려면 BFS 경로를 역추적해야 합니다... 이 과정이 귀찮기 때문에 ㅋㅋ Terminal 노드만 찾으면 BFS 역추적 할 필요 없이 단어가 뭔지 알 수 있도록 data 필드에 전체 단어를 넣어 놓은 것이죠.


위 세 가지만 구현하면 됩니다! 아래는 제가 간단히 파이썬으로 구현해본 Trie 입니다.

(파이썬 전체 코드는 여기를 클릭하면 보실 수 있습니다.)


끝!!

학교 자료구조 수업에서는 비중이 많이 있는 놈은 아니지만, 기술 면접이나 코딩 대회에서 많이 다루어진다고 하니 열심히 공부합시다!! 우리의 핵심 목표는 Trie다 하는 것으로 정신을 차리고 나아가면 취직할 수 있는 에너지가 분산되어 우주가 나서서 도와준다는 그런 마음을 가질 수 있을거다, 그렇게 생각합니다.

[언어 모델링] n-gram

Natural Language Processing

자연어 처리에서 확률의 중요성


우리가 자연어로 만들어내는 문장들은 정규화되지 않고 무한하며 복잡한 문법을 따르기 때문에 컴퓨터가 처리하기 어렵습니다. 하지만 효과적인 언어 모델링을 이용하면 분석이 한결 더 쉬워질 수 있습니다. 예를 들어 음성 인식의 경우를 생각해 봅시다.


"It's hard to recognize a speech."


와 


"It's hard to wreck a nice beach."


라는 두 문장이 있습니다. 발음해보시면 알겠지만, 둘은 서로 거의 비슷한 음성적 특성을 가지는 문장입니다. 하지만 두 번째 문장처럼 일어나기 힘든(단어들이 조합되기 힘든) 말이 주어질 확률은 낮습니다. 따라서 확률적으로 훨씬 빈도/가능성이 제일 높은 첫 번째 문장으로 인식하죠. 한국어에서도 사이시옷 같은 괴랄한 맞춤법 규칙, 띄어쓰기, 발음 변동 현상과 같은 문제를 해결하는 데 언어 모델링이 엄청 중요하다고 생각합니다.



비슷하게, "피아노를" 이라는 어절을 주면 다음에 "치다" 같은 단어가 올 것이라고 예상할 수 있습니다. 이런 생각에서 다양한 확률론적 모델이 고안되었고 오늘 다룰 n-gram 이 그런 확률적 분석 방법의 하나입니다. 


n-gram

 


n-gram 은 n개 어절/음절을 연쇄적으로 분류해 그 빈도를 따집니다. n=1 일 때는 unigram, 2일 때는 bigram, 3 - trigram 식으로 불리는데 분석 예제를 보면 무슨 뜻인지 감이 오실겁니다.


"쓸쓸하던 그 골목" 음절 단에서 bigram 으로 분석한 결과


['쓸', '쓸'], ['쓸', '하'], ['하', '던'], ['던', ' '], [' ', '그'], ['그', ' '], [' ', '골'], ['골', '목']

"쓸쓸하던 그 골목을 당신은 기억하십니까" 을 단에서 trigram 으로 분석한 결과

[['쓸쓸하던', '그', '골목을'], ['그', '골목을', '당신은'], ['골목을', '당신은', '기억하십니까'], ['당신은', '기억하십니까', ' '], ['기억하십니까', ' ', ' ']]



그리고 긴 텍스트를 분석하게 된다면 같은 n-gram 이 여러개 나오게 될 겁니다. 그 n-gram 들의 수를 세서 리스트로 만든 것을 빈도 리스트 (frequency list) 라고 합니다. 저는 이상의 소설에서 가장 많이 나온 n-gram 이 뭘까 궁금해서 이상의 날개를 이용해 Python으로 n-gram 분석을 해봤습니다. 아래를 보시죠.

Python 구현



#!/usr/bin/env python3
# -*- coding:utf-8 -*-]

with open('nalgae.txt', 'r', encoding='utf-8', newline='\n') as f:
	file = f.read()
sample_file = ''.join(file) 

#어절 n-gram 분석
#sentence: 분석할 문장, num_gram: n-gram 단위
def word_ngram(sentence, num_gram):
	# in the case a file is given, remove escape characters
	sentence = sentence.replace('\n', ' ').replace('\r', ' ')
	text = tuple(sentence.split(' '))
	ngrams = [text[x:x+num_gram] for x in range(0, len(text))]
	return tuple(ngrams)

#음절 n-gram 분석
#sentence: 분석할 문장, num_gram: n-gram 단위
def phoneme_ngram(sentence, num_gram):
	text = tuple(sentence) # split the sentence into an array of characters
	ngrams = [text[x:x+num_gram] for x in range(0, len(text))]
	return ngrams

#n-gram 빈도 리스트 생성
def make_freqlist(ngrams):
	freqlist = {}

	for ngram in ngrams:
		if (ngram in freqlist):
			freqlist[ngram] += 1
		else:
			freqlist[ngram] = 1
	
	return freqlist

ngrams = word_ngram(sample_file, 3)
freqlist = make_freqlist(ngrams)
sorted_freqlist = sorted(freqlist.items(), key=operator.itemgetter(1))
print(sorted_freqlist)


 


빈도 리스트는 길어서 상위 4개 trigram 만 적습니다.

날개의 본문은 저작권이 만료되었으므로 한국저작권위원회 공유마당에서 내려받으실 수 있습니다.

(('것', '같았다.', '나는'), 3), (('돈을', '놓고', '가는'), 3), (('그', '돈', '오'), 4), (('알', '수', '없다.'), 4)]

날개의 n-gram 분석 결과도 흥미롭네요 ㅎㅎ


추가>> bigram 분석 결과 시 다음과 같이 나왔습니다. 

(('다.', '나는'), 6), (('돈을', '놓고'), 6), (('내', '방'), 6), (('놓고', '가는'), 6), (('아내', '방으로'), 6), (('견딜', '수가'), 6), (('이불', '속에서'), 6), (('수', '있는'), 6), (('않았다.', '나는'), 6), (('', '나는'), 6), (('한', '번'), 6), (('나는', '그'), 7), (('내', '방으로'), 7), (('나는', '이'), 8), (('나는', '또'), 12), (('것이다.', '나는'), 12), (('나는', '내'), 12)]




여담: Google Books Ngram Viewer



Google Ngram Viewer (링크: https://books.google.com/ngrams) 은 구글이 구축한 말뭉치에서 연도별로 검색된 n-gram 을 검색해서 보여줍니다. 빅데이터 텍스트 마이닝 분야뿐 만 아니라 요새는 인문학 연구, 마케팅에도 자주 쓰인다고 하네요. 상당히 흥미로운 통계도 찾을 수 있으니 직접 해보시기 바랍니다.



참고자료


  1. Zhu, Xiaojin. "Language Modeling." CS769: Advanced Natural Language Processing (2010): n. pag. Web.
  2. 심광섭. "품사 태깅 말뭉치에서 추출한 n-gram을 이용한 음절 단위의 한국어 형태소 분석." 정보과학회논문지 : 소프트웨어 및 응용, 40.12 (2013): 869-876. Print.


[알고리즘] 너비 우선 탐색(Breadth First Search)과 구현 방법

자료구조

이 글에서는 트리나 그래프를 순회(traverse)/탐색(search)하는 알고리즘 중에 하나인 너비 우선 탐색 (Breadth First Search, BFS) 에 대해 다룹니다. 깊이 우선 탐색에 대해서는 아래 글을 참고해주세요 


2016/07/05 - [자료구조] - [알고리즘] 깊이 우선 탐색(Depth First Search)과 구현 방법


그래프 탐색의 필요성 이미 DFS 에 대한 제 글을 읽으셨다면 그래프 탐색의 필요성을 넘어가시면 됩니다. ^ㅍ^


 

사진 출처: http://pages.cs.wisc.edu/~paton/readings/Graphs/


그래프 자료구조라고 하면 어떤 것이 생각나시나요? 위와 같이 아기자기한 그림인가요? 


하지만 아래를 보면 어떠신가요?


자료 구조 설명하다가 무슨 삼성 그룹의 순환 출자에 대한 그림을 가져왔냐고 화를 내실지도 모르겠습니다만 꼭짓점(vertex)이 수없이 많은 그래프라고 생각해보세요. 이 모든 꼭짓점을 빠짐없이 방문하려면 어떻게 해야할까요? 선형구조인 단순한 리스트(List) 였다면 리스트의 총 원소 개수 N을 구해서 0~ N 까지 위치의 원소를 출력하면 탐색 완료지만, 그래프에서는 노드에 순서대로 번호가 있는 것도 아니고 하기 때문에 모든 원소에 대한 탐색이 어려운 것입니다. 이 난관을 극복하기위해 DFS 같은 알고리즘이 필요한 것이죠.


기본 원리

아래 두 사진 출처: CS188: Artificial Intelligence, UC Berkeley (강의 슬라이드)





위에 그림처럼 산과 그 속에 묻힌 보석을 찾아야하는 로봇이 있습니다. 로봇은 보석을 찾기 위해 첫번째 그림처럼 한없이 밑으로 내려가볼 수도 있고, 두번째 그림처럼 정상부터 점점 내려오면서 높이 별로 찾아볼 수도 있을겁니다. 전자와 같은 방식을 깊이 우선 탐색이라고 하고요, 후자가 오늘 설명할 너비 우선 탐색 (Breadth First Search, BFS) 라고 합니다. 둘은 산 속에 숨겨진 보석을 찾는다는 목표는 같지만, 그 찾는 순서가 다릅니다. 


산이 2000m 라고 할 때, BFS는 2000m -> 1900m 훑고 -> 1800m 훑고 -> ... -> 100m ~ 0m 까지 훑어서 탐색하는 것이죠. 좀 더 정의에 관련해서 설명하자면, 시작점 (2000m) 에서 같은 거리에 있는 원소들을 다 훑어야만 그 거리보다 더 먼 곳 (1900m~0m) 으로 차례차례 진격할 수 있는 것입니다.



가족 관계를 예로 들어 설명해보겠습니다. 자 오늘은 추석입니다~ 우리 민족의 대명절 추석에 아차! 일이 생겨 가족 모임에 가지 못하게 됐습니다. 저는 가족 관계를 원만하게 하는 것을 미덕으로 생각하는 사람이라서 8촌 이내의 모든 가족에게 빠짐 없이 연락하고 싶습니다. BFS 의 방식으로 연락을 한다면 어떻게 되는걸까요? 먼저 1촌인 부모님과 자녀에게 연락을 합니다. 그다음에 2촌인 가족들에게 연락을 돌리고요, 계속해서 3, 4, ... 8촌 까지 연락을 하면 모든 가족에게 빠짐없이 연락한 것이 됩니다. 이러한 순서로 그래프를 탐색하는 것이 BFS 입니다.



귀여운 그림을 사용해서 설명을 해봤는데 실제 그래프를 통해 BFS 가 어떻게 이루어지는지 아래에서 살펴봅시다.



BFS의 방문 순서

사진 출처: https://en.wikipedia.org/wiki/Breadth-first_search


맨 위를 첫 번째 단(Tier 1)이라고 하고 그 뒤로 두 번째 단, ... 이어진다고 합시다. 먼저 첫번째 단의 원소인 1 을 찍고 갑니다 (방문visit합니다). 그 다음 두번째 단에는 원소들을 전부 찍고, 세번째 단도 전부 찍고,... 단(Tier) 별로 방문하는 것을 볼 수 있습니다. 각 노드 안의 숫자는 방문 순서를 나타냅니다.



파이썬으로 구현하기

이제 BFS 를 실제 코드로 구현해보도록 합시다. BFS 에서 중요한 요소는 바로 큐 (Queue) 자료 구조입니다. 


좀 흥미로운 그래프를 가져왔습니다. 우리나라 정부 청사들이 다 세종시로 옮겨가는 중인데요, 세종시에서 BFS 를 통해 우리나라의 주요 장소를 (평양까지...!!ㅋㅋㅋ) 순회해보겠습니다.


순회 과정을 아래에 차근 차근 표현해 놓았으니, 아래 그래프를 새 창에 열어놓고 과정을 천천히 따라가보세요.



1. 먼저 Queue 에 시작점인 세종시를 넣습니다. 


그 다음, 큐의 맨 앞에 있는 세종을 불러서Queue.dequeue() 방문visit합니다. 세종시에 이어진 서울, 강릉, 대구, 광주을 큐에 줄세웁니다Queue.enqueue(세종의 자손 노드들) . 


>> 큐의 뒤

IN 

(enqueue)

  

 광주

대구

강릉

울 

세종 (Visit)

 >> 큐의 앞

OUT

(dequeue)

방문한 곳: {세종, }


2. 큐의 맨 앞에 있는 서울을 큐에서 내보내고 방문합니다. 서울시에 이어진 평양, 인천을 큐에 줄세웁니다Queue.enqueue(서울의 자손 노드들) . 단, 세종은 이미 방문했으므로 제외합니다.


>> 큐의 뒤

IN 

 

 

인천 

 

광주

대구

강릉

서울 (Visit)

 >> 큐의 앞

OUT

방문한 곳: {세종, 서울, }


3. 큐의 맨 앞에 있는 강릉을 큐에서 내보내고 방문합니다. 강릉시에 이어진 독도를 큐에 줄세웁니다Queue.enqueue(강릉의 자손 노드들) . 단, 세종은 이미 방문했으므로 제외합니다.


>> 큐의 뒤

IN 

 

독도 

 인천

평양

광주

대구

강릉 (Visit)

 >> 큐의 앞

OUT

방문한 곳: {세종, 서울, 강릉, }


4. 큐의 맨 앞에 있는 대구를 큐에서 내보내고 방문합니다. 대구시에 이어진 울산을 큐에 줄세웁니다Queue.enqueue(대구의 자손 노드들) . 단, 세종은 이미 방문했으므로 제외합니다.


>> 큐의 뒤

IN  

 

 울산

독도 

 인천

평양

광주

대구 (Visit)

 >> 큐의 앞

OUT

방문한 곳: {세종, 서울, 강릉, 대구, }


5. 큐의 맨 앞에 있는 광주를 큐에서 내보내고 방문합니다. 광주시에 이어진 여수를 큐에 줄세웁니다Queue.enqueue(광주의 자손 노드들) . 단, 세종은 이미 방문했으므로 제외합니다.


>> 큐의 뒤

IN  

 

여수

 울산

독도 

 인천

평양

광주 (Visit)

 >> 큐의 앞

OUT

방문한 곳: {세종, 서울, 강릉, 대구, 광주, }


6. 큐의 맨 앞에 있는 평양을 큐에서 내보내고 방문합니다. 평양시에 이어진 서울은 이미 방문했네요. Queue.dequeue()  하고 평양 visit만 한 채로 다음 단계로 갑니다.


>> 큐의 뒤

IN  

 

 

 여수

 울산

독도 

 인천

평양 (Visit)

 >> 큐의 앞

OUT

방문한 곳: {세종, 서울, 강릉, 대구, 광주, 평양, }


7. 큐의 맨 앞에 있는 인천을 큐에서 내보내고 방문합니다. 인천시에 이어진 서울은 이미 방문했네요. Queue.dequeue()  하고 인천 visit만 한 채로 다음 단계로 갑니다.


>> 큐의 뒤

IN  

  

 

 여수

 울산

독도 

인천 (Visit)

 >> 큐의 앞

OUT

방문한 곳: {세종, 서울, 강릉, 대구, 광주, 평양, 인천, }


8. 큐의 맨 앞에 있는 독도을 불러서 방문합니다. 독도에 이어진 강릉은 이미 방문했네요. Queue.dequeue()  하고 독도 visit만 한 채로 다음 단계로 갑니다.


>> 큐의 뒤

IN  

   

 

 여수

 울산

독도 (Visit)

 >> 큐의 앞

OUT

방문한 곳: {세종, 서울, 강릉, 대구, 광주, 평양, 인천, 독도, }



9. 큐의 맨 앞에 있는 울산을 큐에서 내보내고 방문합니다. 울산시에 이어진 부산을 큐에 줄세웁니다Queue.enqueue(울산의 자손 노드들) . 단, 대구는 이미 방문했으므로 제외합니다.


>> 큐의 뒤

IN  

    

 부산

 여수

울산 (Visit)

 >> 큐의 앞

OUT

방문한 곳: {세종, 서울, 강릉, 대구, 광주, 평양, 인천, 독도, 울산, }


9. 큐의 맨 앞에 있는 여수를 큐에서 내보내고 방문합니다. 여수시에 이어진 부산을 큐에 줄세웁니다Queue.enqueue(여수의 자손 노드들) . 단, 광주는 이미 방문했으므로 제외합니다.


>> 큐의 뒤

IN  

    

 부산

 부산

여수 (Visit)

 >> 큐의 앞

OUT

방문한 곳: {세종, 서울, 강릉, 대구, 광주, 평양, 인천, 독도, 울산, 여수, }


10. 큐의 맨 앞에 있는 부산을 큐에서 내보내고 방문합니다. 부산시에 이어진 여수, 울산은 모두 이미 방문했으므로 부산 visit 만 한 채로 다음 단계로 갑니다.


>> 큐의 뒤

IN  

    


 부산

부산 (Visit)

 >> 큐의 앞

나가는 방향

방문한 곳: {세종, 서울, 강릉, 대구, 광주, 평양, 인천, 독도, 울산, 여수, 부산, }



11. 마지막으로 큐에 남아있는 부산은 이미 방문되어 있으므로 큐에서 내보냅니다. 그 뒤에 큐에 남은 장소가 없으므로 BFS 탐색이 끝났습니다.


>> 큐의 뒤

IN  

    


 

부산 (이미 방문)

 >> 큐의 앞

나가는 방향

방문한 곳: {세종, 서울, 강릉, 대구, 광주, 평양, 인천, 독도, 울산, 여수, 부산, }


결과를 보니깐 11개 장소를 빠짐 없이 방문한 것을 볼 수 있습니다. 오예!


 

이 긴 과정을 파이썬 코드로 나타내보겠습니다. 


그래프는 파이썬에서 다음과 같이 나타낼 수 있겠습니다.

 
korea = {'세종': set(['서울', '강릉', '대구', '광주']),
         '서울': set(['평양', '인천', '세종']),
         '강릉': set(['독도', '세종']),
         '광주': set(['세종', '여수']),
         '대구': set(['세종', '울산']),
         '평양': set(['서울', ]),
         '인천': set(['서울', ]),
         '독도': set(['강릉', ]),
         '여수': set(['광주', '부산']),
         '울산': set(['대구', '부산']),
         '부산': set(['여수', '울산']),
         }


아래가 bfs 함수입니다.

 
def bfs(graph, root):
	visited = [] # 방문한 곳을 기록
	queue = [root] # 큐에 시작점을 줄세움

	while queue: # queue 가 빌 때 까지 탐색을 계속
		vertex = queue.pop(0) # 큐의 맨 앞의 원소를 방문할 꼭짓점으로 설정

		if vertex not in visited: # 꼭짓점이 방문된 적이 없다면 방문 기록에 추가
			visited.append(vertex)
			for node in graph[vertex]: # 꼭짓점에 연결된 노드들 중 
				if node not in visited: # 방문 안 된 곳 만을
					queue.append(node) # 큐에 줄세움

	return visited

##### 실행결과 #####
print(bfs(korea, '세종'))
>>> ['세종', '서울', '대구', '강릉', '광주', '인천', '평양', '울산', '독도', '여수', '부산']




BFS 경로탐색


방문 순서를 기록하면서 재귀 호출을 이용하면 아래와 같이 부산에서 평양까지의 경로 탐색도 할 수 있습니다. 


paths = [] def bfs_paths(graph, start, end, path=[]): # 그전 방문했던 노드들 유지. 이번 차례 방문하는 꼭짓점도 visited에 추가 path = path + [start] # 목적지에 도달했으면 paths 에 경로 기록 후 종료 if start == end: paths.append(path) # bfs 와 같음 queue = [start] while queue: vertex = queue.pop(0) for node in graph[vertex]: if node not in path: # 방문하지 않은 자손들에 대해 쭈우욱 재귀 호출 BFS_paths(graph, node, end, path) ##### 실행결과 ##### bfs_paths(korea, '부산', '평양') print(paths) >>> [['부산', '울산', '대구', '세종', '서울', '평양'], ['부산', '여수', '광주', '세종', '서울', '평양']]


참고 자료


[알고리즘] 깊이 우선 탐색(Depth First Search)과 구현 방법

자료구조

이 글에서는 트리나 그래프를 순회(traverse)/탐색(search)하는 알고리즘 중에 하나인 깊이 우선 탐색 (Depth First Search, DFS) 에 대해 다룹니다.  너비 우선 탐색에 대해서는 아래 글을 참고해주세요  


2016/07/05 - [자료구조] - [알고리즘] 너비 우선 탐색(Breadth First Search)과 구현 방법



그래프 탐색의 필요성이미 BFS 에 대한 제 글을 읽으셨다면 그래프 탐색의 필요성을 넘어가시면 됩니다. ^ㅍ^


 

사진 출처: http://pages.cs.wisc.edu/~paton/readings/Graphs/


그래프 자료구조라고 하면 어떤 것이 생각나시나요? 위와 같이 아기자기한 그림인가요? 


하지만 아래를 보면 어떠신가요?

사진 출처: 오마이뉴스


자료 구조 설명하다가 무슨 삼성 그룹의 순환 출자에 대한 그림을 가져왔냐고 화를 내실지도 모르겠습니다만 꼭짓점(vertex)이 수없이 많은 그래프라고 생각해보세요. 이 모든 꼭짓점을 빠짐없이 방문하려면 어떻게 해야할까요? 선형구조인 단순한 리스트(List) 였다면 리스트의 총 원소 개수 N을 구해서 0~ N 까지 위치의 원소를 출력하면 탐색 완료지만, 그래프에서는 노드에 순서대로 번호가 있는 것도 아니고 하기 때문에 모든 원소에 대한 탐색이 어려운 것입니다. 이 난관을 극복하기위해 DFS 같은 알고리즘이 필요한 것이죠.



기본 원리

아래 두 사진 출처: CS188: Artificial Intelligence, UC Berkeley (강의 슬라이드)

깊이 우선 탐색



너비 우선 탐색



위에 그림처럼 산과 그 속에 묻힌 보석을 찾아야하는 로봇이 있습니다. 로봇은 보석을 찾기 위해 첫번째 그림처럼 한없이 밑으로 내려가볼 수도 있고, 두번째 그림처럼 정상부터 점점 내려오면서 높이 별로 찾아볼 수도 있을겁니다. 전자와 같은 방식을 오늘 설명할 깊이 우선 탐색이라고 하고요, 후자는 너비 우선 탐색 (Breadth First Search, BFS) 라고 합니다. 둘은 산 속에 숨겨진 보석을 찾는다는 목표는 같지만, 그 찾는 순서가 다릅니다.


오늘 설명할 DFS 는 한 번 판곳은 땅바닥이 나올 때까지 죽도록 팝니다. 식물 뿌리를 생각해볼까요? 


이 식물의 뿌리는 네 방향으로 나뉘어집니다. 제가 각각 1, 2, 3, 4로 표시 했습니다.

이제 로봇이 1로 탐색하려고 들어갔다고 한다면... DFS 에 따르면 1의 줄기인 a, b, c 를 모두 다 찍고 가야합니다. 

마찬가지로 그 다음에 2에 들어갔다면 2에 연결 된 줄기 모두를 찍어야 3이나 4로 넘어갈 수 있는 거지요.



마침 엉덩국 씨의 유명한 짤이 생각나서 넣어봤습니다.


 한 곳을 팠을 때는 마음대로였겠지만, 나갈때는 아니란다! DFS 는 팠으면 끝까지 파고 난 다음에야 나갈 수 있는 것입니다.


귀여운 그림을 사용해서 설명을 해봤는데 실제 그래프를 통해 DFS 가 어떻게 이루어지는지 아래에서 살펴봅시다.


DFS의 방문 순서

1. 맨 위 root node (1) 에서 탐색이 시작한다고 가정.
2. 좌우 노드 중 왼쪽 노드를 항상 우선 탐색한다고 가정.
사진 출처: http://docs.seqan.de/seqan/1.2/streePreorder.png



위 그림에서 각 꼭짓점 안의 숫자는 방문 순서를 의미합니다. 맨 위 뿌리 노드에서 시작합니다. 가정에 따라 맨 왼쪽으로 가네요... 그리고 한없이 밑으로 갑니다. 왼쪽 3으로 갔다가 4로 가서 5, 6까지 내려갑니다. 다음, 현재 방문하지 않은 꼭짓점 중 가장 왼쪽이면서 위쪽에 있는 노드인 7로 갑니다. 그 뒤로는 위 그림의 방문 순서를 스스로 따라가보시기를 권합니다. 


파이썬으로 구현하기

제가 요즘 열심히 공부하는 Python 으로 DFS 를 구현해보고자 합니다. 중요한 점: DFS 를 구현할 때는 스택을 이용하는데, 그 이유를 아래 그림과 함께 보시죠.

사진 출처: https://en.wikipedia.org/wiki/Depth-first_search

 순서

(방문하고 있는)

꼭짓점

자손

 스택 

(빨간색 = 스택의 맨 위)

 1

 

 

   A

 2

 A (시작점)

 B, C, E

  B, C, E

 3

 B

 D, F

  D, F, C, E 

 4

 D

 없음

  F, C, E 

 5

 F

 E

  E, C, E 

 6

 E

 A (이미 방문)

   C, E 

 7

 C

 G

   G, E 

 8

 G 없음

  E (이미 방문)

 9

 스택이 비면 탐색 종료






1. 스택에 처음 시작점을 넣습니다stack.push(A).

2. 스택의 맨 위 원소를 빼낸stack.pop() (A) 가 현재 방문하고 있는 꼭짓점이 됩니다. 그 꼭짓점의 자손들 (B, C, E) 를 스택에 밀어 넣습니다stack.push(B, C, E).

3. 또 다시 stack.pop() (B) 를 방문합니다. 그 다음 B의 자손들 (D, F) 를 스택에 밀어 넣습니다stack.push(D, F).

4. stack.pop() (D) 를 방문합니다. D 의 자손은 없으니 다음 순서로 넘어갑니다.

5. stack.pop() (F) 를 방문합니다. F 의 자손(E) 를 스택에 밀어 넣습니다stack.push(E).

6. stack.pop() (E) 를 방문합니다. E 의 자손(A) 를 스택에 밀어 넣으려고 보니 이미 방문한 점이네요. 넣지 않고 다음 순서로 넘어갑니다.

7. stack.pop() (G) 를 방문합니다. G 의 자손은 없으니 다음 순서로 넘어갑니다.

8. stack.pop() 하니깐 이미 방문한 E가 나오네요. 다음 순서로 넘어갑니다.

9. 더이상 stack 에 남아있는 꼭짓점이 없습니다. 탐색을 종료합니다.



pseudo-code 로 DFS 과정을 대략 짜보겠습니다.

 
function DFS(Graph graph, Node root)
	Stack stack // Stack 선언

	stack.push(root)

	while 스택에 원소가 있을 동안 do
		방문할 꼭짓점 V = stack.pop() // 스택 맨 위의 원소를 꺼내서
		V.visit() // 방문
		stack.push(V 의 자손 노드들 *단, 이미 방문한 노드는 제외) // 방문한 노드의 자손 노드들을 스택에 push.
	end


자 이제 파이썬으로 코딩하기 전에, Graph 를 표현해야겠죠.


파이썬에서 Graph 는 아래 같이 원소와 연결된 원소들의 set 을 대응시킨 dictionary 자료형으로 표현할 수 있습니다. (Python Patterns - Implementing Graphs | Python.org)

#파이썬에서 위 그래프 표현
graph = {'A': set(['B', 'C', 'E']),
         'B': set(['A', 'D', 'F']),
         'C': set(['A', 'G']),
         'D': set(['B']),
         'E': set(['A', 'F']),
         'F': set(['B', 'E']),
         'G': set(['G'])}


자 그러면 DFS 를 구현해봅시다. 

def dfs(graph, root):
	visited = [] # 각 꼭짓점(vertex)이 방문되었는지 기록
	stack = [root, ] 

	while stack: # stack 이 비게 되면 탐색 끝
		vertex = stack.pop() # 방문되어지고 있는 꼭짓점
		if vertex not in visited: # 
			visited.add(vertex)
			stack.extend(graph[vertex] - visited)

	return visited;

########### 실행 결과 ###########
print(dfs(graph, 'A'))
>>> {'F', 'B', 'A', 'E'}

참고로 DFS 는 그래프에서 모든 꼭짓점을 찾아가는 과정이라고 생각하세요. dfs(graph, 'A') 의 결과가 저와 순서가 다른 것은 당연합니다. visited 는 순서가 없는 list 자료형이니까요. 중요한 것은 dfs 를 통해 모든 꼭짓점을 찾았느냐입니다.


이 DFS 를 재귀적으로(recursive) 구현도 합니다. 좀 더 깔끔해 보이는 장점이 있는데, 아래 코드를 함께 보시죠.

def dfs_recursive(graph, root, visited=None):
	if visited is None:
		visited = set()

	visited.add(root)

	# 주어진 root 과 연결되어 있는 다른 node 들에 대해 방문하지 않은 것들만 재귀 호출합니다.
	for node in graph[root] - visited:
			dfs_recursive(graph, node, visited)

	return visited



DFS 경로 탐색


그렇다면 DFS 로 A 부터 F 까지 가는 경로를 탐색해볼까요? 앞의 dfs 함수와는 달리 방문 순서를 순서대로 기록할 필요가 있다는 것만 기억하시면 되겠습니다.

 

paths = []

def dfs_paths(graph, start, end, visited=[]):
	# 그전 방문했던 노드들 유지. 이번 차례 방문하는 꼭짓점도 visited에 추가
	visited = visited + [start]

	# 도착했으면 paths 에 경로 기록하고 종료
	if start == end:
		paths.append(visited)

	# 현재 점의 자손 노드 중에 방문하지 않은 노드에 대해 재귀 호출
	for node in graph[start]:
		if node not in visited:
			dfs_paths(graph, node, end, visited)


########### 실행 결과 ###########
dfs_paths(graph, 'A', 'F')
print(paths)
>>> [['A', 'C', 'F'], ['A', 'B', 'E', 'F']]



다음에는 너비 우선 탐색에 대해 다뤄보도록 하겠습니다.



참고 자료

http://pages.cs.wisc.edu/~paton/readings/Graphs/

Depth-First Search and Breadth-First Search in Python - Edd Mann

[자작] web2kindle: 웹페이지를 pdf 로 저장해 킨들 이메일로 보내기

공부/Python

Kindle 이메일에 문서를 보내면 자동으로 동기화하는 기능 아시죠?(참고: Send to Kindle by E-mail) 




저는 이 기능을 인터넷 기사나 블로그 글 같은 것을 옮길 때 쓰는데, 매번 pdf 변환해야하고 이메일 로그인해서 킨들 이메일로 보내야하고 여간 귀찮은 일이 아니더군요. 그래서 킨들로 바로바로 쉽게 보내기 위해 간단한 Python 스크립트를 만들어봤습니다. 


Python 버전은 3.x 이고 사용한 모듈은 pdfkit(웹페이지를 pdf 로 바꿔줌), smtplib(SMTP 서버를 이용해 간단히 이메일 보내기), lxml 입니다. 시간이 되면 제 GitHub 에 꾸준히 개선판을 올리겠습니다. (아직 기능적으로 많이 부족해요 ㅠㅠ 참고만 해주세요)


사용법: 먼저 네이버/다음/지메일 계정으로 로그인한 다음, 본인의 Kindle 이메일 계정을 쓰고 킨들에 전송하고자 하는 사이트의 URL 을 입력하면 됩니다.

#!/usr/bin/env python3
# -*- coding:utf-8 -*-

import pdfkit
import getpass
import smtplib
import lxml.html

from email.mime.multipart import MIMEMultipart
from email import encoders
from email.message import Message
from email.mime.base import MIMEBase

NAVER_SMTP = "smtp.naver.com"
NAVER_SMTP_PORT = 587
NAVER_SUFFIX = "@naver.com"

DAUM_SMTP = "smtp.hanmail.net"
DAUM_SMTP_PORT = 465
DAUM_SUFFIX = "@hanmail.net"

GMAIL_SMTP = "smtp.gmail.com"
GMAIL_SMTP_PORT = 587
GMAIL_SUFFIX = "@gmail.com"

# store the webpage in a byte variable
def html2pdf(url):
	# convert the webpage to pdf
	options={
       	'page-size': 'A4',
        'margin-top': '0',
        'margin-right': '0',
        'margin-left': '0',
        'margin-bottom': '0',
        'encoding': "UTF-8",
        'no-outline': None,
    }
	return pdfkit.from_url(url, False, options=options)

def get_title_from_webpage(url):
	# Get the title from url
	t = lxml.html.parse(url)
	return t.find(".//title").text

def send_pdf_to_kindle(server, sender, receiver):
	body = MIMEMultipart()
	body["From"] = sender
	body["To"] = receiver
	body["Subject"] = ""

	url = input("킨들에 전송하고자 하는 url을 입력하세요.")

	title = get_title_from_webpage(url)
	try:
		pdf = html2pdf(url)
	except:
		print("pdf 로 변환하는데 오류가 발생했습니다.")
	#pdf = pdfkit.from_url(url, False)
	#file = html2pdf_as_file(url)

	#file = open("out.pdf", "rb")
	attachment = MIMEBase("application/pdf", "application/x-pdf")
	attachment.set_payload(pdf)
	#attachment.set_payload(file.read())
	#file.close()
	encoders.encode_base64(attachment)
	attachment.add_header("Content-Disposition", "attachment", filename= title + '.pdf')
	body.attach(attachment)

	try:
		server.sendmail(sender, receiver, body.as_string())
		print(receiver +  "로 전송 완료")
		server.quit()
	except:
		print('메일을 전송하는데 오류가 발생했습니다.')

def main():
	# initialize configurations for sending email
	while True:
		email_provider = input("어떤 이메일을 사용할까요? 1. 네이버 2. 다음 한메일 3. 구글 지메일")
		if email_provider == '1':
			smtp_server = NAVER_SMTP
			smtp_port = NAVER_SMTP_PORT
			smtp_suffix = NAVER_SUFFIX
			USE_SSL = False
			break
		elif email_provider == '2':
			smtp_server = DAUM_SMTP
			smtp_port = DAUM_SMTP_PORT
			smtp_suffix = DAUM_SUFFIX
			USE_SSL = True
			print("Kindle 허용 이메일에는 @hanmail.net 이메일로 추가해주세요.")
			break
		elif email_provider == '3':
			smtp_server = GMAIL_SMTP
			smtp_port = GMAIL_SMTP_PORT
			smtp_suffix = GMAIL_SUFFIX
			USE_SSL = False
			break
		else: 
			print("잘못 입력하셨습니다.")
	if USE_SSL:
		server = smtplib.SMTP_SSL(smtp_server, smtp_port)
	else:
		server = smtplib.SMTP(smtp_server, smtp_port)
	username = input("로그인 ID를 입력해주세요.")
	sender_email = username + smtp_suffix
	password = getpass.getpass("비밀번호를 입력해주세요.")
	server.starttls()
	server.login(username, password)
	print("로그인 되었습니다.")
	#print("로그인 실패")

	receiver_email = input("Kindle 이메일 계정을 입력하세요.")

	send_pdf_to_kindle(server, sender_email, receiver_email)

if __name__ == "__main__":
    main()