Merge/Heap/Quick Sort같이 Comparsion을 이용한 Sorting의 경우 최저 하한선이 O(NLogN)가 된다. (Decision Tree를 통해 시각화 하면 -> n개 element에 대해서 Decision Tree의 Height 만큼인 LogN번 Comparision 해야 되기 때문.) 하지만 Counting/radix/bucket Sort의 경우 저러한 하한선을 깨고 (경우에 따라서) O(N) 안에 정렬을 마무리 할 수 있다! 이는 정수의 범위 제한/분포 같은 추가 정보를 이용한 것이다. Counting Sort Counting Sort는 n개의 요소들이 0 to k의 정수라고 가정할 때 작동한다. 그럼 한번씩 순회하면서 0 to k의 element가 각각 몇개인지 세고, 그 ..

Quick Sort는 Merge Sort와 비슷하게, 아래와 같이 분할 정복을 사용한다.Divide : 배열 A[p..r]을 A[p..q-1]과 A[q+1..r]로 나눈다.Conquer : 재귀를 이용해서 배열A[p..r]과 A[q+1..r]에 대해서 Quick Sort를 시행한다.Combine : 서브 배열들이 이미 정렬된 관계로 딱히 합칠 필요는 없다. 그리고 이는 아래와 같은 의사 코드로 표현해 낼 수 있다.// Let A -> matrix and p,r -> indexPartition(A, p, r) x = A[r] i = p-1 for j = p to r-1 if A[j] 대충 하나를 Pivot으로 잡아서 서브어레이를 만들어 내고, 정렬을 때린 다음 다시 서브 어레이를 돌린다고..

일단 대충 요약하자면 Heapsort는 O(nlogn)의 시간복잡도를 자랑한다. 근데 그전에 Heap이 뭔지는 설명해야 할거 아닌가? Heap데이터 구조인 Heap은 거의 CBT로 볼수있는 array object라고 할 수 있겠다. 위 사진에서 볼 수 있듯 어떤 노드의 요소는 배열의 어떤 요소에 대응될 수 있을 것이다. 대충 배열 이름을 A라고 해보면, 트리의 루트는 A[1]이 될 것이고 이런식으로 치면 아래와 같이 PARENT/LEFT/RIGHT NODE를 구할 수 있을 것이다. Parent : [ i/2 ]Left : 2iRight : 2i + 1when i is 0>=. 그리고 Binary한 Heap에는 두가지 종류가 있는데, 하나는 max-heap이고 다른 하나는 min-heap이 되..

내 PS....이제 어디로 가야하오..

Explict Graph데이터를 저장할 공간을 직접 할당하여 정점과 간선을 기록하는 방식이다.인접 행렬, 인접 리스트, 포인터 기반 연결 리스트를 통해서 직접 데이터를 구현하는 방식.A와 B가 연결되어있다라는 정보를 메모리에 물리적으로 저장하는 셈이다.노드간의 관계를 직관적으로 파악할 수 있으나, 노드 수가 많아질수록 메모리 사용량이 아작난다. (O(V^2))Implict Graph데이터를 저장하는 데신, Rule/Function/Numbers...등을 통해 실시간으로 간선을 계산하는 방식이다.수식이나 조건문을 이용해서 "표현"한다.메모리에 간선 정보를 저장하지 않고, 탐색 과정에서 "다음 노드는 어디인가?"를 로직으로 산출한다.메모리 효율이 아-주 좋고, Locality가 보장됨에 따라 Cache hi..

5개월이라는 시간이 흐르면 자료구조/알고리즘 기억해 놨던게 사라지는 기현상이 있어서... 이진 탐색과 매개변수 탐색에 대해 이야기를 해보려고 한다. 사실 Binary Search는 구현 자체는 크게 어렵지도 않고, 개념적으로도 마찬가지로 어렵지도 않다. 업다운 게임을 생각해 보면 편한데, 1~100까지 수 중에 하나를 고르라 하면 50이 먼저 나올게 당연한 것 아닌가? 마찬가지로 이진 탐색도 정렬되어 있는 수 중에서 (혹은 범위가 지정되어 있는 수 중에서) Up-Down 게임을 열심히 지지고 볶으면 된다. 물론 이진 탐색의 경우 수 중에서 "해당 값"이 반드시 존재하는 경우에 사용하고, 만약 "범위"로 검색하고 싶으면 매개변수 탐색이라는 것을 동원해야 한다. #include #include using ..