Python 78 - 이진탐색 _ 범위를 반씩 좁혀가는 탐색 ( 순차탐색 )

순차탐색

이번 장에서는 리스트 내에서 데이터를 매우 빠르게 탐색하는 이진 탐색 알고리즘에 대하여 공부하겠다. 이진탐색에 대해 알아보기 전에 가장 기본 탐색 방법인 순차 탐색에 대해 먼저 이해할 필요가 있다. 1장부터 차례대로 읽은 독자라면 이미 자연스럽게 순차 탐색의 원리를 익혔다. 사실 지금까지 예제 문제에서 N개의 데이터가 있을 때 , 그데이터를 차례대래로 하나씩 확인하여 어떠한 처리를 해준 경우가 많았는데 그 자체로도 이미 순차 탐색이라고도 할 수 있다. 예를 들어 3장의 '거스름돈' 문제에서 가장 큰 화폐 단위부터 확인(탐색)해서 각 단위에 대하여 처리한 것을 기억해보자.

이와 같이 순차탐색(Sequential Search)이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나의 차례대로 확인하는 방법이다. 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다. 리스트 내에서 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소( 데이터 )를 찾을 수 있다는 장점이 있다.

다음은 순차 탐색으로 Taeyoung을 찾는 과정이다.

순차 탐색은 이름처럼 순차로 데이터를 탐색한다는 의미이다. 리스트의 데이터에 하나씩 방문하며 특정한 문자열과 같은지 검사하므로 구현도 간단하다. 순차 탐색은 정말 자주 사용되는데, 리스트에 특정 값의 원소가 있는지 체크할 떄도 순차 탐색으로 원소를 확인하고, 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때 도 내부에서는 순차 탐색이 수행된다. 순차 탐색을 파이썬 코드로 작성하면 다음과 같다.

순차 탐색 소스코드

# 순차 탐색 소스코드 구현
def sequential_search(n, target, array):
        # 각 원소를 하나씩 확인하며
        for i in range(n):
                # 현재의 원소가 찾고자 하는 원소와 동일한 경우
                if array[i] == target:
                        return i + 1 # 현재의 위치 변환 (인덱스는 0부터 시작하므로 1 더하기)
print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요")
input_data = input().split()
n = int(input_data[0])  # 원소의 개수
target = input_data[1] # 찾고자하는 문자열

print("앞서 작은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.")
array = input().split()

# 순차 탐색 수행 결과 출력
print(sequential_search(n, target, array))

생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.

5 Taeyoung

앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.

Juho Daeho Taeyoung Junghwan Mingu

3

소스코드를 실행하면 정상적으로 이름 문자열이 몇 번쨰 데이터인지 출력하는 것을 알 수 있다.

이처럼 순차 탐색은 데이터 정렬 여부와 상관없이 가장 앞에 있는 원소부터 하나씩 확인해야 한다는 점이 특징이다.

따라서 데이터의 개수가 N개일때 최대 N번의 비교 연산이 필요하므로 순차 탐색의 최악의 경우 시간 복잡도는 O(N)이다.

 

 

---

본 포스팅은 ‘이것이 코딩 테스트다 with 파이썬’을 읽고 공부한 내용을 바탕으로 작성하였습니다.

 

 

 

작성자 : 엄코딩 eomcoding