[알고리즘] 탐색(순차 탐색,이진 탐색)

졸업이 얼마 남지 않아 자소서를 쓰고 있는데 쓸 말이 너무 없다...

바보 같이 가만히 있기보다는 계속 가다듬고 코딩 테스트와 면접 준비를 하는 것이 올바르다고 생각하여 알고리즘과 자료구조 공부를 병행하려 한다!!

 

오늘은 탐색에 대해 공부해보려고 한다.

 

탐색은 두 가지 방법이 있다.

순차 탐색과 이진 탐색이 있다.

 

처음 개념을 들었을 때 이진 탐색이 왜 필요한가?라는 생각으로 했었다.

이유는 충분히 순차 탐색도 나쁘지 않게 사용할 수 있지 않을까라는 생각 때문이었다.

 

하지만 시간이 지나고 난 뒤 내 생각은 변화했다 이유는 코딩 테스트 때문이다.

코딩 테스트 문제를 풀면서 다들 많이 겪었겠지만 범위가 너무 커 효율성이 오버 나는 경우가 왕왕 있다.

물론 탐색 문제가 아니고 그냥 알고리즘 사용이 잘못된 경우가 대부분이지만 순차 탐색 말고 이진 탐색을 알아두면 쓸 곳이 있을 거라 생각한다.

 

순차 탐색

말 그대로 순차적으로 탐색을 진행하는 방법이다.

arr=[A,B,C,D,E,F]

 

해당 배열에 값이 들어가 있다고 생각하고 'D'를 찾는 순차 탐색을 진행해보자.

 

 

def sequential_search(answer,arr):
	for i in range(len(arr)):
		if arr[i]==answer:
			return i
	return -1    

 

순차적으로 배열 0번부터 차례차례 내가 원하는 값이 맞는지 확인해보면 된다.

위에 그림대로 실행한다면 4번 만에 원하는 데이터를 찾게 된다.

하지만 만약 원하는 데이터가 F라면 6번의 연산을 거쳐 데이터를 찾게 된다.

 

그래서 순차 탐색의 최악의 경우에는 n번의 연산을 수행해야 하고 따라서 시간 복잡도는 최악의 경우 O(N)이다. 

 

순차 탐색은 간단하고 어렵지 않고 쓰기 편하다. 

 

이제 이진 탐색을 알아보자

 

이진 탐색

이진 탐색은 내부 데이터가 정렬되어 있어야 사용할 수 있는 탐색 알고리즘으로 세 개의 점(시작점, 끝점, 중간점)을 구하고  원하는 데이터와 중간점을 비교하여 구간을 좁혀나가 원하는 데이터를 구하는 알고리즘이다.

 

 

arr=[1,2,3,4,5,6,7,8,9,10]

 

해당 배열에서 '9'를 찾는 이진 탐색을 진행해보자.

 

시작점과 끝점을 정하고 중간점이 '9'인지 확인한다. 만약 중간점이 9가 아니라면 중간점의 배열 값을 확인하여 '9'보다 큰지 확인한다. 만약 작다면 중간점+1을 시작점으로 변경하고 크다면 중간점-1을 끝점으로 변경한다.

위에 사례에서는 9보다 작으니 중간점+1을 시작점으로 변경한다.

 

이전 중간점을 시작점으로 변경하고 시작점과 끝점 사이에 설정한 중간점과 중간점의 데이터를 비교한다.

중간점의 데이터와 설정한 데이터 값('9')이 아닐 경우는 위에 루틴을 반복한다.

위와 같이 만약 설정한 데이터 값이 맞은 경우에는 루틴을 끝낸다.

 

def binary_search(arr,start,end,answer):#재귀 함수를 위해 arr,start,end,answer를 매개변수로 설정.
	if start>end:
		return -1
	mid=int((start+end)/2)    
	if arr[mid]==answer:#원하는 데이터를 찾았을 때
		return mid
	elif arr[mid]>answer:#중간값이 원하는 데이터보다 클 때
		binary_search(arr,start,mid-1,answer):
	elif arr[mid]<answer:#중간값이 원하는 데이터보다 작을 때
		binary_search(arr,start,mid+1,answer):

 

 

위에 그림은 만약 순차 탐색이었으면 9번의 연산을 거쳤겠지만 이진 탐색이기 때문에 3번의 연산만에 답을 도출해낼 수 있었다.

여기서 알 수 있는 것은 연산을 할 때마다 데이터의 반이 줄어들기 때문에 시간 복잡도는 O(logN)이다. 

 

 

보통 이진 탐색은 코딩 테스트 조건에서 데이터량(조건이 클때)이 많을 때 사용하면 좋다.