불곰 불곰

공부/자료구조

• Sorting (Heap, Quick, Merge Sort)

  공부/자료구조 2018. 9. 30. 23:49

  Heap SortHeapTree에서의 Heap을 사용 (Max Heap 또는 Min Heap)따라서 complete binary tree 임Max Heap일 때 parent node는 child node(subtree)의 key보다 무조건 큼binary search tree가 아님Tree의 Heap은 정렬을 위함이 아닌 Insert와 Delete를 위함Max(Min) Heap의 내용은 Heap 에서 확인 1. Max(Min) Heap을 만든 다음 모든 데이터를 넣음2. (Max Heap이라 할 때) 만든 heap tree에서 root node를 지우고 정렬하고자 하는 list에 지운 root node를 넣음3. (Max Heap이라 할 때) heap tree를 재조정해서 루트를 결정한 다음, 다시 루트를..

• Sorting (Bubble, Selection, Insertion Sort)

  공부/자료구조 2018. 9. 30. 13:49

  대부분 정렬의 시간복잡도는 O(n·logn)와 O(n²) 사이임특별한 경우 O(n)까지 가능 Internal sorting - main memory 에서 일어나는 정렬External sorting - secondary storage(하드디스크) 에서 일어나는 정렬Bubble Sort이웃되는 값끼리 비교하여 자리를 변경해나가는 방식기본적으로 O(n²). 이미 정렬이 되어 있을 경우는 O(n)예시예시2Selection Sortarray에서 가장 큰 수를 찾은 다음, 찾은 수를 어레이의 맨 끝인 n자리에 놓는다.다음 큰수를 찾은 다음, 어레이의 n-1자리에 넣는다. 이때 찾은 수와 해당 자리에 있는 수의 자리를 바꾼다.O(n²)의 performance가 나옴 bubble sort와 똑같이 O(n²)이지만 bu..

• 트리 탐색 방법 (Tree traversal)

  공부/자료구조 2018. 9. 28. 13:56

  PreorderVisit the root.Visit the left-subtree.Visit the right-subtree.InorderVisit the left-subtree.Visit the root.Visit the right-subtree.PostorderVisit the right-subtree.Visit the left-subtree.Visit the root.Breadth First Search(BFS) or Level order traversalsstarts at the tree root and explores the neighbor nodes first, before moving to the next level neighbors.Depth First Search(DFS)예시

• Spanning Tree (Prim 알고리즘, Kruskal 알고리즘, Dijkstra 알고리즘)

  공부/자료구조 2018. 9. 26. 18:34

  Spanning TreeN개의 노드들의 connected graph에서 얻을 수 있음depth-first traversal 또는 breadth-first traversal 을 통해 확인N개의 node와 N-1개의 edges로 된 Treecycle은 그래프로부터 제거됨 - 한번 방문한 노드는 다시 방문하지 않기에 cycle이 생길 수 없음한개 이상의 spanning tree는 같은 그래프에서 구할 수 있음추가정보그래프가 connected 일 때, dfs나 bfs는 암묵적으로 그래프 G의 edge를 두개의 집합으로 분리T(for tree edges): edge의 집합으로 사용되거나 search 도중에 방문N(for nontree edges): 남아있는 edge의 집합T의 edge는 G의 모든 vertex들을..

• Graph

  공부/자료구조 2018. 9. 26. 15:49

  Graph트리는 그래프의 특수한 케이스그래프는 다양한 문제를 모델링 하는 것과 문제를 해결하기 위해 알고리즘을 고안하는데 유용 용어vertex, vertices(vertex의 복수형): 트리의 Node와 동일개념root node와 leaf node가 아닌 모든 노드edge: 트리의 link와 동일개념undirected edge ( = undirected graph)directed edge ( = directed graph)단방향, 양방향in-degree (해당노드로 들어오는 방향성 있는 edge), out-degree (해당노드에서 나가는 방향성 있는 edge)weighted edge ( = (directed or undirected) weighted graph)서울 - 제주도 와 서울 - LA의 wei..

• AVL Tree

  공부/자료구조 2018. 8. 17. 23:09

  BST에서 위와 같은 Skewed Tree의 경우 복잡도가 O(n)이 나오는 한계점을 해결하기 위해 AVL Tree가 고안됨. AVL 은 해당 자료구조를 만든 사람의 앞글자를 하나씩 따서 만든 것(..)AVL Tree 예시AVL TreeNot AVL Tree용어노드의 height: hbalance factor: bf (왼쪽 서브트리의 height - 오른쪽 서브트리의 hegiht)empty height: -1특징AVL 트리는 BST이면서 동시에 균형을 유지하고 있음모든 노드의 왼쪽과 오른쪽 서브트리의 높이 차이가 1 이하 (왼쪽과 오른쪽 서브트리의 height 계산 결과가 1, 0, -1 이외라면 해당 트리는 AVL 트리가 아님 - 만약 height가 없는 경우는 -1) 즉, 모든 노드들은 balance..

• Binary Search Tree

  공부/자료구조 2018. 8. 15. 18:04

  Binary Search Tree(BST - 이진검색트리) 는 비어있거나 아래의 속성을 만족하는 binary tree 입니다. 자세하게 Binary Search (이진 검색)과 Linked List를 결합한 자료구조입니다. 이진 검색의 검색능력을 유지하면서 빈번한 값의 삽입, 삭제가 가능하도록 고안되었습니다. 이진검색의 경우 검색에 소요되는 시간복잡도는 O(log₂n)으로 빠르지만 자료 입력, 삭제가 불가능합니다. linked list의 경우 자료 입력, 삭제에 필요한 시간복잡도는 O(1)로 효율적이지만 탐색하는 데에는 O(n)의 복잡도가 발생합니다.정의각각의 모든 node 들의 key는 중복된 값이 아님 (unique)기존의 binary tree는 순서가 없지만 BST는 순서가 존재parent node..

• Heap

  공부/자료구조 2018. 8. 13. 21:07

  Heap은 Complete Binary Tree를 기본으로 가지는 자료구조일반적으로 array로 구현하는 것이 좋음Heap 은 최댓값 또는 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안됨시간복잡도: O(log₂N)Heap은 다음과 같은 속성(property)를 만족함A가 B의 부모노드이면 A의 키값과 B의 키값 사이에는 대소관계가 성립종종 priority queue를 보충하는대에 사용종류max heap: root노드가 가장 큰 수min heap: root노드가 가장 작은 수Max Heap부모노드의 키가 자식노드의 키보다 항상 큼 Node Insertionmax heap에서 노드 추가는 말단의 맨 오른쪽의 leaf node에 자리를 하나 만들고 해당 노드에 값을 대입한 다음 parent node와 값을 ..

• Binary Tree

  공부/자료구조 2018. 8. 1. 22:13

  degree가 최대 2인 트리i번째 level에 나올 수 있는 노드의 최대 개수는 2^(i - 1)주의 할 것은 전체 tree의 노드 최대 개수 또는 i번째 level까지 전체 노드의 개수가 아닌 i번째 level만 단독으로 보고 있음.k가 tree의 depth일 때, 최대 노드의 개수는 : 2^k -1위 그림에서 2번째 level의 노드의 최대 개수는 2^(2-1) = 2개이고, depth는 2^2-1 = 3개, height는 2^3 - 1 = 7개임 binary tree에는 skewed tree, complete binary tree, full(perfect) binary tree가 있음Full (Perfect) Binary Tree마지막 레벨까지 노드가 꽉 차게 있는 트리 Complete Binar..

• Tree

  공부/자료구조 2018. 7. 31. 22:04

  Tree 구조 트리는 위와 같은 구조를 갖고 있습니다.용어node: 트리에서 데이터를 의미branch(link): 노드와 노드를 연결root node: 최상위 노드interior node: 자기자신 아래에 연결된 노드가 있는 형태leaf node: 자기자신 아래에 노드가 더이상 연결되어있지 않은 형태parent: child 노드들이 연결되어 있는 상위 노드child: 부모노드 아래에 연결되어 있는 노드sibling: 부모노드 아래에 존재하며 동일한 레벨에 있는 노드degree (노드의 degree): 자기자신 아래에 연결된 노드가 몇개가 있는지depth: 루트에서 어떤 노드에 도달하기까지 거쳐야 하는 branch(link)의 수level: 트리의 특정 depth를 가지는 노드의 집합height: 루트노드..