ComDoc ComDoc

너비 우선 검색(bfs)의 응용입니다. 경로의 길이가 1인 노드(정점)들을 찾아보고, 길이가 2인 노드들을 찾아보고... 반복하다 목표를 찾으면 끝입니다. 각 노드를 처음 방문했을 때 직전 노드와 현 노드를 기록하는데 이것이 최단 경로의 재료가 됩니다. 이 기록을 도착 노드에서 시작 노드까지 역으로 거슬러 올라가면 최단 경로가 되기 때문입니다. 이 재료를 중간중간 저장할 수 있도록 set이었던 marked를 딕셔너리로 수정합니다. class Graph: def __init__(self): self.graph = {} def add(self, v, w): self.graph.setdefault(v, {w}) self.graph[v].add(w) self.graph.setdefault(w, {v}) self..

현재 정점과 인접한 정점 중 방문하지 않은 정점을 '큐'에 넣고 하나씩 방문하면서 위의 문장을 반복합니다. 깊이 우선 검색과 비교했을 때 스택, 큐 외에는 차이가 없습니다. 귀차니즘으로... list를 queue로 사용했습니다. https://docs.python.org/ko/3/tutorial/datastructures.html#using-lists-as-queues 리스트를 큐로 사용하는 것도 가능한데, 처음으로 넣은 요소가 처음으로 꺼내지는 요소입니다 (《first-in, first-out》); 하지만, 리스트는 이 목적에는 효율적이지 않습니다. 리스트의 끝에 덧붙이거나, 끝에서 꺼내는 것은 빠르지만, 리스트의 머리에 덧붙이거나 머리에서 꺼내는 것은 느립니다 (다른 요소들을 모두 한 칸씩 이동시켜야..

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)이라 합니다. 집합의 동작은 다음과 같습니다. 합집합 두 집합을 합쳐 새로운 집합을 만듭니다. 교집합 두 집합에 모두 존재하는 멤버로 새로운 집합을 만듭니다. 차집합 한집합의 멤버 중 다른 집합에 존재하지 않는 멤..