탐색
- 주어진 리스트에 특정한 값이 있는지 찾아 그 위치를 돌려주는 알고리즘
- 리스트에 찾는 값이 있다면 -1을 반환해준다.
리스트에 있는 첫 번째 자료부터 하나씩 비교하면서 같은 값이 나오면 그 위치를 결과로 돌려주고, 리스트 끝까지 찾아도 같은 값이 나오지 않으면 -1을 돌려주면 된다.
이 방법은 '리스트 안에 있는 원소를 하나씩 순차적으로 비교하면서 탐색한다'고 하여 '순차 탐색(Sequential search)'이라고 부른다.
1. 순차 탐색으로 특정 값의 위치 찾기
아래 코드에서는 순차 탐색 알고리즘을 이용해 주어진 리스트 [17, 92, 18, 33, 58, 5, 33, 42]에서 특정 값(18, 33, 900)을 찾아서 해당 위치 번호를 돌려주는 프로그램이다.
# 리스트에서 특정 숫자의 위치 찾기
# 입력: 리스트 a, 찾는 값 x
# 출력: 찾으면 그 값의 위치, 찾지 못하면 -1
def search_list(a, x):
n = len(a) # 입력 크기 n
for i in range(0, n): # 리스트 a의 모든 값을 차례로
if x == a[i]: # x 값과 비교하여
return i # 같으면 위치를 돌려준다.
return -1 # 끝까지 비교해도 없으면 -1을 돌려준다.
v = [17, 92, 18, 33, 58, 5, 33, 42]
print(search_list(v, 18)) # 2(순서상 세 번째지만, 위치 번호는 2)
print(search_list(v, 33)) # 3(33은 리스트에 두 번 나오지만 처음 나온 위치만 출력)
print(search_list(v, 900) # -1(900은 리스트에 없음)위 코드에서 주어진 리스트 v에서 18을 순차 탐색으로 찾는 과정에 대해 알아보자.
첫 번째 값(위치 번호는 0)인 17부터 차례로 비교하면서 18을 찾으면 해당 위치 번호인 2를 돌려준다. return i
만약 900과 같이 리스트에 없는 자료를 입력으로 넣을 경우에는 아래 그림과 같이 리스트의 끝까지 차례로 비교해도 900과 같은 값이 존재하지 않으므로 -1을 반환하게 된다. return -1
2. 알고리즘 분석
순차 탐색 알고리즘으로 원하는 값을 찾으려면 몇 번의 비교를 필요로 할까?
이 질문은 답하기 힘든 질문이다. 왜냐하면 경우에 따라서 다르기 때문이다.
찾는 값이 리스트의 맨 앞에 있다면 단 한 번만 비교해도 결과를 얻을 수 있다. 하지만 찾는 값이 리스트의 마지막에 있거나 아예 없다면 리스트의 끝까지 하나하나 비교해야 한다.
이처럼 경우에 따라 계산 횟수가 다를 때는 최선의 경우, 평균적인 경우, 최악의 경우로 나누어 각각 계산 복잡도를 생각해 보기도 한다. 물론 어느 경우든 나름대로 의미가 있지만, 최악의 경우를 분석했을 때 어떤 경우라도 그보다는 빨리 계산할 수 있을 것이다.
따라서 보수적인 관점에서 이 알고리즘을 최악의 경우로 분석해 보면 비교가 최대 n번 필요하고, 계산 복잡도는 O(n) 이다.
즉, 순차 탐색으로 스무 개의 자료 중에서 어떤 값을 찾으려면 비교를 최대 스무번 해야 하고, 백 개의 자료라면 비교를 최대 백 번 해야한다.
하지만 다행히도 우리는 사전의 첫 장부터 한 장씩 넘기면서 원하는 단어를 찾지 않는다. 사전의 단어는 가나다순 혹은 알파벳순으로 '정렬'되어 있기 때문이다. 그래서 아마 다음 글은 정렬일 것 같다!
오늘은 탐색 문제를 풀어봐야겠다.
