Sweet Sixteen Bars Sweet Sixteen Bars

자료구조 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 구현 일반적으로 배열로 구현 (완..

Function / isPrime - 소수판별 목표 정수 num이 소수인지 판별하기 소수 : Prime Number - 1 보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 자연수, 무리수 구현 github GitHub - keeplo/SwiftTools: 자료구조 알고리즘 등 직/간접적으로 사용가능한 예제 자료구조 알고리즘 등 직/간접적으로 사용가능한 예제. Contribute to keeplo/SwiftTools development by creating an account on GitHub. github.com //Swift 5 // Created by Yongwoo Marco 21.05.31 import Foundation func isPrime(num: Int) -> Bool { if(num..

자료구조 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..

자료구조 04 / Hash Table 정의 해쉬 테이블 키(Key) 값을 주어질때 Hash Function을 거처 하나의 같은 길이(크기)의 데이터(Value)를 저장하는 데이터 구조 용어정리 Hash : 임의 값을 고정 길이로 변환하는것 Hashing Function : Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수 Hash Value (Hash Address) : Key를 해싱 함수로 연산해 해쉬 값을 알아내 해쉬 테이블에서 해당 Key에 대한 데이터 위치 Slot : 한 개의 데이터를 저장할 수 있는 공간 * 저장할 데이터에 대해 Key를 추출 할 수 있는 별도 함수도 존재 할 수있음 일반적인 예 (Swift) : Dictionary Dictionary 사용법 간단한 정리 - ..