이진 탐색 정복기1 -기본 이론 순차 탐색?-

리스트 내에서 데이터를 매우 빠르게 탐색하는 알고리즘에 대하여

 

 

1. 순차 탐색

 

가장 기본적인 탐색 방법

 

n개의 데이터가 있을 때, 데이터를 차례대로 하나씩 확인하여 어떠한 처리를 해준 그 자체가 바로 순차 탐색이다.

 

순차 탐색(sequential search)이란 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

 

정렬되지 않은 리스트에서 데이터를 찾아야할때

 

리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 원소를 찾을 수 있다

 

 

2. 순차 탐색으로 'IU'를 찾는 과정

 

 

1) 먼저 첫번째 데이터 'Daehyuck'는 찾고자 하는 문자열 'IU'와는 다르다. 따라서 다음 데이터로 이동

 

2) 두번째 데이터 'Taeyeon'은 찾고자 하는 'IU'와는 다르다. 따라서 다음 데이터로 이동

 

3) 세번째 데이터 'IU'는 찾고자 하는 문자열과 같으므로 탐색을 종료

 

---------------------------------------------------------------------

 

3. 구현예시

 

순차 탐색은 이름처럼 순차로 데이터를 탐색한다는 의미이다. 

 

리스트의 데이터에 하나씩 방문하여 특정한 문자열과 같은지 검사하므로 구현도 간단하다

 

순차 탐색은 정말 자주 사용되는데, 

 

리스트에 특정 값의 원소가 있는지 체크할 때도 순차 탐색으로 원소를 확인하고

 

리스트 자료형에 특정한 값을 가지는 원소의 개수를 세는 count() 메소드를 이용할 때도 내부에서는 순차 탐색이 수행된다

 

#순차탐색 소스코드 구현

def sequential_search(n, target, array):
    
    #각 원소를 하나씩 확인

    for i in range(n):
        
        #현재 원소가 찾고자 하는 원소와 동일한 경우

        if array[i] == target:
            
            return i+1 #현재 위치를 반환함(0부터 시작하는 인덱스에 1을 더해서)

 

아주 간단하게 리스트의 길이 n에 대하여 range(n)을 순회하여 array[i]가 찾고자하는 target과 같으면 바로 그 위치 i+1을 return하면 된다

 

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

 

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 IU
앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.
Daehyuck Taeyeon IU Suzy Minkyung
3

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

 

데이터의 개수가 N개일 때 최대 N번의 비교 연산을 수행하므로 최악의 경우 O(N)의 시간복잡도가 필요하다.