본문 바로가기
  • 紹睿: 자유롭고 더불어 사는 가치있는 삶

Data/python·알고리즘39

[Graph] 최단경로검색, Dijkstra algorithm(다익스트라) Dijkstra algorithm(다익스트라 알고리즘) 열심히 그렸는데, 맞겠지. stack에 값을 넣어놓고 pop해서 꺼내면 된다. *A에서 D로 가는 경우, A에서 B를 거쳐 D로 가게되면 8이 됨으로, 7A를 저장해 준다. class Graph: def __init__(self): self.node = set() self.edges = {} self.distances = {} def add_node(self, value): self.nodes.add(value) def add_edge(self, from_node, to_node, distance): self._add_edge(from_node, to_node, distance) self._add_edge(to_node, from_node, dist.. 2018. 9. 25.
[Graph] BFS(Breadth first Search), 넓이우선탐색 [Graph] DFS(Depth first Search), 깊이우선탐색에서는 stack을 이용하고, BFS에서는 queue를 이용하면 된다. vertextList = [0, 1, 2, 3, 4, 5, 6] edgeList = [(0, 1), (1, 0), (0, 2), (2, 0), (1, 3), (3, 1), (2, 4), (4, 2), (2, 5), (5, 2), (4, 6), (6, 4)] graphs = (vertextList, edgeList) def bfs(graph, start): vertextList, edgeList = graph visitedVertex = [] queue = [start] adjacencyList = [[] for vertex in vertextList] for edg.. 2018. 9. 25.
[Graph] DFS(Depth First Search), 깊이우선탐색 DFS, 깊이우선탐색은 게임에서 주로 많이 쓰인다. 먼저, vertextList, edgeList를 만들어 adjacencyList를 만들어 준다. adjacencyList를 만들어 주면 DFS를 이용할 수 있다 ^_^ [[1, 2], 2018. 9. 24.
[Binary Tree] 이진트리(2) - pre order, in order, post order 이진트리의 삽입과 삭제는 [Binary Tree] 이진트리(1)에 있다 오늘은 Pre order, In oder, Post order에 대하여 알아보자! 예전에 정보처리기사와 수업을 들으면서 Pre = PLR IN = LPR Post = LRP P(parent), L(left), R(right)순이라고 그냥 외웠었다. class BinaryTree: def preorder(self): if self.head != None: self.__preorder(self.head) def __preorder(self, cur): self.preorder_list.append(cur.val) if cur.left != None: self._preorder(cur.left) if cur.right != None: se.. 2018. 9. 24.
[Binary Tree] 이진트리 (1) - 삽입, 삭제 Binary Tree 이진트리 무슨 코드든 차분히, 차근차근 한단계씩 밟고 지나가면 이해할 수 있다. BinaryTree()를 하면, head = Node(None) 다음과 같은 아이들이 생성된다. 1. add: val의 값을 비교해 left, right에 넣어주기 2. search: 있으면 True, 없으면 False 3. remove: 복잡복잡한듯 값이 head.val이면 자식 (left, right)를 조사하고 해당 조건에 따라 처리 아니면, head.val의 값과 비교하여 작으면 left, 크면 right로 가서 반복처리 class Node: def __init__(self, item): self.val = item self.left = None self.right = None class Bina.. 2018. 9. 24.
[heap sort] 힙 힙 힙! Heap tree parent 와 child로 이루어진 구조 heapify: 트리를 heap 트리로 바꾸는 과정 siftdown: (max) heap에서는 parent가 child보다 크면 된다 1단계만 실제로 보자면 root(6)의 right child(4)에서는 child와 비교헀을때, 8이 가장 크기 때문에 8과 4를 swap해준다. 이러한 과정을 거치면 아래와 같이 된다. [6, 2, 4, 9, 7, 5, 8] [6, 2, 8, 0, 7, 5, 4] [6, 9, 8, 2, 7, 5, 4] [9, 7, 7, 2, 6, 5, 4] (max) heap에서는 가장 큰 값만 뽑으면 되기 때문에, 8, 5, 4의 경우 더이상 순회 하지 않는다. def heapsort(a): def swap(a, i, j):.. 2018. 9. 24.

티스토리툴바