자료구조, 알고리즘3 [알고리즘][탐색][C/C++] Lower Bound, Upper Bound Lower Bound, Upper Bound 특징 Lower Bound : 원하는 값 k 이상이 처음 나오는 위치를 찾기 Upper Bound : 원하는 값 k 초과가 처음 나오는 위치를 찾기 Binary Search (= 원하는 값 k의 위치 찾기)에서 파생된 index search 알고리즘 시간복잡도 : O(logN) Lower Bound, Upper Bound 과정 이해하기 이 2가지 알고리즘의 결과는 아래 그림처럼 표현할 수 있다. 그렇다면, 위의 결과를 어떻게 구현할 수 있을까? 먼저 Lower Bound 구현 과정을 확인해보자. [ Lower Bound 과정 ] 1. 배열의 처음과 끝을 각각 s와 e로 설정한다. 2. s와 e의 중간인 mid index를 계산한다. 3 - ①. K A[mid].. 2023. 1. 24. [알고리즘][정렬][C/C++] Heap Sort (우선순위 큐) Heap Sort (우선순위 큐) 특징 Tree 구조(완전이진트리)를 활용하는 알고리즘 Heap에 저장된 상태는 완전히 정렬된 상태가 아니고, Heap에서 Pop할 때, 정렬이 완성된다. 우선순위 큐 (정의된 우선순위에 따라 처리되는 큐) 를 Heap으로 보통 구현한다. 시간복잡도 : O(N*logN) N 크기의 배열을 이용하여 구현한다. * 완전 이진트리 (Complete Binary Tree) : 이진 트리의 원소가 왼쪽부터 채워지는 트리를 말한다. : 아래 그림 중, A, C, D에 해당 * Heap : 아래 그림 중 A, D에 해당 : A는 Min Heap, D는 Max Heap * Heap 구조와 배열 Index의 관계 ● Left Child Index = p * 2 ● Right Child I.. 2023. 1. 20. [알고리즘][정렬][C/C++] Merge Sort (병합정렬) Merge Sort (병합정렬) 특징 비교를 통해 정렬하는 비교기반 정렬 알고리즘 Divide & Conquer (분할 정복) 알고리즘 시간 복잡도 : O(N*logN) N크기의 임시 배열 1개가 추가적으로 필요 Merge Sort 과정 이해하기1 - 전체 Process Merge Sort는 분할하여, 정렬한뒤, 이를 비교하면서 Merge하는 과정을 통해서 이루어진다. 먼저, 배열에 2개의 Data가 있을 때, 오름차순으로 Merge Sort하는 과정을 살펴보자. 3과 1을 분할한 뒤에, 각각을 정렬해야하지만, Data가 1개씩 있기 때문에 정렬할 필요가 없다. 분할된 두 배열을 합칠 때, 비교하여 둘 중에 작은 수가 먼저 오도록 Merge 한다. 이제 배열에 6개의 Data가 있을 때, 오름차순으로 M.. 2023. 1. 18. 이전 1 다음 반응형
