[알고리즘] 순차 탐색(Sequential Search)에 대해 알아보자!(+Python 구현)

본 포스팅에서는 순차 탐색(Sequential Search)에 대해 알아봅니다.

📚 목차

1.  순차 탐색(이란?
2.  동작 과정
3.  구현(Python)
4.  시간 복잡도

1.  순차 탐색이란?

순차 탐색(Sequential Search)은 말 그대로 리스트 내 특정 데이터를 찾기 위해 앞에서부터 데이터를 차례대로 탐색하는 알고리즘입니다.

2.  동작 과정

순차 탐색의 과정은 아래와 같습니다. 풀어써서 복잡해 보이지만 맨 앞에서부터 차례대로 비교하는 단순한 방법입니다.

 

1️⃣ 맨 앞 데이터와 찾으려는 데이터가 같은지 탐색합니다.

2️⃣ 데이터가 서로 같지 않다면 다음 데이터와 찾으려는 데이터가 같은지 탐색합니다.

3️⃣ 같은 데이터를 찾기 전까지 2️⃣ 과정을 반복합니다.

 

리스트 내 데이터가 아무리 많아도 시간만 충분하다면 반드시 원하는 데이터를 찾을 수 있습니다. 이제 예를 들어, 아래 그림 1 과 같이 5개의 도시 중 'Seoul'이 리스트 내에 몇 번째 위치해 있는지 순차 탐색을 통해 알아보겠습니다. 편의상 찾는 데이터를 파란색 동그라미로, 현재 비교하는 데이터를 파란색 화살표로, 비교한 데이터는 회색 동그라미로 표현하겠습니다.

 

그림 1.  5개의 도시 이름이 담긴 리스트

(1)  맨 앞의 데이터('New York')부터 확인하여 'Seoul'이라는 문자열과 같은지 확인합니다. 같지 않다면 다음 데이터를 탐색합니다.

 

(2) 두 번째 데이터('Paris')와 'Seoul'이라는 문자열과 같은지 확인합니다. 같지 않다면 다음 데이터를 탐색합니다.

 

 

(3) 세 번째 데이터('Seoul')와 'Seoul'이라는 문자열과 같은지 확인합니다. 두 데이터가 같기 때문에 탐색을 마칩니다.

 

3.  구현(Python)

소스 코드

def sq_search(n, target, arr):
    # 리스트 내 데이터를 차례로 탐색
    for i in range(n):
        if arr[i] == target:
            # 비교한 위치 반환(인덱스는 0부터 시작하기 때문에 1 더하기)
            return i + 1 

arr = ['New York', 'Paris', 'Seoul', 'London', 'Toronto']
# 원소 개수
n = len(arr)
# 찾고자 하는 문자열
target = arr[2]

print("{}번째에서 데이터 탐색 종료.".format(sq_search(n, target, arr)))

앞서 살펴본 예시에 대한 순차 탐색의 구현은 위와 같습니다.

실행 결과

2번째 위치에서 탐색 종료.

4.  시간 복잡도

순차 탐색은 데이터 정렬 여부와 상관없이 맨 앞에 있는 데이터부터 하나씩 차례대로 탐색해야 합니다. 따라서 리스트 내 데이터가 N개 있다면 비교 연산을 최대 N번 수행해야 합니다. 즉, 최악의 경우 순차 탐색의 시간 복잡도는 O(N) 입니다.

---

포스팅 내용에 오류가 있을 경우 댓글 남겨주시면 감사드리겠습니다.

그럼 오늘도 즐거운 하루 보내시길 바랍니다 :)

고맙습니다.