풀풀풀

_Spanning Tree 정의 Spanning Tree(신장트리)는 아래의 속성을 만족하는 그래프를 말한다. 원래의 그래프의 모든 노드를 포함 모든 노드가 서로 연결되어 있음 트리의 속성을 만족 ( 사이클이 존재하지 않음) 즉, 그래프의 최소 연결 부분 그래프이다. 최소 연결 = 간선의 수가 가장 적다 N개의 노드를 가진 그래프 최소 간선의 수 : N-1 (N-1)개의 간선으로 == 최소 간선으로 연결되어 있으며 트리의 형태이면 Spanning Tree _Minimum Spanning Tree (MST) 가능한 Spanning Tree 중에서 간선의 가중치 합이 최소인 Spanning Tree 위 사진에서 첫 번째 그래프의 경우 2개의 MST를 가질 수 있다. 두번째, 세번째 트리가 모두 가중치의 합이..

정렬 알고리즘 종류정렬 종류 정렬 방법 최고 효율 평균 효율 최악 효율 특징 버블 정렬 교환 방식 n^2 n^2 n^2 구현하기 쉽다. 선택 정렬 교환 방식 n^2 n^2 n^2 삽입 정렬 삽입 방식 n n^2 n^2 코드가 간단하고 n의 수가 작을 때 유리하다. 병합 정렬병합 방식n x log(n)n x log(n)n x log(n)입력자료를 분할하여 병합하므로 별도의 기억장소가 필요하다.퀵 정렬 나누기(부분집합) 방식 n x log(n) n x log(n) n^2 분할한 입력자료를 재귀적으로 반복하여 정렬하므로 빠르다. 힙 정렬 선택 방식 n x log(n) n x log(n) n x log(n) 입력자료를 힙이라는 자료형을 유지하도록 선택하여 정렬한다. 셸 정렬 삽입 방식 n n^1.5 n^2 삽입..

힙 정렬 최대 힙 트리나 최소 힙 트리를 구성해 정렬하는 방법으로, 내림차순 정렬을 위해서는 최대 힙을 구성하고 오름차순 정렬을 위해서는 최소 힙을 구성하면 된다. 1. 정렬해야할 n개의 요소들로 최대힙(완전 이진 트리 형태)를 만든다. 내림차순 기준 정렬2. 다음으로 한 번에 하나씩 요소를 힙에서 꺼내서 배열의 뒤부터 저장하면 된다.3. 삭제되는 요소들(최댓값부터 삭제)는 값이 감소되는 순서로 정렬되게 된다. - 완전 이진 트리를 기본으로 하는 힙 자료구조를 기반으로한 정렬방식이다.- 힙은 1차원 배열로 쉽게 구현될 수 있다.- 가장 유용한 경우는 전체 자료를 정렬하는 것이 아니라 가장 큰 값이나 작은 값을 구할 때, 최대 k만큼 떨어진 요소들을 정렬할 때 이다. 시간 복잡도최선/최악/평균 모두 O(n..

퀵 정렬 퀵소트는 divide and conquer 방법을 통해 정렬한다. 리스트 가운데서 하나의 원소를 고른다. 이렇게 고른 원소를 피봇이라고 한다.피봇 앞에는 피봇보다 값이 작은 모든 원소들이 오고, 피봇 뒤에는 피봇보다 값이 큰 모든 원소들이 오도록 피봇을 기준으로 리스트를 둘로 나눈다. 이렇게 리스트를 둘로 나누는 것을 분할이라고 한다. 분할을 마친 뒤에 피봇은 더 이상 움직이지 않는다.분할된 두 개의 작은 리스트에 대해 재귀적으로 이 과정을 반복한다. 재귀는 리스트의 크기가 0이나 1이 될 때까지 반복된다.[ 위키백과 참조 ] 시간 복잡도 ( T(n) 은 n의 리스트를 정렬하는데 걸리는 시간 ) 평균적으로 O(nlog n) 의 시간복잡도를 갖는다. 최선의 경우 : O(nlog n) 최악의 경우 ..

트리Node : 트리를 구성하고 있는 각각의 요소를 의미Edge : 트리를 구성하기 위해 노드와 노드를 연결하는 선을 의미Root Node : 트리 구조에서 최상위에 있는 노드를 의미Terminal Node ( Leaf Node ) : 하위에 다른 노드가 연결되어 있지 않은 노드를 의미Internal Node : Leaf 노드를 제외한 모든 노드로 루트 노드를 포함 Level : 각 층별로 매긴 숫자로 루트노드의 레벨은 0이고, 최고 레벨을 높이라고 한다. Binary Tree- 루트노드를 중심으로 두 개의 서브트리로 구성되어 있다.- 두 개의 서브트리도 모두 이진트리여야 한다. Full Binary Tree / Complete Binary Tree모든 레벨이 꽉 찬 이진트리를 말한다.포화이진트리는 노드..

red-black tree자가 균형 이진 탐색트리로써, 대표적으로는 연관 배열 등을 구현하는 데 쓰이는 자료구조.트리에 n개의 원소가 있을 때 최악의 경우에도 일정한 O(log n)의 시간복잡도로 삽입, 삭제, 검색을 한다.또, 레드-블랙 트리에서는 리프 노드들은 비어있고, 자료를 가지고 있지 않다. 1. 특징트리의 모든 노드의 색은 BLACK or RED루트 노드의 색은 무조건 BLACK 모든 리프 노드(자식이 없는 노드)의 색은 BLACK RED 노드의 자식들은 모두 BLACK , BLACK 노드의 자식들은 BLACK or RED루트 노드에서 모든 리프 노드 사이에 있는 BLACK 노드의 수는 모두 동일> BLACK 은 연달아 올 수 있지만, RED 는 연달아 올 수 없다. 2. 연산[ 회전 ] > ..