Algorithm - 검색 알고리즘

검색 알고리즘

 

데이터의 집합에서 원하는 값을 가진 요소를 찾아내는 검색 알고리즘

주소록을 검색한다고 가정하면 다음과 같은 방법으로 이루어진다.

1. 국적이 한국인 사람을 찾는다

2. 나이가 21세 이상 27세 미만인 사람을 찾는다

3. 찾으려는 이름과 가장 비슷한 이름을 가진 사람을 찾는다

 

위의 방법들을 보면 특정 항목에 주목한다는 공통점이 있다.

이때 주목하는 항목을 키라고 칭한다.

1. 선형 검색 : 무작위로 늘어서 있는 데이터 모임에서 검색을 수행한다
2. 이진 검색 : 일정한 규칙으로 늘어서 있는 데이터 모임에서 아주 빠른 검색을 수행한다.
3. 해시법 : 추가, 삭제가 자주 일어나는 데이터 모임에서 아주 빠른 검색을 수행한다.
	- 체인법 : 같은 해시값의 데이터를 선형 리스트로 연결하는 방법
  	- 오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시 하는 방법

여기서 해시법은 데이터 검색뿐만 아니라 추가나 삭제 등을 효율적으로 수행할 수 있는 종합적인 방법이다.
우리가 알고리즘을 선택함에 있어 검색만 하면 된다!고 생각을 한다면 단순히 계산 시간이 짧은 알고리즘을
선택하면 해결될 것이다.
허나 데이터 집합에서 검색뿐만이 아니라 데이터의 추가/삭제 작업을 자주 한다면 검색 이외의 작업에
소요되는 비용을 종합적으로 평가하여 알고리즘을 선택해야한다.
예를 들면 데이터 추가를 자주 한다면 검색이 빠르더라도 데이터의 추가 비용이 많이 들어가는 알고리즘은
피해야 하는 것이다.
데이터의 추가 비용은 어떤 경우에 더 많이 들까?
 - 학생의 번호 순서대로 키의 값을 넣은 배열이 있다고 가정할 때 학생의 번호만 알면 바로 킷값을 알 수 있다.
 하지만 새로운 학생이 전학을 와서 중간에 데이터를 끼워넣어야 한다면 이후의 학생들을 모두 뒤로 밀어내는 작업을 해야한다. 
 바로 이러한 경우에 배열을 빠르게 검색할 수 있지만 데이터를 추가하는 데 많은 비용이 든다고 한다

 

1. 선형검색

요소가 직선 모양으로 늘어선 배열에서 검색은 원하는 키값을 갖는 요소를 만날 때까지 맨 앞부터 순서대로 요소를 검색

1

5

9

8

7

2

다음과 같은 배열이 있을 때 8을 검색하는 진행 방식이다.

인덱스가 0인 요소 1을 선택 -> 검색하려는 값이 아님
인덱스가 1인 요소 5을 선택 -> 검색하려는 값이 아님
인덱스가 2인 요소 9을 선택 -> 검색하려는 값이 아님
인덱스가 3인 요소 8을 선택 -> 검색하려는 값이 맞음

허나 요소중에 존재하지 않는 6을 검색한다면?

인덱스가 0인 요소 1을 선택 -> 검색하려는 값이 아님
인덱스가 1인 요소 5을 선택 -> 검색하려는 값이 아님
인덱스가 2인 요소 9을 선택 -> 검색하려는 값이 아님
인덱스가 3인 요소 8을 선택 -> 검색하려는 값이 아님
인덱스가 4인 요소 7을 선택 -> 검색하려는 값이 아님
인덱스가 5인 요소 2을 선택 -> 검색하려는 값이 아님

 

< 종료 조건 >

1. 종료 검색할 값을 발견하지 못하고 배열의 끝을 지나간 경우 = 검색 실패

2. 종료 검색할 값과 같은 요소를 발견한 경우 = 검색 성공

 

static int seqSeach(int []a, int n, int key){
	int i = 0;
    
    while(true){
    if(i==n) return -1; //검색 실패시 -1을 반환
    if(a[i]==key) return i; //검색 성공시 인덱스를 반환
    i++;
    }

}

 

위의 메소드는 값이 key인 요소가 여러개가 존재할 경우 가장 처음 발견한 요소의 인덱스를 반환한다

2를 검색하면 이 값은 배열x[3] x[5]에 존재한다고 가정 했을 때 가장 먼저 찾은 x[3]의 인덱스 값인 3을 반환한다

 

보초법으로 선형 검색 구현하기

선형 검색은 반복할 때마다 다음의 종료 조건 1과 2를 모두 판단한다.

이 종료조건을 검사하는 비용은 절대 무시할 수 없기 때문에 이 비용을 반으로 줄이는 방법이 보초법이다.

가령 2를 검색한다고 가정해보자

a[0]=5

a[1]=3

a[2]=2

a[3]=4

a[4]=2(보초)

a[0]~a[3]은 초기에 준비해둔 데이터이다.

맨 끝 요소 a[4]는 검색하기 전에 값을 저장하는 보초이다.

보초에는 다음과 같이 검색하고자 하는 키값을 저장한다.

1. 2를 검색하기 위해 보초로 a[4]에 2를 저장한다

2. 5를 검색하기 위해 보초로 a[7]에 5를 저장한다

 

만약 원하는 값이 데이터에 존재하지 않아도 보초까지 검색하면 종료 조건 2(검색할 값과 같은 요소를 발견했는가)가 성립된다. 이렇게 하면 원하는 키 값을 찾지 못했을 때 판단하는 종료조건 1이 없어도 된다.

또한 보초는 반복문에서 종료 판단 횟수를 2회에서 1회로 줄이는 역할을 한다.

 

//보초법을 활용한 메소드

static int seqSearchSen(int[] a, int n, int key){
	int i = 0;
    a[n] = key;
    
    while(true){
    	if(a[i]==key) break;
        i++;
    }
    return i == n ? -1 : i;
}

2. 이진 검색

이 알고리즘을 적용하는 전제 조건은 데이터가 키값으로 이미 정렬되어 있다는 것이다.

이진 검색은 선형 검색보다 좀 더 빠르게 검색할 수 있다는 장점이 있다.

인덱스	0	1	2	3	4	5	6	7	8
요소	5	7	16	25	32	41	58	77	82

1.먼저 배열의 중앙 요소인 a[4] 32부터 검색을 시작한다.

2.검색할 값이 58라고 가정하면 a[4] 32보다 크기에 뒤쪽 a[5]~a[8]로 검색 대상을 좁힌다.

3.검색할 값 58은 중간 인덱스 (6+7)/2 로 계산하여 6이 된다. 정수의 나눗셈은 나머지를 버리기 때문

4.6번 인덱스는 검색할 값 58과 같으므로 검색 성공이다.

 

이 알고리즘의 핵심은 이진 검색을 한 단계씩 진행할 때마다 검색 범위가 거의 반으로 좁혀진다는 것이다.

검색 범위를 좁혀가는 방법을 간단히 정리해보자면

- 중앙값이 key보다 작을 때 : 중앙 바로 오른쪽 인덱스를 새로운 검색 범위의 pl(왼쪽)으로 하여 뒤쪽으로 좁힌다

- 중앙값이 key보다 클 때 : 중앙 바로 왼쪽 인덱스를 새로운 검색 범위의 pr(오른쪽)으로 하여 앞쪽으로 좁힌다

 

<종료 조건>

1. 중앙값과 key가 일치한다

2. 검색 범위가 더 이상 없다

 

만일 원하는 값을 못찾을 경우엔?

STEP1
검색할 범위는 배열 전체(a[0]~a[10])이고 중앙 요소 a[5]값은 31이다.
키값인 6보다 크므로 검색 범위를 a[0]~a[4]로 좁힌다.

STEP2
새로운 검색 범위에서 중앙 요소 a[2]값은 15이다.
키값인 6보다 크므로 검색할 범위를 a[0]~a[1]로 좁힌다.

STEP3
새로운 검색 범위에서 중앙 요소 a[0]값은 5이다.
키값인 6보다 작으므로 pl을 pc+1(1)로 업데이트 합니다. 그러면 pl과 pr은 둘다 1이 됩니다.

STEP4
새로운 검색 범위에서 중앙요소 a[1]값은 7이다.
키값인 6보다 크므로 pr을 pc-1(0)로 업데이트 한다.

STEP5
그러면 pl이 pr보다 커지면서 검색 범위가 없어지며 종료조건 2가 성립하므로 검색 실패이다.

이진 검색은 검색을 반복할 때마다 검색 범위가 거의 절반이 되므로 검색에 필요한 비교 횟수의 평균값은 log n이다.

검색에 실패하면 [log(n+1)]회, 검색에 성공하면 대략 log n-1회 이다.

여기서 [x]는 x의 천장함수라고 하며 x보다 크거나 같으면서 가장 작은 정수이다.

 

복잡도 구하기

static int seqSearch(int []a, int n, int key){
	int i = 0; //O(1)
    while(i<n) { //O(n)
    	if(a[i]==key) //O(n)
        	return i; //O(1)
    	i++; //O(n)
    }
    return -1; //O(1)
}

시간 복잡도는 가장 차수가 높은 복잡도를 선택한다.

그렇기 때문에 선형 검색의 시간복잡도는 O(1)+O(n)+O(n)+O(1)+O(n)+O(1) = O(max(1, n, n, 1, n, 1)) = O(n)이다.