CS 공부/Algorithm, Data Structure (재정리) 검색 결과

해당 글 10건

MST, 최소신장트리

Minimum Spanning Tree 그래프 G 의 spanning tree 중 edge weight 의 합이 최소인 spanning tree를 말한다. 여기서 말하는 spanning tree란 그래프 G 의 모든 vertex 가 cycle 이 없이 연결된 형태를 말한다. Kruskal Algorithm 초기화 작업으로 edge 없이 vertex 들만으로 그래프를 구성한다. 그리고 weight 가 제일 작은 edge 부터 검토한다. 그러기 위해선 Edge Set 을 non-decreasing 으로 sorting 해야 한다. 그리고 가장 작은 weight 에 해당하는 edge 를 추가하는데 추가할 때 그래프에 cycle 이 생기지 않는 경우에만 추가한다. spanning tree 가 완성되면 모든 ver..
CS 공부/Algorithm, Data Structure (재정리) 2021. 4. 11. 20:25

Heap Sort 및 Heap

Heap 이란? 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리 자료 구조이다. 완전 이진 트리이기 때문에 배열을 이용하여 손쉽게 구현할 수 있다. max - heap은 부모가 자식보다 항상 큰 자료구조이고, min - heap 은 부모가 항상 자식보다 작은 자료 구조이다. 이를 응용하여 우선 순위 큐를 구현할 수 있다. 새로운 원소가 삽입 될 때나 root 원소를 추출하고 나서 heap 규칙을 따르도록 원소의 위치를 바꾸는 과정을 heapify 라 불리며 log n 이 소요 된다. 새로운 원소는 항상 힙 구조의 제일 끝 원소로 추가되며 heapify 과정을 통해 자신의 자리를 찾아 올라가고, root 값인 min, max 값을 뽑고서는 제일 끝 원소를 root으로 옮기고 h..
CS 공부/Algorithm, Data Structure (재정리) 2021. 4. 7. 00:07

Binary Tree

Tree 계층적 관계 표현 루트 노드를 제외하고 모든 노드는 단 하나의 부모 노드만을 갖는다. 이진 트리는 배열과 연결 리스트로 표현 가능. 이진 트리란? 루트를 기준으로 left, right subtree가 존재하고, 두 서브트리 모두 이진트리여야 한다. 따라서 공집합도 노드로 인정한다. 각 노드가 최대 2개 까지만 자식 노드를 갖을 수 있다. 이진 트리의 종류 정 이진 트리 ( FULL ) 리프 노드를 제외하고 2개의 자식 노드를 갖는다. ( 자식이 있다면 2개고 아니면 없다! ) 완전 이진 트리 ( COMPLETE ) 왼쪽에서 오른쪽으로 순서대로 차곡 차곡 쌓인다 포화 이진 트리 ( PERFECT ) 리프 노드 빼고 모든 노드가 2개의 자식 노드를 갖으며, 리프 노드들은 같은 레벨에 위치한다. 이진..
CS 공부/Algorithm, Data Structure (재정리) 2021. 4. 7. 00:00

Stack, Queue

Stack 스택은 Last In First Out 으로, 요소가 들어올 때마다 기존 요소들에 차곡차곡 쌓아 올린 형태의 자료구조이며, 제일 마지막으로 들어온 요소 즉, Top 이 가르키는 요소에만 접근, POP을 할 수 있다. 비어있는 상태의 스택을 pop 할 때 stack underflow, 꽉 찬 스택에 push 할 때 stack overflow를 발생시킨다. 배열로 구현할 시에, top 인덱스를 활용하여 여러 메소드를 구현한다. 스택의 활용 예시 운영체제의 메모리 스택 웹 브라우저 방문기록의 뒤로가기 역순 문자열, 후위 표기법 계산, 수식의 괄호 검사 등 DFS ( 함수의 재귀, 메모리 스택을 활용 ), 미로찾기 2개로 큐 구현하기. Queue 큐는 First In First Out 으로, 먼저 들..
CS 공부/Algorithm, Data Structure (재정리) 2021. 4. 6. 23:56

Insertion Sort

Insertion Sort void insertionSort(int arr[], int n){ int tmp; int idx; for(int i=1;i= 0 && arr[idx] > tmp){ arr[idx+1] = arr[idx]; --idx; } arr[idx+1] = tmp; } } 삽입 정렬은 평균, 최악의 시간복잡도가 O(n^2) 로 버블, 선택 정렬과 같이 느리지만 직관적인 알고리즘으로 여겨지지만, 최선의 경우 O(n)이기도 하며, 전체적으로 위 두 알고리즘보다 빠른 정렬기법이다. 배열의 인덱스가 0부터 시작될 때, 1 ~ n-1 라운드가 진행되며, i 라운드에 i 번째 원소의 위치를 찾는다. 이 때, 0 ~ i 인덱스까지의 요소들은 정렬되어 있다고 가정하며 역순으로 탐방하며 자신의 위치를 찾..
CS 공부/Algorithm, Data Structure (재정리) 2021. 4. 6. 23:55