[Section 6] 검색 알고리즘의 종류와 특징

자료구조와 알고리즘 목차 보기

[INTRO] 자료구조와 알고리즘

0. INTRO

검색 알고리즘은 자료 구조에서 특정 조건의 데이터를 추출하거나 찾는 데 사용하는 알고리즘이다. 자료구조에 따라 어떤 알고리즘이 효율적인지 그 종류와 특징에 대해 간략히 알아보자.

1. 간단히 구현 가능한 선형 검색

선형 검색(Linear Search)은 자료가 리스트 혹은 기타 선형 자료구조에서 단순히 구현 가능한 검색 알고리즘이다. 예를 들어, 배열의 데이터가 어떤 조건을 가지지 않고 무작위로 저장되어 있을 때 다음과 같이 반복문을 이용하여 조건에 맞는 데이터를 찾을 수 있다. 그리고 이 알고리즘은 자료구조가 정렬되어있든 아니든 관계없이 동일한 시간 복잡도 O(n)의 특성을 갖는다. 

 

예시:

def LinearSearch(List,c):

    for i in range(len(List)):

        if List[i] == c:

            return i

 

* 공간 복잡도는 O(1)이다.

2.  이진 검색과 보간 검색 알고리즘

이진 검색 알고리즘의 경우, 단순한 선형 검색과는 다르게 어떤 자료 구조에서 중간값에 먼저 접근하는 방식의 알고리즘이다. 예를 들어, 찾고자 하는 값이 중간값보다 크면 중간값부터 끝 값을 각각 최소, 최대 값으로 정하고 중간값에 다시 접근한다.

 

* 이진 검색 알고리즘의 시간 복잡도는 O(logn), 공간 복잡도는 O(1)이라는 특성을 갖는다.

 

이와 달리 보간 검색 알고리즘은 흔히 사전에서 어떤 단어를 찾는 것과 유사하다는 특징을 가지고 있다. 예를 들어, 한글 사전에서 '컴퓨터'라는 단어를 찾을 때, 우리는 'ㅋ'이라는 자음이 표시된 페이지부터 사전을 펼친다. 이와 마찬가지로 어떤 자료구조에서 상수 K를 공식화하여 이 상수값을 기준으로 검색 범위를 좁혀가는 것이 보간 검색 알고리즘의 핵심이다. 

 

* 평균적으로 보간 검색 알고리즘의 시간 복잡도는 O(log(logn))부터 최악의 경우 O(n) 까지로  알려져 있다.

 

이외에도 테이블, 해쉬, 문자열 검색 등 다양한 알고리즘이 존재한다.