Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편 - 03 검색 알고리즘 요약

검색 알고리즘이란?

검색과 키

키

검색 조건으로 주목하는 항목이며 대부분 데이터의 일부이다.

 

검색에서는 조건을 하나만 지정할 수 있고 논리곱, 논리합을 사용하여 복합해서 지정할 수 있다.

검색의 종류

• 선형 검색: 무작위로 늘어놓은 데이터 집합에서 검색을 진행한다.
• 이진 검색: 일정한 규칙으로 늘어놓은 데이터 집합에서 아주 빠른 검색을 수행한다.
• 해시법: 추가, 삭제가 자주 일어나는 데이터 집합에서 아주 빠른 검색을 수행한다.

선택할 수 있는 알고리즘이 다양한 경우에는 용도, 목적, 실행 속도, 자료구조 등 여러 사항을 고려해서 선택해야 한다.

복잡도(Complexity)

알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도라고 한다.

• 시간 복잡도(time complexity): 실행하는 데 필요한 시간을 평가
• 공간 복잡도(space complexity): 메모리와 파일 공간이 얼마나 필요한지를 평가

시간 복잡도

알고리즘의 전체 복잡도는 차원이 가장 높은 복잡도를 선택한다.

선형 검색

선형 검색(linear search)

선형으로 늘어선 배열에서 검색하는 경우에 원하는 키값을 가진 원소를 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘.

순차 검색이라고도 한다.

선형 검색의 시간 복잡도

O(n)

보초법(Sentinel method)

선형 검색은 반복할 때마다 '검색할 값과 같은 원소를 찾았는가?'와 '검색할 값을 찾지 못하고 배열의 맨 끝을 지나갔는가?' 이 2가지 조건을 체크한다. 보초법은 검색할 값과 같은 원소를 배열의 맨 끝에 추가하여 위의 2번째 조건을 판단하지 않아도 된다.

즉, 검색할 값과 같은 원소를 찾은 후 해당 원소의 인덱스를 배열의 끝에 새롭게 추가한 값의 인덱스와 비교하여 배열에 원래 원소가 있었는 지만 비교하면 된다.

결론적으로, 보초법은 반복을 종료하는 판단 횟수를 줄이는 역할을 한다.

이진 검색

이진 검색(Binary search)

이진 검색 알고리즘은 배열의 데이터가 사전에 오름차순 혹은 내림차순으로 정렬된 배열에서 사용한다.

 

배열에 중앙에 위치한 원소를 검색할 값과 비교하여 값이 같으면 검색이 성공하고 값이 다르면 대소를 비교해 다시 검색할 배열을 절반으로 줄인 뒤 해당 배열의 중앙에 위치한 원소를 비교하는 과정을 반복한다.

이진 검색의 종료 조건

• 비교하는 원소와 검색할 값이 같은 경우
• 검색 범위가 더 이상 없는 경우

이진 검색의 시간 복잡도

O(log(n))

해시법(Hashing)

해시법은 '데이터를 저장할 위 = 인덱스'를 간단한 연산으로 구하는 것을 말한다.

이 방법을 통해 검색과 더불어 데이터의 추가, 삭제도 효율적으로 수행할 수 있다.

해시값(hash value)

데이터를 접근할 때 기준

해시 테이블(hash table)

해시값을 인덱스로 하여 원소를 새로 저장한 배열

해시 함수(hash function)

키를 해시값으로 변환하는 과정이며 일반적으로 함수는 나머지를 구하는 연산 또는 그 연산을 응용할 때 주로 사용한다.

해시함수는 가능한 한 해시값이 한쪽으로 치우치지 않고 고르게 분산된 값을 출력하도록 만드는 것이 가장 좋다.

버킷(bucket)

해시 테이블에서 만들어진 원소

해시 충돌

키와 해시값은 일반적으로 다 대 1(n:1)이다. 이처럼 저장할 버킷이 중복되는 현상을 충돌이라고 한다.

 

이러한 충돌이 발생하는 경우 2가지 방법으로 대처할 수 있다.

• 체인 법: 해시값이 같은 원소를 연결 리스트로 관리한다.
• 오픈 주소법: 빈 버킷을 찾을 때까지 해시를 반복한다.

체인법(chaining)

해시값이 같은 데이터를 체인(chain) 모양의 연결 리스트로 연결하는 방법, 오픈 해시법(open hashing)이라고도 한다.

오픈 주소법(open addressing)

충돌이 발생했을 때 재해시(rehashing)를 수행하여 빈 버킷을 찾는 방법, 닫힌 해시법(closed hashing)이라고도 한다.

 

위와 같은 과정을 통해 원소를 추가하면 특정 원소를 찾을 때 같은 해시를 같은 다른 원소가 있을 경우 검색에 실패할 수 있다. 구체적인 예시를 들자면, 먼저 1의 해시값을 갖는 원소 a가 먼저 저장되고 똑같이 1의 해시값을 갖는 원소 b는 재해시를 통해서 다른 해시값으로 저장된 해시 테이블에 원소 a가 삭제를 당하고 다시 b를 찾을 때 처음 찾은 1 인덱스의 버킷에는 아무것도 들어있지 않아 검색에 실패할 수 있다. 이때를 대비해 a를 지울 때 특정 표식을 남기면 나중에 b를 검색할 때 없는 원소로 단정 짓지 않게 할 수 있다.