ComDoc ComDoc

1. 재귀 방문한 노드는 마크합니다. 따라서 마크용 셋을 미리 만들어야 합니다. 마크용으론 리스트보다 set이 좋은 경우가 많은데 set은 해시를 이용해서 검색 시 속도가 빠르기 때문입니다. https://wiki.python.org/moin/TimeComplexity 재귀적이지만 비교적 단순한 알고리듬입니다. 스택으로도 만들 수 있습니다. for 문 내부에 재귀가 있습니다. 그렇기 때문에 하나의 노드에서 재귀로 깊이 우선 검색을 먼저 하게 되고, for 문으로 다음 노드로 넘어가서 또 깊이 우선 검색을 하게 되는 반복 구조입니다. class Graph: def __init__(self): self.graph = dict() # {} self.marked = set() def add(self, v, w)..

그래프는 정점(노드)과 간선(링크, 에지)으로 구성됩니다. 지도도 일종의 그래프라 할 수 있죠. 각 마을은 정점, 도로가 간선. 정점은 v1, v2 등으로 정의하며, 간선은 (v1, v2)와 같은 쌍으로 정의합니다. 정점들은 무게나 비용 등의 가중치를 포함할 수 있습니다. 방향성(유향) 그래프(directed graph, digraph) 간선에서 정점의 순서를 따집니다. 화살표로 표시할 수 있습니다. 무방향성(무향) 그래프 경로의 길이는 첫 번째 정점에서 마지막 정점까지의 간선의 수를 의미합니다. 정점 자신으로 향하는 경로, 즉 루프도 경로에 포함되지만, 이때 루프의 길이는 0입니다. 첫 번째 정점에서 마지막 정점까지의 (하나 이상의 간선으로 이루어진) 경로가 같은 경우를 사이클(cycle)이라고 합니다..

노드 삭제하기 상당히 복잡합니다. 먼저 노드에서 특정값을 찾아야 합니다. (find 메서드를 고치면 되겠죠?) def find(self, item): current = self.root while True: if current is None: return None if current.item > item: current = current.left elif current.item < item: current = current.right else: # current.item == item return current 찾은 뒤에는... 1. 특정값을 가진 노드가 자식 노드가 없는 리프 노드라면 노드를 삭제하고, 삭제된 노드를 가리키던 부모의 링크를 None으로 바꿔줍니다. 2. 만약 한 개의 자식이 있으면, 삭..

최댓값과 최솟값 찾기 이진 탐색 트리에서 최솟값은 항상 왼쪽에 있기 때문에 왼쪽의 None을 찾아 직전의 값을 리턴하면 됩니다. 최댓값은 반대입니다. 특정값 찾기 현재 노드의 값과 특정값을 비교해서 높으면 오른쪽 낮으면 왼쪽으로 내려가면 됩니다. class Node: def __init__(self, item): self.item = item self.left = None self.right = None class BST: def __init__(self): self.root = None def insert(self, item): new_node = Node(item) if self.root is None: self.root = new_node return current = self.root while ..

트리란? Tree는 edge와 node의 집합입니다. 최상위 node를 root라 하고, 한 노드가 아래 노드와 연결되어 있을 때 위 노드를 parent, 아래 노드를 child라 합니다. 자식노드가 없는 노드를 leaf 노드라고 합니다. 직접 연결되지 않은 노드라도 연결된 에지를 통해 방문할 수 있습니다. 한 노드에서 다른 노드로 도달하는 데 사용한 에지의 모음을 경로(path)라고 합니다. 모든 노드를 일정한 순서로 방문하는 것을 트리 순회(tree traverasal) 또는 트리 탐색이라 합니다. 트리를 레벨로 구분하기도 합니다. 루트는 레벨0 그 자식들은 레벨 1이 되는 식입니다. 총 레벨을 수를 트리의 깊이라고 합니다. 이진트리란? 이진 트리(binary tree)는 모든 노드의 자식 노드가 2..

집합(set)은 파이썬 2.3부터 포함된 자료형입니다. 이걸 또 한 번 만들어 보겠습니다. 삽질 맞습니다. ㅠ,.ㅠ 집합의 특징은 다음과 같습니다. 집합의 멤버는 순서가 없으며 유일합니다. 멤버가 하나도 없는 집합을 공집합(empty set)이라 합니다. 집합에 포함될 수 있는 모든 멤버를 포함하는 집합을 전체집합(universe)이라 합니다. 두 집합의 멤버가 정확하게 같아야 같은 집합입니다. 한 집합의 모든 멤버가 다른 집합에 포함되어 있을 때 이 집합을 다른 집합의 부분 집합(subset)이라 합니다. 집합의 동작은 다음과 같습니다. 합집합 두 집합을 합쳐 새로운 집합을 만듭니다. 교집합 두 집합에 모두 존재하는 멤버로 새로운 집합을 만듭니다. 차집합 한집합의 멤버 중 다른 집합에 존재하지 않는 멤..

해싱은 데이터를 아주 빠르게 '삽입'하거나 '가져올 때' 사용하는 기법입니다. 하지만, 최솟값이나 최댓값을 찾을 때(전체 자료를 검색해야 할 때)는 효율이 떨어집니다. 김 빠지는 이야기를 하나 하자면.. 파이썬의 딕셔너리는 해시 테이블로 구현되어 있습니다.. ㅇㅇ 있는 걸 만드는 삽질을 또 해보겠습니다. 주의: 직접 만든 해시 함수를 보안에 관련된 부분에 사용하는 것은 위험합니다. 해시(hash)의 개념은 각기 다른 곳에서 독립적으로 발생하였다. 1953년 1월 H. P. Luhn은 체이닝(chaining)으로 해시를 사용한 내부 IBM 비망록을 작성했다. G. N. Amdahl, E. M. Boehme, N. Rochester, Arthur Samuel은 거의 같은 시기에 해시를 사용하는 프로그램을 제..

먼저 파이썬 내장 딕셔너리 자료형을 이용해 다음 텍스트에서 각 단어가 몇 번 나오는 지를 확인하는 프로그램을 구현해 봅시다. the brown fox jumped over the blue fox 예상 결과 the 2 brown 1 fox 2 jumped 1 over 1 blue 1 코딩 def count_words(text): words = text.split(' ') counter = {} for word in words: if word in counter: counter[word] += 1 else: counter[word] = 1 for word in counter: print(word, counter[word]) count_words('the brown fox jumped over the blue..