검색 알고리즘
검색 알고리즘이란 데이터의 집합에서 원하는 값을 가진 원소를 찾아내는 알고리즘 이다.
검색과 키
어떠한 검색 조건이 주어졌을 때, 그 검색조건이 주목하는 항목을 키라고 한다.
예를 들어 국적으로 검색을 하는 경우 국적이 키이고, 나이로 검색을 하는 경우 나이가 키이다.
국적이 프랑스인 사람을 찾습니다.
나이가 20세 이상 48세 이상인 사람을 찾습니다.
검색의 종류
알고리즘에는 다양한 검색 방법이 존재하지만 일단은 크게 3가지로 나눠보자.
이 중에서 이번에 알아볼 검색 방법은 배열 검색이다. 배열 검색은 또 다음과 같은 3가지로 나뉜다. 각각에 대해 자세히 알아보자.
- 선형 검색
- 이진 검색
- 해시법
선형 검색
선형 검색
선형 검색이란 직선 모양(선형)으로 늘어선 배열에서 원하는 키 값을 가진 원소를 찾기위해 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘이다.
선형 검색 과정에서 배열 스캔이 종료하는 조건은 다음과 같은 2가지이다.
- 검색할 값을 찾지 못해 배열의 맨 끝을 지나간 경우 (=검색 실패)
- 검색할 값과 같은 원소를 찾는 경우 (=검색 성공)
위의 종료 조건을 다음과 같이 작성할 수 있다.
i = 0
while True:
if i = len(a): #검색 실패
#스캔 종료
if a[i] = key: #검색 성공
#스캔 종료
i += 1 선형 검색 실습
선형 검색 알고리즘 실습 프로그램은 다음과 같다.
from typing import Any, Sequence
def seq_search(a:Sequence, key:Any) -> int:
i = 0
while True:
if i == len(a) :
return -1 #검색 실패시(key값을 찾지 못하고 배열을 맨 끝까지 간 경우) -1을 반환
if a[i] == key:
return i #검색 성공시 현재 위치의 인덱스를 반환
i += 1
if __name__ == '__main__' :
num = int(input('원소 수를 입력하세요.: '))
x = [None] * num #입력 받은 원소 수 만큼 빈 공간을 가지는 배열 생성
for i in range(num): #빈 배열 채우기
x[i] = int(input(f'x[{i}]:'))
ky = int(input('검색할 값을 입력하세요.: ')) #검색 할 key값을 입력 받음
idx = seq_search(x, ky) # x 배열에서 ky와 같이 같은 원소를 검색
if idx == -1:
print('검색값을 갖는 원소가 존재하지 않습니다.')
else:
print(f'검색값은 x[{idx}]에 있습니다.')
while문 대신 for문을 사용하면 더 간결하게 프로그램을 작성 가능하다.
from typing import Any, Sequence
def seq_search(a:Sequence, key:Any) -> int:
i = 0
for i in range(len(a)):
if a[i] == key: #검색 성공 시 그 위치의 인덱스 값을 반환
return i
return -1 #검색에 실패해 배열의 맨 끝에 도다한 경우 -1을 반환
if __name__ == '__main__' :
num = int(input('원소 수를 입력하세요.: '))
x = [None] * num #입력 받은 원소 수 만큼 빈 공간을 가지는 배열 생성
for i in range(num): #빈 배열 채우기
x[i] = int(input(f'x[{i}]:'))
ky = int(input('검색할 값을 입력하세요.: ')) #검색 할 key값을 입력 받음
idx = seq_search(x, ky) # x 배열에서 ky와 같이 같은 원소를 검색
if idx == -1:
print('검색값을 갖는 원소가 존재하지 않습니다.')
else:
print(f'검색값은 x[{idx}]에 있습니다.')보초법
앞서 말했듯이 선형 검색의 스캔 종료 조건은 다음 2가지이다.
- 검색할 값을 찾지 못해 배열의 맨 끝을 지나간 경우 (=검색 실패)
- 검색할 값과 같은 원소를 찾는 경우 (=검색 성공)
보초법을 사용하면 위의 두 조건 중 첫번째 조건에 대하여 판단할 필요가 없어져 종료 조건을 검사하는 비용을 간단하게 할 수 있다.
배열의 원소 a[0]~a[6]까지는 원래 데이터이고 검색하고 하는 key값을 배열의 맨 끝 a[7]에 저장한다. 이때 저장하는 값을 보초라고 한다.
그림b에서 key값이 기존의 배열에 존재하지 않아도 보초인 a[7]까지 스캔하게되면 선형 검색의 두번째 종료 조건을 만족하게 된다.
따라서 보초를 추가하면 선형 검색의 첫번재 종료 조건을 고려대상에서 벗어나는 것이다.
보초법을 반영하여 기존의 프로그램을 수정해보자.
from typing import Any, Sequence
import copy
def seq_search(seq:Sequence, key:Any) -> int:
a = copy.deepcopy(seq) #배열 seq를 복사하기
a.append(key) #복사본의 맨 뒤에 보초 key를 추가하기
i = 0
while True:
if a[i] == key:
break
i += 1
return -1 if i == len(seq) else i
if __name__ == '__main__' :
num = int(input('원소 수를 입력하세요.: '))
x = [None] * num #입력 받은 원소 수 만큼 빈 공간을 가지는 배열 생성
for i in range(num): #빈 배열 채우기
x[i] = int(input(f'x[{i}]:'))
ky = int(input('검색할 값을 입력하세요.: ')) #검색 할 key값을 입력 받음
idx = seq_search(x, ky) # x 배열에서 ky와 같이 같은 원소를 검색
if idx == -1:
print('검색값을 갖는 원소가 존재하지 않습니다.')
else:
print(f'검색값은 x[{idx}]에 있습니다.')보초법을 통해 선형 검색의 첫번째 종료 조건이 고려대상에서 벗어났기 때문에 while문 안에서 if문은 1개뿐이다. 따라서 반복을 종료하기 위해 판단하는 횟수가 절반으로 줄어든다.
이진 검색
이진 검색
이진 검색 알고리즘을 사용하려면 배열의 데이터가 정렬되어 있어야 한다. 이진 검색을 사용하면 선형 검색보다 더 빠르게 검색할 수 있다.
오름차순으로 정렬된 배열에서 76(key값)을 찾는 과정을 알아보자.
1) 배열의 중앙에 위치한 원소 47에 주목하자.
2) 76은 중앙 원소인 47보다 뒤에 존재하기 때문에 검색 범위는 47 이후부터로 좁힐 수 있다. 이어서 업데이트된 대상 범위의 중앙 원소인 77에 주목하자.
3) 76은 중앙 원소인 77보다 앞에 존재하기 때문에 검색 범위를 다시 좁힐 수 있다. 이어서 업데이트된 대상 범위의 중앙 원소인 64에 주목하자.
4) 76은 중앙 원소인 64보다 뒤에 존재하기 때문에 검색 범위를 다시 좁힐 수 있다. 이어서 업데이트된 대상 범위의 중앙 원소인 76에 주목하자. 중앙 원소와 찾아야 할 값이 일치하므로 검색에 성공했다.
앞의 과정을 일반화 시켜보자.
n개의 원소가 오름차순으로 정렬된 배열 a에서 검색 범위의 맨 앞, 맨 끝, 중앙의 인덱스를 각각 pl, pr, pc라고 정의하자.
검색을 시작할 때, pl = 0, pr = n-1, pc = (n-1)//2로 초기화하자.
이진 검색을 한 단계씩 진행할 때 마다 검색 범위는 반으로 좁혀진다. 검색 범위를 좁히는 방법은 다음과 같다.
1) a[pc] < key 일 때
a[pl] ~ a[pc]는 key보다 작은 것이 분명하므로 검색 대상에서 제외한다. 따라서 검색 범위를 pc보다 뒤인 a[pc+1] ~ a[pr]로 좁힐 수 있다. a[pl]의 값을 a[pc+1]로 업데이트하자.
2) a[pc] > key 일 때
a[pc] ~ a[pr]는 key보다 큰 것이 분명하므로 검색 대상에서 제외한다. 따라서 검색 범위를 pc보다 앞인 a[pl] ~ a[pc-1]로 좁힐 수 있다. a[pr]의 값을 a[pc-1]로 업데이트하자.
이진 검색 알고리즘의 종료 조건은 다음 조건 중 하나만 성립하면 된다.
조건 1) a[pc]와 key가 일치하는 경우
조건 2) 검색 범위가 더 이상 없는 경우
조건 2가 성립하여 검색에 실패하는 예를 살펴보자.
위와 같은 배열에서 6을 검색하기 위해 검색 범위를 줄여나가는 과정에서 pl이 pr보다 커지면 검색 범위가 더 이상 없어진다.
이진 검색 실습
from typing import Any, Sequence
def bin_search(a: Sequence, key: Any) -> int:
#시퀀스 a에서 key와 일치하는 원소를 이진 검색
pl = 0
pr = len(a)-1
while True:
pc = (pl+pr)//2
if a[pc] == key: # 검색 성공
return pc
elif a[pc] < key: # 검색 범위를 뒤쪽 절반으로 좁힘
pl = pc + 1
else: # 검색 범위를 앞쪽 절반으로 좁힘
pr = pc - 1
if pl > pc:
break
return -1 # 검색 실패
if __name__ == '__main__':
num = int(input('원소 수를 입력하세요: '))
x = [None] * num #원소 수가 num인 배열을 생성
print('배열 데이터를 오름차순으로 입력하세요')
x[0] = int(input('x[0]: '))
for i in range(1, num):
while True:
x[i] = int(input(f'x[{i}]: '))
if x[i] >= x[i-1]:
break
ky = int(input('검색할 값을 입력하세요: '))
idx = bin_search(x, ky)
if idx == -1:
print('검색 값을 갖는 원소가 존재하지 않습니다')
else:
print(f'검색값은 x[{idx}]에 있습니다') 이진 검색에서는 검색 대상 배열이 오름차순으로 정렬되어 있음을 전제로 한다. 따라서 배열 데이터를 입력 받는 과정에서 앞에 입력한 원소보다 작은 값을 입력하는 경우 다시 입력하도록 유도한다.
복잡도
프로그램의 실행 속도는 프로그램이 동작하는 하드웨어나 컴파일러 등의 조건에 따라 달라진다. 알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도라고 한다.
시간 복잡도(time complexity) : 실행하는 데 필요한 시간을 평가
공간 복잡도(space complexity) : 메모리와 파일 공간이 얼마나 필요한지를 평가
선형 검색과 이진 검색의 시간 복잡도는 각각 O(n), O(log n)이다.
index()함수로 검색하기
리스트나 튜플에서 검색은 index()함수로 수행할 수 있다.
obj.index(x,i,j)리스트나 튜플 obj[i:j] 안에 x와 같은 원소가 있으면 그 가운데 가장 작은 인덱스를 반환한다. 또 x와 값이 같은 원소가 obj에 없으면 예외처리로 ValueError를 내보낸다.
