티스토리 뷰
Table of Contents
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 을 리턴한다. } | 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; } | 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); } | cs |
그런데 사실, f(x) < f(x+0.00...001)을 만족하는 최소의 x를 찾으면 이분 검색으로 x를 찾을 수 있으며, 이 방법의 속도가 더 빠른 경우도 많습니다. ( 조금 더 정확한 표현으로는 parametric search)
4. 문제
(0) [BOJ 1920] 수 찾기
※ 본문의 코드들은 C++ 17 환경에서 작성되었습니다.
※ 문의 : rikang93@gmail.com