순차 탐색(Sequential Search) 의 개념

탐색은 여러 원소로 구성된 데이터에서 원하는 원소를 찾는 것입니다. 데이터의 형태는 리스트나 트리, 그래프 등 다양한 형태가 가능합니다.

순차 탐색은 리스트 형태로 주어진 원소들을 처음부터 하나씩 차례로 살펴보며 원하는 값을 가진 원소를 찾는 방법입니다.

어떤 데이터를 삽입하고자 한다면, 리스트의 마지막에 새로운 원소를 하나 추가하면 되며 삭제를 원한다면 삭제할 원소를 탐색키로 하여 순차 탐색을 통해서 삭제하고, 삭제된 자리에 리스트의 마지막 원소를 옮겨오면 됩니다.

순차 탐색의 Python 구현

Python 으로 순차 탐색을 아래와 같이 구현할 수 있습니다.

def sequential_search(arr: list, key: int) -> int:
    for i in range(len(arr)):
        if arr[i] == key:
            return i
    return -1

순차 탐색은 개념만큼이나 구현도 매우 간단합니다. 배열을 순차적으로 돌며, 원하는 값을 가진다면 그것을 반환하는 것입니다.

순차 탐색의 성능 분석과 특징

• 순차 탐색은 하나의 루프로 구성되며, 루프는 입력 배열의 크기에 비례합니다.
• 순차 탐색의 시간 복잡도는 O(n) 입니다.
• 순차 탐색의 삽입 알고리즘은 상수 시간만 필요합니다. 시간 복잡도는 O(1) 입니다.
• 순차 탐색의 삭제 알고리즘은 O(n) 입니다. O(n) 인 탐색 알고리즘을 사용해 삭제할 원소를 찾고, 리스트의 마지막 원소를 삭제할 원소의 위치로 이동시켜 삭제하기 때문입니다.
• 순차 탐색은 입력이 리스트 형태라면 언제라도 적용이 가능합니다. 데이터가 정렬되어 있지 않아도 된다는 의미입니다.
• 순차 탐색은 시간 복잡도가 O(n) 이므로, 데이터가 큰 경우에는 적합하지 않은 탐색 방법입니다.