Preface
이번 장에선 배열 내에서 특정 데이터 값을 찾는 검색 알고리즘에 대해 공부했다.
선형 검색을 수행하는 코드를 작성해 본 후 보초법에 대한 설명을 읽어봤을 땐 어디서 반복을 줄여준다는 것인지 이해가 가지 않았다.
그러나 두 코드를 주의깊게 비교해보니 while 문 내에서 if 문의 개수가 다르다는 것을 알 수 있었다.
알고리즘을 정확히 공부하고 코딩 실력을 향상시키기 위해선 코드 내에서의 미세한 차이가 결과적으론 큰 차이를 이끌어낼 수 있다는 것을 항상 명심하자.
1. 검색 알고리즘이란?
- 키(key) : 검색 조건에서 주목하는 항목
→ 대부분 키는 데이터의 일부이다.
- 검색의 종류
1) 배열 검색
2) 연결 리스트 검색
3) 이진 검색 트리 검색
- 배열 검색 알고리즘
1) 선형 검색 : 무작위로 늘어놓은 데이터 집합에서 검색 수행
2) 이진 검색 : 일정한 규칙으로 늘어놓은 데이터 집합에서 빠른 검색 수행
3) 해시법 : 추가 · 삭제가 자주 일어나는 데이터 집합에서 빠른 검색 수행
4) 체인법 : 같은 해시값 데이터를 연결 리스트로 연결하는 방법
5) 오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시 하는 방법
→ 여러 사항을 고려해서 검색 알고리즘을 선택하는 것이 중요하다.
2. 선형 검색
- 선형 검색(순차 검색) : 직선 모양으로 늘어선 배열에서 검색하는 경우, 원하는 키값을 가진 원소를 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘
- 선형 검색의 종료 조건
1) 검색할 값을 찾지 못하고 배열의 맨 끝을 지나간 경우
2) 검색할 값과 같은 원소를 찾은 경우
- 선형 검색 코드
from typing import Any, Sequence
def seq_search(a: Sequence, key: Any) -> int:
i = 0
while True:
if i == len(a):
return -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('검색할 값을 입력하세요.:'))
idx = seq_search(x, ky)
if idx == -1:
print('검색값을 갖는 원소가 존재하지 않습니다.')
else:
print(f'검색값은 x[{idx}]에 있습니다.')
- 보초법 : 원래 데이터의 맨 끝에 검색하고자 하는 키값을 추가하여 검색하는 방법
→ 반복을 종료하는 판단 횟수를 줄여준다.
- 보초법 코드
from typing import Any, Sequence
import copy
def seq_search(seq: Sequence, key: Any) -> int:
a = copy.deepcopy((list(seq)))
a.append(key)
i = 0
while True:
if a[i] == key:
break
i += 1
if i == len(seq):
return -1
else:
return 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('검색할 값을 입력하세요.:'))
idx = seq_search(x, ky)
if idx == -1:
print('검색값을 갖는 원소가 존재하지 않습니다.')
else:
print(f'검색값은 x[{idx}]에 있습니다.')
댓글