03. 검색 알고리즘
03-1. 검색 알고리즘이란?
검색과 키
키 key : 검색 조건이 주목하는 항목(데이터의 일부)
검색의 종류
배열 검색, 연결 리스트 검색, 이진 검색 트리 검색 등
배열 검색
선형 검색
무작위로 늘어놓은 데이터 집합에서 검색 수행
이진 검색
일정한 규칙으로 늘어놓은 데이터 집합에서 아주 빠른 검색 수행
해시법
추가 · 삭제가 자주 일어나는 데이터 집합에서 아주 빠른 검색 수행
- 체인법 : 같은 해시값 데이터를 연결 리스트로 연결
- 오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시
03-2 선형 검색
선형 검색 linear search
직선 모양(선형)으로 늘어선 배열에서 검색하는 경우, 원하는 키값을 가진 원소를 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘
= 순차 검색 sequential search
선형 검색의 종료 조건
- 검색 실패 : 검색할 값을 찾지 못하고 배열의 맨 끝을 지나간 경우
- 검색 성공 : 검색할 값과 같은 원소를 찾는 경우
-> 해당 조건을 판단하는 평균 횟수 : 배열 원소의 개수 / 2번
## 선형 검색 pseudo code
i = 0
while True:
if i == len(a):
# 검색 실패
if a[i] == key:
# 검색 성공(찾은 원소의 인덱스는 i)
i += 1
# [Do it! 실습 3-1] while 문으로 작성한 선형 검색 알고리즘
from typing import Any, Sequence
def seq_search(a: Sequence, key: Any) -> int:
"""시퀀스 a에서 key값이 같은 원소를 선형 검색(while 문)"""
i = 0
while True:
if i == len(a):
return -1 # 검색에 실패하여 -1을 반환
if a[i] == key:
return i # 검색에 성공하여 현재 조사한 배열의 인덱스를 반환
i += 1
if __name__ == '__main__':
num = int(input('원소 수를 입력하세요.: ')) # num 값을 입력
x = [None] * num # 원소 수가 num인 배열을 생성
for i in range(num):
x[i] = int(input(f'x[{i}]: '))
key = int(input('검색할 값을 입력하세요.: ')) # 검색할 키 key를 입력받기
idx = seq_search(x, key) # key와 같은 원소를 x에서 검색
if idx == -1:
print('검색값을 갖는 원소가 존재하지 않습니다.')
else:
print(f'검색값은 x[{idx}]에 있습니다.')
# 실행 결과
원소 수를 입력하세요.:5
x[0]: 1
x[1]: 2
x[2]: 3
x[3]: 4
x[4]: 5
검색할 값을 입력하세요.: 3
검색값은 x[2]에 있습니다.
while문을 for문으로 리팩토링
# [Do it! 실습 3-2] for 문으로 작성한 선형 검색 알고리즘
from typing import Any, Sequence
def seq_search(a: Sequence, key: Any) -> int:
"""시퀀스 a에서 key값이 같은 요소를 선형 검색(for문)"""
for i in range(len(a)):
if a[i] == key:
return i # 검색 성공(인덱스를 반환)
return -1 # 검색 실패(-1을 반환)
if __name__ == '__main__':
num = int(input('원소 수를 입력하세요.: ')) # num 값을 입력
x = [None] * num # 원소 수가 num인 배열을 생성
for i in range(num):
x[i] = int(input(f'x[{i}]: '))
key = int(input('검색할 값을 입력하세요.: ')) # 검색할 키 key를 입력받음
idx = seq_search(x, key) # key와 같은 값의 요소를 x에서 검색
if idx == -1:
print('검색 값을 갖는 요소가 존재하지 않습니다.')
else:
print(f'검색 값은 x[{idx}]에 있습니다.')
# 실행 결과
원소 수를 입력하세요.: 3
x[0]: 5
검색할 값을 입력하세요.: 2
검색 값을 갖는 요소가 존재하지 않습니다.
x[1]: 4
검색할 값을 입력하세요.: 3
검색 값을 갖는 요소가 존재하지 않습니다.
x[2]: 2
검색할 값을 입력하세요.: 2
검색 값은 x[2]에 있습니다.
03-3 이진 검색
이진 검색 binary search
원소가 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색할 수 있는 알고리즘
선형 검색보다 빠르게 검색 가능
이진 검색 알고리즘을 실행하는 프로그램
# [Do it! 실습 3-3] 이진 검색 알고리즘
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 > pr:
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('검색할 값을 입력하세요.: ')) # 검색할 ky를 입력
idx = bin_search(x, ky) # ky와 같은 값의 원소를 x에서 검색
if idx < 0:
print('검색값을 갖는 원소가 존재하지 않습니다.')
else:
print(f'검색값은 x[{idx}]에 있습니다.')
# 실행 결과
원소 수를 입력하세요.: 5
배열 데이터를 오름차순으로 입력하세요.
x[0]: 1
x[1]: 2
x[2]: 3
x[3]: 4
x[4]: 5
검색할 값을 입력하세요.: 3
검색값은 x[2]에 있습니다.
복잡도 complexity
종류
시간 복잡도 time complexity : 실행하는 데 필요한 시간 평가
공간 복잡도 space complexity: 메모리(기억 공간)와 파일 공간이 얼마나 필요한지 평가
선형 검색의 시간 복잡도
선형 알고리즘의 복잡도 = O(n)
def seq_search(a: Sequence, key: Any) -> int:
i = 0 # 1단계
while i < n # 2단계
if a[i] == key: # 3단계
return i # 4단계 검색에 성공하여 인덱스를 반환
i += 1 # 5단계
return -1 # 6단계 검색에 실패하여 -1을 반환
단계 | 실행 횟수 | 복잡도 |
1 | 1 | O(1) |
2 | n/2 | O(n) |
3 | n/2 | O(n) |
4 | 1 | O(1) |
5 | n/2 | O(n) |
6 | 1 | O(1) |
이진 검색의 시간 복잡도
선형 알고리즘의 복잡도 = O(log n)
def bin search(a: Sequence, key: Any) -> int:
"""시퀀스 a에서 key와 일치하는 원소를 이진 검색"""
pl = 0 # 1단계: 검색 범위 맨 앞 원소의 인덱스
pr = len(a) - 1 # 2단계: 검색 범위 맨 끝 원소의 인덱스
while True:
pc = (pl + pr) // 2 # 3단계: 중앙 원소의 인덱스
if a[pc] == key: # 4단계
return pc # 5단계: 검색 성공
elif a[pc] < key: # 6단계
pl = pc + 1 # 7단계: 검색 범위를 뒤쪽 절반으로 좁힘
else:
pr = pc - 1 # 8단계: 검색 범위를 앞쪽 절반으로 좁힘
if pl > pr: # 9단게
break
return -1 # 10단계: 검색 실패
단계 | 실행 횟수 | 복잡도 |
1 | 1 | O(1) |
2 | 1 | O(1) |
3 | log n | O(log n) |
4 | log n | O(log n) |
5 | 1 | O(1) |
6 | log n | O(log n) |
7 | log n | O(log n) |
8 | log n | O(log n) |
9 | log n | O(log n) |
10 | 1 | O(1) |
이진 검색의 실행 과정 출력하기
# [Do it! 실습 3C-3] 이진 검색 알고리즘의 실행 과정을 출력
from typing import Any, Sequence
def bin_search(a: Sequence, key: Any) -> int:
"""시퀀스 a에서 key와 일치하는 원소를 이진 검색(실행 과정을 출력)"""
pl = 0 # 검색 범위 맨 앞 원소의 인덱스
pr = len(a) - 1 # 검색 범위 맨 끝 원소의 인덱스
print(' |', end='')
for i in range(len(a)):
print(f'{i : 4}', end='')
print()
print('---+' + (4 * len(a) + 2) * '-')
while True:
pc = (pl + pr) // 2 # 중앙 원소의 인덱스
print(' |', end='')
if pl != pc: # pl 원소 위에 <-를 출력
print((pl * 4 + 1) * ' ' + '<-' + ((pc - pl) * 4) * ' ' + '+', end='')
else:
print((pc * 4 + 1) * ' ' + '<+', end='')
if pc != pr: # pr 원소 위에 ->를 출력
print(((pr - pc) * 4 - 2) * ' ' + '->')
else:
print('->')
print(f'{pc:3}|', end='')
for i in range(len(a)):
print(f'{a[i]:4}', end='')
print('\n |')
if a[pc] == key:
return pc # 검색 성공
elif a[pc] < key:
pl = pc + 1 # 검색 범위를 뒤쪽의 절반으로 좁힘
else:
pr = pc - 1 # 검색 범위를 앞쪽의 절반으로 좁힘
if pl > pr:
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('검색할 값을 입력하세요.: ')) # 검색할 ky를 입력
idx = bin_search(x, ky) # ky와 같은 값의 원소를 x에서 검색
if idx == -1:
print('검색값을 갖는 원소가 존재하지 않습니다.')
else:
print(f'검색값은 x[{idx}]에 있습니다.')
# 실행 결과
원소 수를 입력하세요.: 11
배열 데이터를 오름차순으로 입력하세요.
x[0]: 1
x[1]: 2
x[2]: 3
x[3]: 4
x[4]: 5
x[5]: 6
x[6]: 7
x[7]: 8
x[8]: 9
x[9]: 10
x[10]: 11
검색할 값을 입력하세요.: 8
| 0 1 2 3 4 5 6 7 8 9 10
---+----------------------------------------------
| <- + ->
5| 1 2 3 4 5 6 7 8 9 10 11
|
| <- + ->
8| 1 2 3 4 5 6 7 8 9 10 11
|
| <+ ->
6| 1 2 3 4 5 6 7 8 9 10 11
|
| <+->
7| 1 2 3 4 5 6 7 8 9 10 11
|
검색값은 x[7]에 있습니다.
'공부 > TIL' 카테고리의 다른 글
[Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편] 03. 검색 알고리즘-2 (0) | 2024.05.29 |
---|---|
[Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편] 02. 기본 자료구조와 배열 (0) | 2024.02.01 |
[Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편] 01. 알고리즘 기초 (1) | 2024.01.26 |
[한 권으로 읽는 컴퓨터 구조와 프로그래밍] (0) | 2024.01.17 |
[SQL 첫걸음] 32강 - 36강 (0) | 2024.01.15 |