Kim-Baek 개발자 이야기

Heap Sort는 Heap 이라는 자료구조를 이용해 정렬을 하는 알고리즘이다. Heap 이란 완전 이진 트리 형태로 Paren Node 는 Child Node 보다 반드시 큰(작은) 값을 가진다. Heap Sort의 경우 항상 O( N log(N) ) 의 시간복잡도를 가진다. 우선 모든 원소를 최대(최소) Heap에 삽입한다.( O(logN) ) Heap 트리의 최대(최소) 값을 출력한다.( O(1) ) 최대(최소) 값을 제거하고 Heap을 재배열 한다.( O(logN) ) Heap이 빌때가지 반복한다.( O(N) ) Stable 을 만족하지 않는다. #include #include #include using namespace std; int main() { vector v = { 3,1,4,1,5,9..

Quick Sort는 데이터내의 Pivot 값을 정하고 그 기준으로 두 개의 부분집합으로 나눈다. 한쪽은 Pivot보다 작은 값을 다른 한쪽은 Pivot보다 큰 값으로 나눈다. 더 이상 쪼갤 부분집합이 없을 때까지 재귀적으로 진행한다. Quick Sort는 어떤 Pivot 값을 고르는지에 따라 성능이 결정된다. 가장 이상적인 Pivot은 전체 데이터를 절반씩 쪼갤 수 있어야 한다. 이 경우 O(N log(n)) 의 복잡도를 가진다. 최악으 경우는 집합의 최소(최대) 값을 Pivot으로 고른 경우이다. 그러면 한쪽의 부분집합은 비어있고, 다른 한쪽은 n-1개의 원소가 있다(pivot 제외). 이 경우 재귀호출 횟수가 O(N)이며, 최악의 경우 O(N^2) 의 복잡도를 가진다. 하지만 평균적으로 O(N lo..

Merge Sort는 Divide and Conquer 알고리즘 기법이다. Merge Sort의 경우 항상 O( N log(N) ) 의 시간복잡도를 가진다. 성능은 전반적으로 Quick Sort 에 비해 떨어진다. Stable 하다 추가 메모리 공간(Not in-place)이 필요하다. C++의 stable_sort 가 Merger Sort 로 구현되어 있다. #include using namespace std; void merge_sort(int ary[], int left, int right); void merge(int ary[], int left, int mid, int right); int* temp; int main() { int ary[] = { 6,4,2,7,9,7,6,4,4,1,0 }; ..

Insertion Sort는 단순한 정렬 알고리즘 중 하나이다. 한번의 한 원소씩 이미 정렬된 다른 원소들과 비교하여 올바른 위치에 삽입하는 정렬이다. 삽입 정렬은 이미 정렬되어 있을때 O(N) 의 효율이다.(Best Case) Average, Worse Case의 경우 O(N^2) 이다. Bubble Sort에서 발전된 형태이다.(비교 횟수를 줄였다) 소량의 데이터를 처리할때 좋다. Stable 하다 무작위로 정렬된 많은 데이터의 효율이 매우 안좋다. #include using namespace std; void insertion_sort(int data[], int size); int main() { int data[] = {3,7,9,4,5,1,3,4,6,9}; insertion_sort(data,..

알고리즘 문제에서 정렬(Sort)는 중요한 기술이다. 여러가지 정렬 알고리즘이 있지만 기본적인 것 부터 하나하나 알아보자. 선택 정렬 (Selection Sort) 단순한 정렬 알고리즘 중 하나이다. 배열의 첫 번째 원소에서 시작하여 배열 전체를 훓으면서 작은(큰) 값을 찾아 첫 번째 원소와 바꿔준다. 이 작업을 (배열의 길이 - 1 ) 만큼 진행한다. 선택 정렬은 Best, Average, Worst Case 모두 O(N^2) 의 효율이다 - 원소를 바꾸는 횟수가 최대 n -1 이다. 즉 원소를 바꾸는 과정에서 많은 비용이 드는 경우에 효율적일 수 있다. - 선택 정렬은 다른 알고리즘에 비해 효율(performance) 가 좋지 않다. - stable을 만족하지 않는다. #include using na..

BFS는 너비우선탐색 이라고 블리는 Graph 알고리즘 중 하나이다. - BFS 는 일반적으로 Queue를 이용해 구현 - 시작 정점과 인접한 모든 정점을 방문하는 방법 - 얻어진 해가 최단 경로가 된다는 것을 보장 - 경로가 매우 길 경우에는 많은 저장 Memory 가 필요 C++를 이용해 BFS를 구현 #include #include #include using namespace std; vector* vertex; bool* checked; void bfs(int st); int main() { int n, m, s; int from, to; cin >> n >> m >> s; vertex = new vector[n + 1]; checked = new bool[n + 1]; for (int i = 0..

Tree Traversal Tree Traversal 은 트리 순회이다. Tree 자료구조에서 각각의 노드를 정화히 한 번만, 체계적으로 방문하는 과정이다. 전위 순회(PreOrder Traversl) Root 노드부터 탐색하기 시작한다. root => sub left => sub right PreOrder Traversal은 가장 깊은 왼쪽 노드부터 탐색하기 때문에, 우리가 잘 알고 있는 DFS 라고 생각하면 된다. def preOrder(node): print(node, end = ' ') if node.left != null: preOrder(node.left) if node.right != null: preOrder(node.right) 중위 순회(InOrder Traversal) 왼쪽 서브 트리..