검색 ( Search )

티스토리 뷰

검색 ( Search )

검색 ( Search )

RiKang 2018. 1. 2. 23:36

Table of Contents

선형 검색 (linear search)

이분 검색 (binary search)

삼분 검색 (ternary search)

문제

1. 선형 검색 (linear search)

가장 간단한 검색 알고리즘입니다. 목록의 처음부터 끝까지 탐색하여, 모든 요소들과 비교해보는 방법입니다. 예를 들기 위해 다음과 같은 문제를 풀어보겠습니다.

문제 )

첫 번째 줄에 두 자연수 N, M 이 주어진다. (N,M<=100)

두 번째 줄에 N 개의 자연수( <=100 )가 주어진다.

이 때, N 개의 자연수 중 M의 개수를 출력하시오.

이 문제를 해결하기 위해선 아래와 같이 N 개의 자연수를 하나씩 M과 비교해 보면 됩니다. 이러한 방법을 선형 검색이라고 합니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
// code by RiKang, weeklyps.com
#include <stdio.h>
using namespace std;
 
int n,m;
int a[105];
 
int main() {
    scanf("%d %d",&n,&m);
    for(int i=1; i<=n; i++)
        scanf("%d",&a[i]);
    
    int ans = 0;
    for(int i=1; i<=n; i++)
        if(a[i]==m)
            ans++;
    printf("%d",ans);
    return 0;
}
cs

선형 검색의 단점은 모든 요소를 탐색하기 때문에 시간복잡도가 최악이라는 점 ( 1차원 배열의 경우 O(N) ), 장점은 배열이 정렬되지 않은 상태에서도 사용할 수 있다는 점입니다. 때문에 배열이 정렬된 상태에서는 잘 쓰이지 않습니다.

2. 이분 검색 (binary search)

가장 자주 사용되는 검색 알고리즘이며, 정렬된 상태의 자료구조에서 사용할 수 있습니다. 자세한 내용은 아래의 문제를 이분 검색으로 해결하면서 설명하도록 하겠습니다.

문제 )

정렬된 배열 arr가 주어진다. ( arr[] = { 0, 1, 2, 3, 5, 5, 12 } )

arr에서 5의 위치 중 하나를 출력하시오,

정렬된 배열에서 특정한 수를 찾는 전형적인 검색 상황입니다. 이 상황을 좀 더 일반화 하면 아래와 같이 정의할 수 있습니다.

' 0 <= x < 7 인 정수 x 중에서 arr[x] = 5 를 만족하는 x 를 하나 출력하라.'

여기서, 선형 검색을 이용한다면 한 번의 비교 연산으로 다음과 같은 결과가 나옵니다.

선형 검색의 step 1 )

( arr[0] != 5 ) 임을 확인합니다.

-> 0은 답이 아니므로 ' 1 <= x < 7 인 x 중에서 arr[x] = 5 를 만족하는 x 를 출력하라.' 로 문제가 좁혀집니다.

-> 한번의 연산으로 검색 범위가 7개{0,1,2,3,4,5,6}에서 6개{1,2,3,4,5,6}로 줄었습니다.

위와 같이 선형 검색을 하면 한 번의 비교 연산으로, 검색 범위가 1개 줄어들게 됩니다. 검색 범위가 줄어들긴 했지만 만족스러운 결과는 아닙니다. 이를 개선한 이분 검색은 한 번의 비교 연산으로 최대한 검색 범위를 줄이는 것에 집중하는 방법입니다.

방법은 간단합니다. arr[0] (시작에 있는 값) 과 5 를 비교하는 것이 아니라, arr[3] (중간에 있는 값) 과 5를 비교하면 됩니다. arr[] 은 정렬된 배열이기 때문에, 중간에 있는 값과 비교하면 한 번의 비교 연산만으로 검색 범위를 절반으로 줄일 수 있습니다.

만일 arr[3] > 5 라면, arr[4], arr[5], arr[6], arr[7] 모두 5보다 큼을 알 수 있고, 검색 범위는 {0,1,2}로 줄어듭니다.

반대로 arr[3] < 5 라면, arr[0], arr[1], arr[2] 모두 5보다 작음을 알 수 있고, 검색 범위는 {3,4,5,6}로 줄어듭니다.

이분 검색의 step 1 )

( arr[3] <= 5 ) 임을 확인합니다

-> ' 4 <= x < 7 인 x 중에서 arr[x] = 5 를 만족하는 x 를 출력하라.' 로 문제를 좁힙니다.

-> 한번의 연산으로 검색 범위가 7개{0,1,2,3,4,5,6}에서 4개{3,4,5,6}로 줄었습니다.

이제 위의 과정을 검색 범위가 1개가 될 때까지 반복하면 됩니다. 초기 검색 범위가 N 개라고 하면, 한번의 비교 연산으로 검색 범위가 절반씩 줄어들기 때문에 시간복잡도는 O(log N) 이 됩니다.

N = 1000 이라면, 10번의 비교 연산, N = 1000000 이라면, 20번의 비교 연산, 검색 범위가 '세계의 모든 이름' 이라도, 정렬만 되어 있다면 35번의 이름 비교로 답을 찾을 수 있는 속도입니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
// code by RiKang, weeklyps.com
int find_idx(int *arr, int l, int r, int v){
    // 오름 차순으로 정렬된 arr[] 에서 arr[x] = v 이고 l<=x<r 인 x 를 리턴한다.
    while(r-l>1){
        int mid = (l+r)/2;
        if(arr[mid] > v) // 검색 범위가 l<=x<mid 로 좁혀진다.
            r = mid;
        else             // 검색 범위가  mid<=x<r 로 좁혀진다.
            l = mid;
    }
    if(arr[l] != v){} // 답이 없는 경우.
    return l; // 검색 범위가 l 밖에 남지 않았기 때문에 l 을 리턴한다.
}
Colored by Color Scripter
cs

3. 삼분 검색 (ternary search)

1. 1차원 배열에서의 삼분 검색

배열 arr[ 0, ..., N-1 ] 가 특정 x에 대해, 다음과 같은 두 조건을 모두 만족할 때 사용할 수 있습니다.

조건 1) arr[0] > arr[1] > arr[2] > .. > arr[x]

조건 2) arr[x] < arr[x+1] < arr[x+2] < .. < arr[N-1]

풀어서 설명하자면 arr[]은 특정 값 x를 기준으로, 왼쪽은 내림차순이고 오른쪽은 오름차순인 형태로서, 2차원 좌표계에 점을 찍어보면 볼록한 형태가 되는 배열입니다. (반대로 왼쪽이 오름차순이고, 오른쪽이 내림차순일 때도 가능합니다.)

이 배열에서 최솟값, 즉, arr[x] 를 찾고 싶을 때 선형 검색을 사용하면 O(N)이 되지만, 삼분 검색을 사용하면 O(log N)으로 찾을 수 있습니다. 아이디어는 이분 검색과 비슷합니다. 한번의 비교 연산으로 최대한 검색 범위를 줄이는 것이지요. 단, 전체가 정렬된 상태가 아니므로 중간 값을 2개 잡아야 합니다.

삼분 검색의 step 1)

mid1 = N/3, mid2 = N*2/3 로 설정합니다.

arr[mid1] 과 arr[mid2] 를 비교합니다.

경우 1) arr[mid1] > arr[mid2] 인 경우 : 검색 범위를 mid1 ~ N 으로 줄일 수 있습니다.

( * 최솟값이 mid1 보다 이전에 있다고 가정하면, arr[mid1] < arr[mid2] 가 성립하므로 모순입니다.)

경우 2) arr[mid1] <= arr[mid2] 인 경우 : 검색 범위를 0 ~ mid2 으로 줄일 수 있습니다.

위의 과정을 검색 범위과 최소화될 때까지 반복하는 것이 삼분 검색입니다. 초기 검색 범위가 N 개라고 하면, 한번의 비교 연산으로 검색 범위가 2/3 로 줄어들기 때문에 시간복잡도는 O(log N) 이 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// code by RiKang, weeklyps.com
#include<stdio.h>
#include<algorithm>
 
using namespace::std;
 
long long arr[100005];
 
long long ternary_search(int st, int en){
    // arr[st] ~ arr[en-1] 중 최솟값 리턴
    int l = st, r = en;
    while(r-l>=3) {
        int range = (r-l)/3;
        int mid1 = l + range;
        int mid2 = r - range;
        if(arr[mid1] < arr[mid2]) r = mid2;
        else l = mid1;
    }
    long long ret = arr[l];
    for(int i=l+1; i<r; i++)
        ret = min(ret, arr[i]);
    return ret;
}
Colored by Color Scripter
cs

그런데 사실, arr[x] < arr[x+1] 을 만족하는 최소의 x를 찾으면 이분 검색으로 x를 찾을 수 있으며, 이 방법의 속도가 더 빠른 경우도 많습니다. ( 조금 더 정확한 표현으로는 parametric search)

2. 함수에서의 삼분 검색

어떠한 함수 f(x) 가 특정 값 V 를 기준으로 x < V 일 때 단조 감소이고, x > V 일 때 단조 증가라면, 즉, 볼록한 형태라면 삼분 검색으로 V 값을 찾을 수 있습니다. 이 조건을 만족하는 가장 흔한 함수로는 2차 함수가 있습니다. (반대로 x < V 일 때 단조 증가, x > V 일 때 단조 감소여도 가능합니다.)

f(start) ~ f(end) 안에서 최솟값을 찾는 과정은 아래와 같습니다.

삼분 검색의 step 1)

mid1 = (2*start+end)/3, mid2 = (start+2*end)/3 로 설정합니다.

f(mid1) 과 f(mid2) 를 비교합니다.

경우 1) f(mid1) > f(mid2) 인 경우 : 검색 범위를 mid1 ~ N 으로 줄일 수 있습니다.

( * 최솟값이 mid1 보다 이전에 있다고 가정하면, f(mid1) < f(mid2) 가 성립하므로 모순입니다.)

경우 2) f(mid1) < f(mid2) 인 경우 : 검색 범위를 0 ~ mid2 으로 줄일 수 있습니다.

위의 과정을 검색 범위과 최소화될 때까지 반복합니다. 초기 검색 범위가 N 개라고 하면, 한번의 비교 연산으로 검색 범위가 2/3 로 줄어들기 때문에 시간복잡도는 O(log N) 이 됩니다.

1
2
3
4
5
6
7
8
9
10
11
12
// code by RiKang, weeklyps.com
double ternary_search(double st, double en){
    // f(st) ~ f(en) 중 최솟값 리턴
    double l = st, r = en;
    for(int i=0; i<200; i++) {
      double mid1 = (l*2+r)/3;
      double mid2 = (l+2*r)/3;
      if(f(mid1) < f(mid2)) r = mid2;
      else l = mid1;
    }
    return f(l);
}
Colored by Color Scripter
cs