Sweet Sixteen Bars Sweet Sixteen Bars

자료구조 07 - 3 / Graph 정의 MST: Minimum Spanning Tree - 사용된 간선들의 가중치 합이 최소인 트리, 모든 정점을 방문하는데 사용되는 최소 비용 경로 Spanning Tree (신장트리) : 순환이 없는 최소 연결 그래프 (간선의 수가 최소) n개 정점 -> n-1개 간선 Kruskal Algorithm - Greedy Method(탐욕적 방법) 을 이용해서 모든 정점을 최소 비용으로 연결, 결정 순간마다 가장 최적의 방법으로 진행 시간 복잡도 O(elog₂e) Union-Find 알고리즘으로 사이클 존재 확인 3. 간선 선택 MST에 destination 정점 넣기 Prim Algorithm - 시작 정점부터 신장트리 집합을 단계적으로 방문하며 확장, 연결된 간선 중 ..

자료구조 07 - 2 / Graph 탐색방법 너비 우선 탐색 (Breadth First Search: BFS) 최단경로, 임의의 한 정점에서 연결된 모든 정점으로 나가감, Tree의 LeveOrder Trabersal, 자료구조 Queue 사용(정점의 순서 기록) 시간복잡도 O(v+e) vertex 수 + edge 수 깊이 우선 탐색 (Depth First Search: DFS) 임의의 한 정점으로부터 연결된 한 정점으로만 나아간다, 연결된 정점이 없을때까지 방문하고 그 전 단계 정점으로 돌아서 다시 나아간다 자료구조 Stack 사용(방문했던 정점 기록) 시간 복잡도 O(v+e) vertex 수 + edge 수 추가용어 완전 그래프(complete Graph) : 최대 간선 수를 가진 그래프, 모든 정점..

자료구조 07 - 1 / Graph 정의 각 객체(꼭지점, 정점: vertex, vertices, Node)가 간선(Edge, Link)으로 서로 이어져 있는 집합, 사이클(순환)을 허용한다. E(u, v) = souce vertex에서 destination vertex로 가는 edge Degree 각 정점에 연결된 Edge 수 (Directed Graph에서 나가는 간선 개수 Outdegree/ 들어오는 간선 개수 Indegree weighted Graph 가중 그래프 Sub Graph 부분 그래프 완전 그래프 (모든 정점 간선으로 연결 Weighted Graph Directed Graph(Digraph) and Undirected Graph Representing a Graph Approch 접근방식..

자료구조 06 / Heap 정의 정의 Heap : 데이터에서 최대값과 최소값을 빠르게 찾는 완전 이진트리 구조 (Complete Binary Tree) * 완전 이진트리 : Node를 삽입 할때 최하단 왼쪽 Node 부터 차례대로 삽입 힙의 기능 일반적으로 최대값, 최소값을 찾을때 기대값 O(n) 힙에 데이터를 넣는다면 O(logn) 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현등에 활용 구조 Max Heap 구조 1) 각 노드의 값은 해당 노드의 자식노드가 가진 값 보다 크거나 같음 2) 완전 이진트리 형태 Min Heap 구조 1) 각 노드의 값은 해당노드의 자식노드가 가진 값보다 작거나 같음 2) 완전 이진트리 형태 구현 배열을 이용한 Heap 구현 일반적으로 배열로 구현 (완..

자료구조 05 - 4 / Tree - AVL Tree / 정의 AVL 트리(발명자 Adelson-Velsky and Landis), 이진탐색 트리 구조로 스스로 균형을 잡는 데이터 구조중 최초 발명 두 자식 SubTree의 Height는 항상 1 만큼 차이를 유지, 1보다 큰 경우 스스로 균형을 잡음(Rotation) balance factor = abs( height(left subtree) - height(right subtree) ) A의 서브트리의 높이의 차가 1 보다 커지는 경우 Rotation을 진행 원리 Rotation 이해하기 Single Rotation (raywenderlich.com) 불균형이 발생하면 root의 SubTree 중 높이가 높은 SubTree의 최상단 노드를 Pivot ..

자료구조 05 - 3 / Tree - BinarySearchTree (BST) 정의 이진트리의 종류 중 하나로 Ordered or Sorted Binary Tree로 불림 이진트리로 Subtree가 추가 될때 조건을 가짐, 예를 들어 Current Node 보다 작으면 Left, 크면 Right Child로 추가됨 저장 규칙 (조건)이 좀 더 효율적인 트리로 만들어줌 일반적인 이진트리보다 빠른 탐색 속도를 가진다. 추가 Inserting 추가될 노드의 부모노드가 될때까지의 높이(h)를 거치며 조건에 맞게 자리 잡으므로 O(h) time 소요 탐색 Searching 마찬가지로 추가될 노드의 값을 조건을 확인하며 찾아가므로O(h) time 소요 순회 Traversing In-Order : left -> ro..

자료구조 05 - 2 / Tree - BinaryTree 정의 트리 구조에서 2개의 서브트리만 가지는 트리의 형태, 모든 노드의 자식노드는 두개의 서브트리만 가짐 이진트리의 Leaf Node의 상태에 따라서 * (N = level) Perfect Binary Tree (포화 이진 트리) : 모든 레벨에 노드가 채워진 트리 (총 Node 갯수 : 2ᴺ + 1 개 / Leaf의 갯수: 2ᴺ 개) Complete Binary Tree (완전 이진 트리) : 자식노드가 왼쪽 -> 오른쪽 형태로 채워진 트리 Full Binary Tree (정 이진 트리) : 자식노드가 없거나 2개인 노드로 채워진 트리 로 구분지어 표현 할수 있다. 구현 class BinaryTreeNode: Node { var leftChild..

자료구조 05 - 1 / Tree 정의 그래프의 일종으로 최상위 노드 Root Node를 시작으로 노드를 이어가는 자료구조 비순환, 비선형 자료구조로, 계층적관계 (Hierarchical Relationship)를 표현한다. 트리를 구성하고 있는 구성요소 Edge : 트리를 구성하기 위해 노드와 노드를 연결하는 선 Internal Node : 단말 노드를 제외한 모든 노드로 루트 노드 포함 Parent Node : 현재 노드의 상위 레벨에 이어진 상위 노드 Child Node : 현재 노드의 하위레벨에 이어진 하위 노드 github GitHub - keeplo/SwiftTools: 자료구조 알고리즘 등 직/간접적으로 사용가능한 예제 자료구조 알고리즘 등 직/간접적으로 사용가능한 예제. Contribute..