알고리즘 - Search

Search : 어떤 조건을 만족하는 데이터를 찾아내는 것

 

고려해야 할 사항 : 추가/삭제 같이 검색 이외의 작업에 들어가는 비용, 주어진 자료구조, 데이터의 형태 등을 종합적으로 평가하여 최적의 검색 알고리즘을 선택해야 한다. 배열이 주어지고 그 안에서 특정한 Key값을 찾는다고 할 때, 아래와 같은 방법들을 고려할 수 있다.

 

선형 검색(Linear Search)

무작위로 주어진 데이터에 대하여 순차적으로 검색하는 방법. 검색 시간이 데이터의 크기에 선형적으로 비례한다.

 

방법 : 맨 앞, 혹은 맨 뒤부터 순차적으로 Key 값을 찾는다.

 

종료 조건 : 1. Key와 일치하는 원소를 찾은 경우

                2. 배열의 길이를 넘어선 경우

시간복잡도 : O(n)

 

* 보초법 : 배열의 맨 끝에 찾는 원소를 추가하여 매번 배열의 끝인지 확인할 필요를 줄이는 방법.

 

이진 검색(Binary Search)

정렬된 데이터에 대하여 효율적으로 검색할 수 있는 알고리즘. 한번 비교를 수행할 때마다 비교 대상의 데이터 수가 반으로 줄어든다.

 

방법 : 맨 왼쪽 끝 원소의 Index를 Left, 맨 오른쪽 끝 원소의 index를 Right라고 한 뒤, Center의 값과 Key값을 비교한다. 대소 여부에 다라 Left, Right 값을 변경한다.

 

종료 조건 : 1. a[Center]가 key와 일치하는 경우

               2. 검색 범위가 더이상 없는 경우

 

시간복잡도 : O(logn)

 

 

해시(Hashing)

데이터를 저장할 위치를 해시 함수를 사용하여 결정하는 방법. 키값을 해시 함수를 통과시켜 해시값을 얻어낸 뒤, 해시값에 해당하는 인덱스에 키를 저장한다. 키를 해시값으로 변환하는 함수를 해시 함수, 해시 테이블에서 만들어진 원소를 버킷이라고 한다.

 

해시 함수의 예시 : 13으로 나눈 나머지

위와 같은 해시 함수에 대하여 같은 해시 값을 가진 키가 존재하는 경우 충돌이 일어날 수 있다. 예를 들어, 14도 13으로 나눈 나머지가 1이고, 27도 13으로 나눈 나머지가 1이기 때문에 해시 값이 같은 Key가 존재하게 된다. 이를 해시 충돌이라고 하고, 다음과 같은 두가지 방법으로 처리한다.

 

1) 체인법 : 해시값이 같은 원소를 연결 리스트로 관리한다.

2) 오픈 주소법 : 버킷이 가득 찬 경우를 대비하여, rehash 함수를 정의한다. 이후 가득찬 버킷에 추가할 일이 생기면, 빈 버킷을 찾을 때까지 rehash를 반복한다.