본문 바로가기

Algorithm/C. Sortings & Search

 (14)
40. Parametric Search 매개변수 탐색(Parametric Search)은 최적화 문제를 결정 문제로 변형한 뒤 이분 탐색, 삼분 탐색 등을 이용하여 답을 찾아내는 탐색 방법이다. 예를 들어 어떤 함수 $f(x)$가 특정 구간에서 증가하고 $f(x)$가 $k$ 이상이 되는 최소의 $x$를 찾아야 할 경우 해결해야 하는 것은 주어진 조건을 만족하는 $x$의 최소값이므로 이것은 최적화 문제이다. 하지만 단순히 $f(x)$가 $k$ 이상인지를 판별하는 것은 참, 거짓만 확인하면 되므로 결정 문제가 된다. 또한 이 결정 문제의 답은 $x$가 특정 값보다 작다면 거짓, 그렇지 않다면 참이므로 참, 거짓의 기준이 되는 $x$를 이분 탐색으로 찾아낼 수 있다. 이 방법을 응용하면 일부 조건이 '최대의 $x$', '$k$ 초과', '$k$ 미..
39. Ternary Search 삼분 탐색(Ternary Search)은 어떤 데이터가 극값 하나를 가지는 형태로 나열되어 있을 때 그 극값을 빠르게 찾을 수 있는 탐색 방법이다. 일반적으로 데이터 자체를 삼분 탐색으로 찾을 일은 거의 없고, 어떤 함수의 개형이 특정 구간에서 볼록함수로 나타내어질 때 극값을 찾기 위해 삼분 탐색이 사용되는 경우가 많다. 삼분 탐색을 삼진 탐색이라고 하는 경우도 있으나 삼진 탐색이라는 용어는 잘 쓰이지 않는 것으로 보인다. 다음과 같은 함수 $f(x)$의 극값을 찾는 상황을 생각해 보자. $f(x)$가 극값을 갖는 $x$의 범위를 알고 있고, 임의의 $x$에 대해 $f(x)$를 구할 수 있다고 가정한다. 이 함수는 주어진 구간에서 하나의 극값을 가지므로 삼분 탐색을 사용할 수 있다. 먼저 주어진 구간을 ..
38. Binary Search 이분 탐색(이진 탐색, Binary Search)은 정렬된 데이터에서 원하는 값을 빠르게 찾을 수 있는 탐색 방법이다. 기본적인 원리는 정렬된 데이터를 앞쪽 절반과 뒤쪽 절반으로 나눈 다음 두 구간 중 해당 값을 포함하지 않는 구간을 배제하고 남은 한 구간에서 다시 데이터를 찾는 과정을 반복하는 것이다. 이렇게 하다가 구간에 값이 하나 남았을 경우 그 값을 찾는 값과 비교해서 같다면 원하는 값을 찾은 것이고, 다르다면 데이터에 원하는 값이 존재하지 않는 것이다. 데이터의 수가 $n$일 때 이분 탐색의 시간복잡도는 $O(\text{lg }n)$이다. BOJ 1920. 수 찾기 (Silver IV) 이 문제를 통해서 이분 탐색을 더 자세히 이해할 수 있다. 일단 $n$개의 정수를 정렬하고, 찾으려는 각각의 ..
37. Linear Search 선형 탐색(Linear Search)은 주어진 데이터에서 원하는 데이터를 찾는 가장 기본적인 방법으로, 순차 탐색(Sequential Search)이라고도 한다. 주어진 데이터가 정렬되어 있지 않는 경우에도 사용할 수 있지만 모든 데이터를 다 확인할 수도 있기 때문에 시간복잡도가 $O(n)$으로 다른 빠른 탐색에 비해 상대적으로 느리다는 단점이 존재한다. 다음은 $n$개의 원소로 이루어진 배열 $a$에서 $k$라는 값을 찾는 코드의 일부이다. 인덱스는 $1$-based이다. int pos = 0; for(int i = 1; i
36. Other Sorting Method 칵테일 정렬(Cocktail Sort)은 버블 정렬과 비슷한데 앞의 원소와 뒤의 원소를 번갈아서 정렬한다. 시뮬레이션은 다음과 같다. 콤브 정렬(Comb Sort) 역시 버블 정렬과 비슷하지만 인접한 원소를 비교하지 않고 특정한 간격을 정해서 그 간격만큼 떨어진 원소를 비교한다. 이 간격을 좁혀나가면서 정렬을 수행한다. 트리 정렬(Tree Sort)은 주어지는 데이터로 이진 트리를 만들어 데이터를 정렬하는 방식이다. 힙 정렬과 비슷하지만 힙 정렬이 실행될 때는 트리의 형태에 제약이 있는 반면 트리 정렬이 실행될 때는 트리의 형태에 제약이 없다. 이진 트리가 만들어졌다면 중위 순회를 통해서 데이터의 순서를 정할 수 있다. 팀 정렬(Tim Sort)은 병합 정렬과 삽입 정렬을 결합한 것이다. 기본적으로 병합..
35. Radix Sort 기수 정렬(Radix Sort)은 자릿수가 있는 데이터를 정렬할 수 있는 방법으로, 가장 낮은 자리부터 시작해서 각각의 자리값을 기준으로 한 번씩 정렬을 실행한다. 이 과정이 끝나면 전체 데이터를 정렬할 수 있게 된다. 다음과 같은 데이터가 있을 때, [811, 310, 659, 156, 27, 230, 384, 905, 422, 513, 324] 기수 정렬을 이용해 이 값들을 오름차순으로 정렬한다고 하면 다음과 같은 과정을 거치게 된다. 먼저 일의 자리를 기준으로 값들을 분류한다. [811] [310, 230] [659] [156] [27] [384, 324] [905] [422] [513] 이 값들을 일의 자리 수가 작은 순서대로 모두 이어붙인다. [310, 230, 811, 422, 513, 384..
34. Counting Sort 앞에서 설명한 정렬 기법들은 데이터끼리 서로 비교하면서 정렬을 수행하는데, 이 방법으로는 시간복잡도가 $\Theta(n\text{ lg }n)$보다 작게 할 수 없다. 하지만 데이터의 범위에 제약이 있는 경우 $\Theta(n\text{ lg }n)$보다 작은 시간복잡도로 정렬을 수행할 수 있다. 그 중 가장 대표적인 방법이 계수 정렬(카운팅 정렬, Counting Sort)이다. 계수 정렬은 각각의 원소가 등장하는 횟수를 센 뒤 앞에 나오는 원소부터 그 원소가 등장하는 횟수만큼 나열하는 것이다. 이 방법은 정렬할 원소의 범위가 크지 않을 때만 쓸 수 있다. 카운팅 정렬의 간단한 구현은 다음과 같다. #import using namespace std; int n,a[100005],p[100005]; in..
33. Heap Sort 힙(Heap)은 원소를 정해진 규칙에 따라 배치한 완전 이진 트리로, 크게 최소 힙(Min Heap)과 최대 힙(Max Heap)으로 구분할 수 있다. 최소 힙은 부모 노드의 값이 자식 노드의 값보다 작은 힙을 의미하며, 최대 힙은 그 반대이다. 형제 노드 간에는 대소 관계가 정해지지 않는다. 힙에 원소를 삽입하거나 힙에서 원소를 삭제할 경우 먼저 힙의 구조를 맞춘 다음 원소들의 교환을 통해서 대소 관계를 맞게 한다. 힙의 원소의 수가 $n$일 때 삽입/삭제 연산 한 번의 시간복잡도는 $\Theta(\text{lg }n)$이다. 이 힙을 이용해서 원소들을 정렬하는 것이 힙 정렬(Heap Sort)이다. 원소를 하나씩 힙에 삽입한 다음 힙의 루트에 있는 값을 빼는 과정을 반복하면 원소를 정렬할 수 있다. ..

티스토리툴바