어느덧 정글 2주차가 되며 새로운 주제의 알고리즘 문제들을 맞이하게 되었다. 우선 이분 탐색(이진 검색)부터 포스팅을 해볼까 한다.
검색 알고리즘이란?
데이터 집합에서 원하는 값을 가진 원소를 찾아내는 알고리즘. 배열 검색, 연결 리스트 검색, 이진 검색 트리 검색 등 다양한 검색 알고리즘이 존재하지만 여기선 배열 검색에 관련된 알고리즘만 다루고 나머지는 다른 포스트에서 다루겠다.
- 선형 검색: 무작위로 늘어놓은 데이터 집합에서 검색을 수행합니다.
- 이진 검색: 일정한 규칙으로 늘어놓은 데이터 집합에서 아주 빠른 검색을 수행합니다.
- 해시법: 추가﹒삭제가 자주 일어나는 데이터 집합에서 아주 빠른 검색을 수행합니다.
- 체인법: 같은 해시값 데이터를 연결 리스트로 연결하는 방법입니다.
- 오픈 주소법: 데이터를 위한 해시값이 충돌할 때 재해시하는 방법입니다.
검색 기능만 생각한다면 계산 시간이 짧은 검색 알고리즘을 선택하면 되지만, 데이터의 추가﹒삭제 등 다른 기능도 자주 수행해야 한다면 검색 이외의 작업에 들어가는 비용을 종합 평가하여 알고리즘을 선택해야 한다. 따라서 선택할 수 있는 알고리즘이 다양한 경우에는 용도, 목적, 실행 속도, 자료구조 등 여러 사항을 고려해 선택해야 한다.
목차
- 선형 검색
- 이진 검색
- 해시법
1. 선형검색(Linear Search)
선형검색
배열에서 검색하는 방법 중 가장 기본적인 알고리즘, 직선 모양(선형)으로 늘어선 배열에서 검색하는 경우에 원하는 키값을 가진 원소를 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘이다. 순차 검색(sequential search)라고도 한다.
선형검색의 종료 조건
- 검색할 값을 찾지 못하고 배열의 맨 끝을 지나간 경우 ... 검색 실패
- 검색할 값과 같은 원소를 찾는 경우 ... 검색 성공
- 선형 검색의 종료 조건 1 - if i == len(a)가 성립하면 스캔 종료
- 선형 검색의 종료 조건 2 - if a[i] == key가 성립하면 스캔 종료
Code
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 += 1for문으로 구현
from typing import Any, Sequence
def seq_search(a: Sequence, key: Any) -> int:
for i in range(len(a)):
if a[i] == key:
return i
return -1보초법(setinel method)
선형 검색의 종료 조건을 판단하는 비용을 반으로 줄이는 방법
검색할 값을 배열의 맨 끝에 추가한다. 찾는 값이 원래 데이터에 존재하지 않아도 보초까지 스캔하는 단계에서 선형 검색의 종료 조건 2가 성립한다. 따라서 선형 검색 종료 조건 1은 판단할 필요가 없다. 따라서 반복을 종료하기 위해 판단하는 횟수가 절반으로 줄어든다.
from typing import Any, Sequence
import copy
'
def seq_search(seq: Sequence, key: Any) -> int:
a = copy.deepcopy(seq)
a.append(key)
i = 0
while True:
if a[i] == key:
break
i += 1
return -1 if i == len(seq) else i이진 검색(Binary Search)
이진 검색
이진 검색은 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색할 수 있는 알고리즘이다. 시간 복잡도가 O(log n)인 대표적인 로그 시간 알고리즘이며, 이진 탐색 트리(binary search tree)와도 유사한 점이 많지만 이진 탐색 트리는 정렬된 구조를 저장하고 탐색하는 '자료구조'라면, 이진 검색은 정렬된 배열에서 값을 찾아내는 '알고리즘' 자체를 지칭한다.
원리
검색 범위의 맨 앞, 맨 끝, 중앙의 인덱스를 각각 pl, pr, pc라고 하면, a[pc] 값과 key를 비교하여 검색 범위를 pc 앞쪽 또는 뒤쪽으로 반씩 좁혀 나간다.
검색 범위 좁히는 과정
-
a[pc] < key: 중앙(pc)에서 오른쪽으로 한 칸 이동하여 새로운 왼쪽 끝 pl로 지정하고, 검색 범위를 뒤쪽 절반으로 좁힌다.
-
a[pc] > key: 중앙(pc)에서 왼쪽으로 한 칸 이동하여 새로운 오른쪽 끝 pr로 지정하고, 검색 범위를 앞쪽 절반으로 좁힌다.
이진 검색의 종료 조건
-
a[pc]와 key가 일치하는 경우
-
검색 범위가 더이상 없는 경우
[reference]: https://study.com
Code
from typing import Any, Sequence
def bin_search(a: Sequence, key: Any) -> int:
pl = 0
pr = len(a)-1
while True:
pc = (pl+pr) // 2
if a[pc] == key:
return pc
elif key < a[pc]:
pl = pc+1
else:
pr = pc-1
if pl > pr:
break
return -1복잡도
프로그램의 실행 속도(또는 실행하는 데 필요한 시간)는 프로그램이 동작하는 하드웨어나 컴파일러 등의 조건에 따라 달라진다. 알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도(complexity)라고 한다.
- 시간 복잡도(time complexity): 실행하는 데 필요한 시간을 평가한다.
- 공간 복잡도(space complexity): 메모리(기억 공간)와 파일 공간이 얼마나 필요한지를 평가한다.
알고리즘을 구현할 때 두 복잡도의 균형이 필요하다.
O(f(n))과 O(g(n))의 동작을 연속으로 하는 경우 복잡도는 일반적으로 다음과 같이 나타낸다.
- O(f(n)) + O(g(n)) = O(max(f(n), g(n))
선형 검색의 시간 복잡도
O(n)
이진 검색의 시간 복잡도
O(log n)
+++ 이진 검색 알고리즘 버그 +++
사실 이진 검색 알고리즘에는 오랫동안 아무도 발견하지 못한 버그가 있었다.
mid = (left + right) // 2
left와 right를 더하고 결과를 반으로 나눠 가운데를 계산한다. 수학적으로 잘못된 점은 없지만 컴퓨터과학에서는 문제를 일으킬 만한 소지가 있는 코드다. 두 수를 더하면 항상 각각의 수보다 큰 수가 된다. 그러나 자료형에는 최댓값이 있다. left + right가 자료형의 최댓값을 넘어선다면, 좀 더 구체적으로 int형일 때 231-1을 넘어선다면, C에서는 예상치 못한 결과가 나오게 되고, 자바에서는 오류가 발생한다. 결과가 int 자료형이 허용하는 최댓값을 초과하므로 오버플로(Overflow)가 발생하기 때문이다.
그렇다면 이진 검색은 어떻게 구현할까?
left + (right - left) / 2를 계산하면 오버플로를 피하면서 정확한 mid 값을 구할 수 있다. 두 수를 더하고 그 합을 반으로 나누는 대신, 두 수의 뺄셈을 해서 그 차를 반으로 나눈 후 낮은 수에 더한다. (right - left)는 항상 right보다 작은 값이 나오므로 오버플로의 위험이 없다. (right - left) / 2를 더한 값은 right를 넘지 않으므로 이 역시 오버플로의 위험이 없다.
여기서는 나눗셈 결과가 실수형일 경우, 정수형으로 내림하는 부분을 포함해 계산하는 코드를 다음과 같이 정의할 수 있다.
mid = left + (right - left) // 2
사실 파이썬은 임의 정밀도 정수형을 지원하기 때문에, 이 문제에서 자유로우며 해당 사항이 없다. 그러나 이는 자료형이 엄격한 언어들에는 여전히 발생할 수 있는 문제이기 때문에 주의가 필요하며, 반드시 숙지해야 한다.
