이진탐색이란?
정렬된 리스트에서 목표값을 찾을 때
찾는 시간을 줄이기 위해서 중간값을 기준으로 목표값보다 크냐 작냐에 따라서
검색 범위를 절반씩 줄여가며 탐색하는 방법이다.
O(logN)으로 실행시간이 짧게 나온다.
왜 시간복잡도가 O(logN)으로 나올까?
검색 범위를 1/2씩 줄여서 데이터 수를 N이라고 할 때 계산횟수가 logN이 되기 때문이다.
이때 logN은 밑이 2인 로그를 뜻한다. 컴퓨터는 0과1인 이진으로만 동작하기 때문입니다.
예를 들어 8개의 데이터를 들어왔을 때 log8=3으로 계산횟수가 3이 됩니다.
이진탐색 예제코드
아래의 예제 코드를 보며 이진 탐색이 구현된 코드를 자세히 알아보도록 하자.
백준 알고리즘 1920번
import sys
input = sys.stdin.readline
N = int(input())
N_list = list(map(int,input().split(" ")))
N_list.sort()
M = int(input())
M_list = list(map(int,input().split(" ")))
def binary_search(target, data_list):
start, end = 0, N-1
while(start<=end):
middle=(start+end)//2
middleValue = N_list[middle]
if middleValue == num:
return True
elif num > middleValue:
start=middle+1
elif num < middleValue:
end=middle-1
return False
for num in M_list:
if binary_search(num,N_list):
print(1)
else:
print(0)코드를 보면 def binary_search에 이진탐색 알고리즘이 적용되었다.
기준값인 middle을 기준으로 구하려는 값인 num보다 큰지 작은지에 따라
다음 탐색할 범위를 좁혀나가는 방식이다. 탐색할 범위는 start, end로 표현했다.
탐색 시행 1회마다 탐색할 범위가 1/2로 줄기 때문에
알고리즘 실행시간은 O(logN)이 된다.
퀵소트
정렬 알고리즘 중에서 검색시간이 O(NlogN)인 알고리즘으로
비교연산자를 사용한 정렬 알고리즘 중
가장 빠른 알고리즘으로 알려져 있다.
import sys
input = sys.stdin.readline
array = [2,8,7,1,3,5,6,4]
def quick_sort(array,start,end):
if start>= end: # 원소가 1개인 경우 종료
return
pivot = start # pivot 은 첫 번째 원소
left = start + 1
right = end
while left<=right:
# 피벗보다 큰 데이터를 찾을 때까지 반복
while left<=end and array[left]<=array[pivot]:
left +=1
while right>start and array[right]>= array[pivot]:
right-=1
if left>right: #엇갈렸다면 작은 데이터와 피벗을 교체
array[right],array[pivot]= array[pivot],array[right]
else: #엇갈리지 않았다면 작은 데이터와 큰 데이터를 교체
array[left],array[right]=array[right],array[left]
#분할 이후 왼쪽 부분과 오른쪽 부분에서 각각 다시 정렬 수행
quick_sort(array, start,right-1)
quick_sort(array,right+1,end)
quick_sort(array,0,len(array)-1)
print(array)해시 테이블
해시 테이블이란 키-값 쌍을 저장하는 데이터 구조입니다.
해시 테이블이란 이름은 붙은 이유는 해시 함수를 사용하여
임의의 크기를 가진 키를 고정된 크기의 인덱스로 변환하는 것입니다.
이 인덱스는
해시 테이블은 왜 쓰는 걸까?
결론부터 얘기하면 메모리에 저장한 데이터를 빠르게 탐색,삽입,삭제하기 위해서
스택이나 큐의 경우 데이터를 탐색,삽입,삭제할 때 평균 시간복잡도는 θ(N)이지만
해시 테이블은 평균 시간복잡도가 θ(1)로 비교적 더 빠르다.
다만 해시 충돌등으로 찾아야 하는 주소값이 많아지는 경우 상한 시간 복잡도는 O(N)이 되기도 한다.
하지만 해시 충돌만 잘 다룬다면 대부분의 경우에서 데이터 검색이 빠르기 때문에 선호된다.
해시 충돌이란?
해시충돌이란? 해시함수에 서로 다른 입력값이 들어갔을 때 같은 출력값이 나오는 경우를 말한다.
예를 들어, 해시 테이블에 '키=과일이름, 값=과일 가격' 라고 가정해보자.
def 과일 해시함수(과일 이름):
return 과일 이름의 획수사과, 딸기, 포도, 배, 귤이 데이터의 키로 들어왔을 때
획수를 구하는 해시함수에 입력값으로 넣는다면
사과=10, 딸기=13, 포도=11, 배=7, 귤=10
이런 결과가 나올 것이다
이때 '사과'와 '귤'이 10으로 같은 해시값으로 '해시 충돌'이 발생한다.
즉 같은 해시값을 따로 구분해서 저장해줘야한다.
해시 충돌을 해결하는 방법
대표적으로 2가지 방법이 있다.
- 오픈 주소법: 해시값이 이미 인덱스에 저장되어 있는 경우
해시값을 재해시해서 다른 곳에 저장하는 방법이다. - 체인법: 키,값이 저장되어야할 인덱스를 연결리스트로 구현해
같은 해시값이라도 여러 {키,값}이 저장될 수 있도록 한다.
인덱스에 {키,값}뿐만 아니라 다음 {키,값} 노드의 메모리주소도 지정한다.
| 비교 | 오픈 주소법 | 체인법 |
|---|---|---|
| 강점 | 추가적인 메모리 사용이 없다. | 충돌이 발생해도 검색 속도가 더 빠르다. |
| 단점 | 충돌 발생시 검색 속도가 더 느리다. | 추가적인 메모리가 필요하다. |
