I'll never know if I never commit

머지소트 머지소트의 원리는 '분할정복'이다. 1) 배열을 더이상 쪼갤 수 없을 때까지 쪼갠다 2) 쪼개진 배열을 병합, 정렬한다. 가장처음엔 1개로 이루어진 배열 두개를 정렬하여 길이가 2인 배열을만들고, 이를 또 길이가 2인 배열 두개를 병합/정렬하여 길이가 4인 배열을 만든다..-> 배열이 모두 병합/정렬될 때까지 한다. 머지소트는 재귀의 깊이가 O(log2N)이고, 각 재귀 당 비교 및 스왑연산이 평균적으로 n번수행된다고 보면, 시간복잡도는 O(Nlog2N) 이 되겠다. 머지소트의 최대 단점이라하면, in place 알고리즘이 아니라는 것이다. 즉, 머지소트는 외부의 다른 배열을 만들고, 그 배열에서 정렬한 후, 정렬된 값을 다시 원래의 배열로 옮겨줘야한다. public class Sort { st..

1. 선택 소트 void selection_sort(int list[], int n) { int least=0, i=0, j=0; for (i = 0; i < n-1; i++) { least = i; for (j = i + 1; j < n; j++) { if (list[j] < list[least]) least = j; //가장 작은 값 찾기 } swap(list, i, least); } } 1) 인덱스 0 부터 n-1까지 차례대로 해당 인덱스에 올 i번째로 작은 값을 찾는다. 2) 이를 위해 내부 루프는 i보다 1큰 인덱스부터 시작하여 맨 끝 인덱스까지 본다. 선택 소트는 , 인접요소들 끼리 차례대로 정렬하는 것이 아니라, 앞의 인덱스에 있는 요소와 뒤의 랜덤의 요소 (가장 작은 값)을 정렬하는 것으로..

'우선순위 큐'란 ? 우선순위큐는, 큐에 우선순위가 있는 것으로, 무작정 맨 앞의 값을 pop하는 것이 아니라, 가장 높은 우선순위의 값을 pop해주는 큐를 말한다. 이러한 우선순위 큐를 구현하는 가장 좋은 방법은 바로 'Heap'이다. 일반 배열이나, 연결리스트를 사용 할 수 있겠지만, 일반 배열/ 연결리스트를 사용할 경우, 값을 올바른 위치에 넣는 시간 혹은 정렬 시키는 시간이 O(n)이므로, 비효율적이다. 반면 heap는 O(log2N)의 시간 효율을 가지므로, 다른 방법보다 유리하다. 왜 heap가 O(log2N)의 시간효율을 갖는지 알기 위해서는 heap의 구현법을 알아보자. heap는 배열을 이용한 완전이진트리로 구현하게 된다. 완전 이진트리의 높이는 요소가 n개일 때 log2N이 된다. he..

이진탐색트리 (Binary Search Tree)란, 기존의 이진 트리가 변형된 형태이다 . 이는 말 그대로 '탐색'을 더 효율적으로 하기 위해 설계된 자료구조로, 맨 위 노드를 기준으로 왼쪽은 맨 위 노드보다 작은 데이터가, 오른 쪽은 맨 위 노드보다 큰 데이터가 삽입된다. 또한, 모든 subtree는 이진탐색트리이므로, 모든 subtree에도 이러한 법칙이 적용된다. 그러면 이진탐색트리의 cpp 코드를 하나씩 살펴보도록 하겠다. 1. 트리 노드 타입 class BSTNode { public: int key; BSTNode* left =NULL; BSTNode* right = NULL; }; 2. BST 클래스 class BST { public: BSTNode* root = NULL; void inse..