ComDoc ComDoc

다양한 소팅을 애니메이션으로 보여줍니다. 볼만합니다. https://www.toptal.com/developers/sorting-algorithms Sorting Algorithm Animations Animation, code, analysis, and discussion of 8 sorting algorithms on 4 initial conditions. www.toptal.com 미리 알아야할 지식 파이썬에서는 2개의 변수의 값을 교환할 때 a, b = b, a를 쓸 수 있습니다. 다른 프로그래밍 언어에서는 temp를 동원해서 temp = a a = b b = temp 를 사용하는 것에 비해 상당히 간편합니다. 무식한 정렬법 다들 처음 정렬을 배울 때 이런 식의 무식한 정렬 알고리듬 하나씩 만들어..

위상 정렬(topological sorting)이란 방향성(유향) 그래프의 모든 방향성 간선이 한쪽을 가리키도록 모든 정점을 배치하는 방법입니다. 위키에는 다음과 같이 설명합니다. ㅇㅇ 같은 말입니다. 위상 정렬(topological sorting)은 유향 그래프의 꼭짓점들(vertex)을 변의 방향을 거스르지 않도록 나열하는 것을 의미한다. 쉽게 말해서 위 그래프를 빠지지 않고 모두 이수할 수 있도록 순서를 정하는 것이 위상 정렬입니다. 입학 -> 개론 -> (어셈블리) -> 자료구조 -> 운영체제 -> 알고리듬 입학 -> 개론 -> 자료구조 -> (어셈블리) -> 운영체제 -> 알고리듬 입학 -> 개론 -> 자료구조 -> 운영체제 -> (어셈블리) -> 알고리듬 입학 -> 개론 -> 자료구조 -> 운..

너비 우선 검색(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 ..