한국으로/알고리즘과 자료구조3 병합 정렬 (Merge Sort) Merge SortSample Code 1 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152void merge_sort(int s, int e){ int idxtmp, idx1, idx2, m; if (s == e) return; m = (s + e) / 2; merge_sort(s, m); merge_sort(m + 1, e); idx1 = s, idx2 = m + 1, idxtmp = s; while (idx1 2018. 7. 4. 힙 정렬 (Heap Tree Sort) 힙 정렬 (Heap Tree Sort)HEAP TREE란? (HEAP SORT) 최소값 또는 최대값을 빠른 시간 안에 접근할 수 있도록 만들어진 자료구조. 트리의 최상위 노드는 항상 최소값 또는 최대값을 저장하고 있음. PUSH 프로세스 이후에 POP 으로 정보를 빼오면 SORTING된 상태로 저장됨. (가장 최소값 또는 최대값을 콜해옴과 동시에 트리의 최상위 노드를 그 다음 최소값 또는 최대값으로 업데이트하기 때문) 따라서, 부모 노드의 우선순위가 자식 노드의 우선순위보다 항상 높다! PUSH 함수 데이터의 추가. 새로 추가된 노드는 PARENT NODE 와 경쟁함. 만약 노드가 PARENT NODE 보다 우선하면 SWAP. RECURSIVE until PARENT > 0 POP 함수 데이터 꺼내오기... 2018. 7. 3. 세그먼트 트리 (Segment Tree) 세그먼트 트리 (Segment Tree)세그먼트 트리란?구간에 대한 정보를 저장함.특정 구간의 최적화된 답을 구하는 문제에 사용.부분 구간의 최적 답들 중에서 최적 답을 구할 수 있음. 자료 저장: O(n log n)특정 구간 최적해 검색: O(log n + k) SUM TREE를 배열 기반으로 짜면, 노드마다 자식 노드의 TOTAL SUM 정보를 저장하게 됨. 구현TREE 초기 자료 구성:원본 데이터를 인자로 받아서 LEAF NODE를 찾아 하나씩 저장하는 프로세스. 배열의 크기 잡는 법:예를 들어 데이터가 1000개라면, 1000 < 2^10 이므로, TREE LEVEL은 N = 11개가 만들어져야 함. TREE[1 2018. 7. 3. 이전 1 다음