HappyTomatoLife

Shortest Path Finding • Dijkstra Algorithm • Floyd–Warshall algorithm • Transitive Closure Matrix • Activity Network Shortest Path Finding (1~20) Shortest Path finding은 weighted Digraph에서 최적의 path를 찾는 문제다. 이때 path length는 지나온 path에서 각 edge의 weight를 합해서 구한다. source vertex -> destination vertex라는 용어도 사용한다. shortest path는 3 가지 타입이 있다. 첫째는 vertex u에서 vertex v로 가는 경로를 찾는 "single source, single destin..

Binary Search Trees AVL tree B-Trees Binary Search Trees heap의 한계 heap 자료구조는 root를 검색할 때만 O(logn)의 성능을 갖는다. 만약에 다른 item을 찾는 경우라면, O(n)의 시간 복잡도를 갖게 된다. binary search tree의 필요성 균일하게 tree 높이에 비례한 시간복잡도 O(log2n)을 갖는 자료 구조이기 때문이다. Binary search tree의 정의 전제 : 중복되는 요소가 없음 left sub-tree nodes < root < right sub-tree nodes가 재귀적으로 모든 트리에 적용됨 search a key 구현 1. 재귀 함수 def rBST(self, root, key): if not root:..

Binary tree ex) huffman coding tree, tree traverse, evaluation tree, threaded binary trees Heap ex) priority queue, insert, delete, sort Introduction tree tree는 계층적인 데이터 구조를 나타내기 위한 자료 구조다. tree는 root와 sub-trees로 이루어진다. huffman coding tree huffman coding tree는 텍스트를 압축하기 위한 알고리즘으로, 빈도가 높은 문자를 짧은 비트로 매칭되도록 트리를 구현한 것이다. import copy class Node: def __init__(self, char, num): self.right = None self.l..

Sort selection sort bubble sort insertion sort shell sort quick sort merge sort radix sort sort에 대한 기본적인 설명 정렬이란? sorting 정렬은 사실 탐색을 하기 위한 '준비'를 하는 단계다. 예를 들면, binary search의 전제 조건은 자료가 정렬되어있어야 한다는 것이었는데, 이것이 단지 binary search 만의 조건이 아니었던 것이다. sort 문제는 재료가 되는 데이터와 이를 정렬하는 문제로 구성된다. 데이터는 기록한 구조체 형태일 수 있다. 학생 목록을 정렬하는 문제라면, 한 학생 Ri는 학생을 식별하기 위한 key(Ki)와 다른 데이터(성적, 학기, 재학 상태 등)으로 이해할 수 있다. 그리고 이렇게 데..

학점교류로 듣는 숙명여대 자료구조 day 13. 2022.1.7. 금요일 Shortest Path and Activity Network shortest path finding dijkstra algorithm floyd-warshall algorithm transitive closure matrix activity network shortest path problems directed weighted graph path length is sum of edge weights on path the vertex at which the path begins is the source vertex the vertex at which the path ends in the destination vertex single..

학점교류로 듣는 숙명여대 자료구조 수업 day 13. 2022.1.7. 금요일 graph representation adjacency matrix adjacency list : linked / array adjacency matrix n*n matrix, where n=# of vertices A(i, j) = 1, iff (i,j) is an edge, otherwise 0 self edge = 0 무방향 그래프이기 때문에 대칭으로 그래프가 그려져있음 Diagonal entries are zero adjacency matrix for undirected graph is symmetric A(i, j)=A(j, i) Adjacency Matrix (Digraph) 방향 그래프의 경우 나가는 간선이 진출 ..

학점교류로 듣는 숙명여대 자료구조 day 12. 2022.1.6. 목요일 Koenigsberg Bridge problem 다리를 한번씩만 건너서 처음 위치에 돌아올 수 있을까? => 오일러 경로 중복없이 원래 자리로 돌아올 수가 없다. 그래프로 문제를 풀고자 했던 첫번째 시도 edge, node로 표현했다. Euler's principle - vertex의 차수가 짝수여야지 풀 수 있다. Graphs G = (V, E) V is a vertex set = nodes, points E is an edge set type : undirected graph / directed graph (digraph) undirected graph : no oriented edge directed graph : has or..

숙명여대 학점교류로 듣는 자료구조 day 12. 2022.1.6. 목요일 Binary Search Trees Binary search Trees Balanced binary search trees : AVL Tree heap provides a good performance of O(log2n) only when handling the root for searching other item than the root, it takes O(n) time why binary search tree is necessary requires O(log2n) for any item, which is proportional to tree height (h) => 이진 탐색을 트리로 구현한 것 Binary search tr..

숙명여대 학점교류로 듣는 자료구조 day 11. 2022.1.5. 수요일 정렬 insertion sort => quadratic ------ shell sort => faster than quadratic quick sort heap sort merge sort radix sort Insertion sort If n 1 a[0:n-2] is sorted recursively a[n-1] is inserted into the sorted a[0:n-2] complexity is O(n^2) usually implemented non-recursively Insert a number to the sorted list n 앞까지는 모두 정렬되어있다고 가정하고, n번째 원소를 알맞은 위치에 삽입한다. class..

최종 목표는 프로그램 1, 2를 구현하는 것이다. 프로그램 1. 트리 생성 / 노드의 깊이 / 노드의 높이 / 트리의 깊이 / 트리의 높이 프로그램 2. 허프만 코딩 트리 그러나 이에 앞서서 트리 구조, 이진 트리 구조를 충분히 이해하고 구현하는 과정을 거치고자 한다. 먼저 이진 트리에서 구현하고자 하는 목록은 다음과 같다. 이진 트리 생성 노드의 깊이 노드의 높이 트리의 노드 최댓값 트리의 깊이 최댓값 허프만 코딩 트리 postorder preorder inorder level order copy tree evaluation tree threaded binary tree heap delete insert heap sort make heap priority queue 이진 트리 생성 이진 트리는 최대 두..