[알고리즘-공부] 1. 알고리즘의 첫걸음(1) - 순차탐색, 이진탐색

1.1 최대 숫자 찾기 : 순차탐색

가장 큰 숫자가 적힌 카드를 찾는 한 가지 방법은 카드의 숫자를 하나씩 비교하면서 본 숫자들 중에서 가장 큰 숫자를 기억해가며 진행하는 방법이다. 마지막 카드의 숫자를 본 후에, 머릿속에 기억된 가장 큰 숫자가 적힌 카드를 바닥에서 집어든다.

순차탐색 : 카드를 한 장씩 차례대로 읽어가며 찾는 방법

ex) 17, 92, 18, 33, 58, 7, 33, 42 중 최댓값을 찾기

코드로 생각해보자

#최댓값 구하기 #입력 : 숫자가 n개 들어 있는 리스트 #출력 : 숫자 n개 중 최댓값 def find_max(arr): n = len(arr) #입력크기 n max_arr = arr[0] #리스트의 첫 번째 값을 최댓값으로 기억 for i in range(1,n): #1부터 n-1까지 반복 if arr[i] > max_arr: #이번 값이 현재까지 기억된 최댓값보다 크면 max_arr = arr[i] #최댓값을 변경 return max_arr arr = [17, 92, 18, 33, 58, 7, 33, 42] print(find_max(arr))

값 : 92

 

1.2 임의의 숫자 찾기 : 순차탐색, 이진탐색

최대 숫자 찾기처럼 머릿속에 찾고자 하는 수를 기억하고 차례대로 한 장씩 읽으며 카드를 찾는다.

만약, 오름차순(1,2,...10)으로 정렬된 카드들 중에 찾고자하는 수를 찾을때는 어떻게 하면 순차탐색보다 효율적으로 찾을까? 정렬되어있는 정보를 어떻게하면 활용할 수 있을까?

이진탐색 : 오름차순으로 정렬된 데이터를 반으로 나누고, 나누어진 반을 다시 반으로 나누고, 이 과정을 반복하여 원하는 데이터를 찾는 탐색 알고리즘을 이진탐색(Binary Search)이라고 한다. 

ex) 정렬된 임의의 수 10개 배열중 67을 찾아보자(그림, 숫자, 코드 순서대로 설명할게요.)

 

(1) 먼저 중앙데이터를 찾는다.

(2) 중앙데이터 23과 찾고자하는 수 67과 비교한다. 67이 23보다 크기때문에 우리가 찾는 데이터는 23을 기준으로 오른쪽에 있다는 사실을 알 수 있다. 그러므로 원래 데이터 집합에서 왼쪽은(회색부분) 탐색 대상에서 제외하고 오른쪽에서 다시 중앙데이터를 찾는다. 찾는 숫자 67이 중앙숫자 672보다 작으니 왼쪽에 위치함을 알 수 있다.  

(3) 다시 탐색 대상에서 제외된 요소들을 빼고 나면 67과 139 둘만 남는다. 여기에서 중앙 요소를 선택하면 139가 되고, 탐색 범위는 139의 왼쪽에 있는 67로 좁혀진다.

(4) 탐색완료

 

 

숫자로 생각해보자.

처음 탐색을 시도하면 탐색의 범위가 로 줄어든다. 다음 시도에서는 원래의 반의 반, 즉 원래 탐색 범위의

,로 줄어든다. 계속 줄어들어 탐색대상이 1이 되면 탐색을 종료한다. 데이터 집합의 크기 = n, 탐색 반복 횟수 = x 라 하면 1 = n * 가 된다.

 

즉, 반복횟수는  1000개의 데이터를 탐색할 때 10번이면 된다는 소리다!!

 

 

코드로 생각해보자.

(1) 반복문사용

#배열에서 특정 숫자 위치 찾기(이진 탐색) #입력 : 데이터 배열 arr, 찾는 값 target #출력 : 특정 숫자를 찾으면 그 값의 위치, 찾 지못하면 -1 #배열 arr에 left(처음)부터 right(끝)까지 탐색범위를 지정하여 #그 범위 안에서 target을 찾는 재귀함수 #종료조건 : 남은 탐색 범위가 비었으면 종료 def binary_search_sub(arr, target): left=0 #왼쪽은 배열의 첫번째 값 right=len(arr) -1 #맨 끝값 while left <= right: #탐색 범위의 크기가 0이 될때까지 루프를 반복 mid = (left+right) //2 #중간값 if target == arr[mid]: #발견! return mid elif target > arr[mid]: #중간값보다 찾는값이 더 크면 중간값보다 뒤에있는 배열값을 left에 넣음 left = mid+1 else: right = mid-1 #중간값보다 찾는값이 더 작으면 중간값보다 앞에있는 배열값을 right에 넣음 return -1 #못찾으을 때 arr = [1,7,11,12,14,23,67,139,672,871] print(binary_search_sub(arr, 67))

(2) 재귀함수 사용

#배열에서 특정 숫자 위치 찾기(이진 탐색의 재귀 호출) #입력 : 데이터 배열 arr, 찾는 값 target #출력 : 특정 숫자를 찾으면 그 값의 위치, 찾지못하면 -1 #배열 arr에 left(처음)부터 right(끝)까지 탐색범위를 지정하여 #그 범위 안에서 target을 찾는 재귀함수 #종료조건 : 남은 탐색 범위가 비었으면 종료 def binary_search_sub(arr, target, left, right): if left > right: return -1 mid = (left+right)//2 #탐색 범위의 중간 위치 if target == arr[mid]: #발견! return mid elif target > arr[mid]: #찾는 값이 더 크면 중간을 기준으로 오른쪽 값을 대상으로 재귀 호출 return binary_search_sub(arr, target, mid+1, right) else: #찾는 값이 더 작으면 중간을 기준으로 왼쪽 값을 대상으로 재귀 호출 return binary_search_sub(arr, target, left, mid-1) return -1 #찾지 못했을 때 #리스트 전체를 대상으로 재귀함수 호출 def binary_search(arr,target): return binary_search_sub(arr, target, 0, len(arr)-1) d = [1,7,11,12,14,23,67,139,672,871] print(binary_search(d, 67))

값: 6(목표 값의 자릿수 반환)

 

 

출처 : [알기쉬운 알고리즘-양성봉] 전공책입니다.  [모두의 알고리즘 파이썬]책을 참고하여 코드를 넣었습니다.