개인공부용123 프로그래밍 블로그

FixHeapFast를 사용해서 HeapSort를 구현해봤습니다. 각 함수별 기능 설명 swap함수 : 두 배열의 원소를 바꿔주는 함수입니다. parent, left_child, right_child는 각각 부모 , 왼쪽 자식, 오른쪽 자식노드를 찾아주는 함수입니다.(없어도 무방합니다.) FixHeapFast 함수 : 이 함수는 down Heap을 실행하는 함수로 시작노드에 있는함수를 있어야할 위치까지 내리는 함수입니다. 단 이떄 FixHeapFast함수는 promote함수를 이용해서 높이의 절반 만큼씩 내려가게 됩니다. 그리고 vacant가 잘못 내려갔을경우 BubbleUpHeap함수를 이용해서 있어야할 위치로 올려줍니다. Promote 함수 : vacant를 높이의 절반만큼 내리는 함수입니다. (한칸..

백준 9426문제는 N개의 원소중에서 K개의 부분집합원소의 중앙값들의 합을 구하는 문제입니다. 이 문제는 세그먼트 트리를 이용해서 풀었습니다. 세그먼트 트리의 각노드에는 노드들의 갯수를 저장하고있습니다. (리프 노드에는 해당 노드가 세그먼트 트리에있는지 없는지를 표시) 업데이트시 1, -1로 원소를 추가 삭제 가능합니다. 쿼리함수를 이용해서 서브트리에 대한 중간값에 해당하는 값을 찾을수있습니다. 세그먼트 트리는 보통 포화 이진트리이므로 값이 N개일 떄 높이는 O(logN)입니다. 즉 하나의 중간값을 찾는데 걸리는시간은 O(logN)이 걸립니다. 그러므로 세그먼트 트리를 이용한 최악의 경우 시간 복잡도는 약 O(NlogN)입니다. Worst Case time Complexity = O(NlogN) incl..

MergeSort를 구현했습니다. 각 함수별 기능 설명 Merge : 분할된 두 부분을 합쳐주는 기능을합니다. MergeSort : 분할 정복을 이용해서 각각 Sort를 실행하는 함수입니다. 위 사진과 같이 분할 정복을 통해서 머지소트가 실행됩니다. Worst Case time Complexity 머지소트의 최악수행시간의 점화식은 W(n) = W(n/2) + W(n/2) + W(merge)(n)입니다. 이를 Master theorem을 이용해서 점화식을 풀면 O(nlogn)이라는 최악수행시간이 나옵니다. 즉 MergeSort의 최악수행시간 = O(nlogn) #include #include using namespace std; void Merge(vector& arr,int start, int mid, ..