배열 검색 - 선형 검색과 보초법

검색 알고리즘

 

검색은 어떤 조건을 만족하는 데이터를 찾아내는 과정입니다. 알고리즘에는 배열 검색, 연결 리스트 검색, 이진 검색 트리 검색 등 다양한 검색 알고리즘이 있습니다.

 

선택할 수 있는 알고리즘은 다양하지만, 단순히 계산 시간이 빠르다고 해서 좋은 알고리즘은 아닙니다. 검색 처리 시간뿐만 아니라 데이터의 추가·삭제 등 이외 작업들에 대한 비용을 종합 평가하여 적절한 알고리즘을 선택해야합니다.

 

하여 이번 포스팅에서는 구체적으로 다음 세 가지 배열 검색 알고리즘 중 선형 검색 알고리즘에 대해 공부하고자 합니다.

 

① 선형 검색: 무작위로 늘어놓은(원소의 값이 정렬되지 않은) 데이터 집합에서 검색을 수행

② 이진 검색: 일정한 규칙으로 늘어놓은(원소의 값이 정렬된) 데이터 집합에서 아주 빠른 검색 수행

③ 해시법: 추가·삭제가 자주 일어나는 데이터 집합에서 아주 빠른 검색 수행

 

선형 검색

 

선형 검색이란 선형으로 늘어선 배열에서 검색하는 경우에 타겟 원소를 찾을 때까지 맨 앞에서부터 순서대로 검색하는 알고리즘입니다. 배열의 0번째 원소부터 스캔하여 순차 검색이라고도 합니다. 

 

다음 코드는 배열의 원소 개수가 num인 배열 x를 만들고 이를 while 함수를 활용한 seq_search() 함수를 통해 찾고자 하는 키 값을 찾는 선형 탐색 코드입니다.

from typing import Any, Sequence

def seq_search(seq: Sequence, key: Any) -> int:
    i = 0

    while True:
        if i == len(str(seq)):
            return -1
        if seq[i] == key:
            return i
        i += 1

if __name__ == '__main__':
    num = int(input('원소 수: '))
    x = [None] * num

    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))

    k = int(input('검색할 키 값: '))

    idx = seq_search(x, k)

    if idx == -1:
        print('키 값 없음')
    else:
        print(f'키 값은 x[{idx}]에 있다')
        
        
"""
원소 수: 3
x[0]: 3
x[1]: 1
x[2]: 2
검색할 키 값: 1
키 값은 x[1]에 있다
"""

 

배열의 스캔을 for 문으로 하면 코드가 더 간결해집니다. 

def seq_search(seq: Sequence, key: Any) -> int:
    i = 0

    for idx in range(len(str(seq))):
        if seq[idx] == key:
            return idx
    return -1

 

보초법

 

 

선형 검색은 반복할 때마다 2가지 종료 조건을 체크합니다.

조건 ①: 검색할 값을 찾지 못하고 배열의 맨 끝을 지나갔는가?

조건 ②: 검색할 값과 같은 원소를 찾았는가?

 

단순한 판단이지만, 이 과정을 계속 반복하면 종료 조건을 검사하는 비용을 무시할 수 없습니다. 이 비용을 반으로 줄이기 위한 보초법을 공부하고자 합니다. 

 

보초법은 검색하고자 하는 값을 배열의 맨 끝에 추가하는 것입니다. 그렇다면 원래 배열에서 찾고자하는 값을 찾지 못하여도 마지막 원소까지 스캔하는 단계에서 종료 조건 ②을 성립하여, 종료 조건 ①은 판단할 필요가 없는 것입니다.

 

앞서 while문을 통해 구현한 코드를 보초법을 사용하여 수정한 코드입니다.

from typing import Any, Sequence
import copy


def seq_search(seq: Sequence, key: Any) -> int:
    a = copy.deepcopy(seq)  # seq 복사
    a.append(key)

    i = 0
    while True:
        if seq[i] == key:
            return i
        i += 1
    return -1 if i == len(seq) else i

 

출처

 

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