[Algorithm] Search(탐색)

순차 탐색(sequential Search)

• 선형 탐색이라고도 불린다.
• 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다.
• 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다 .

적용

• 리스트가 아무리 많아도 시간만 충분하다면 항상 원하는 원소를 찾을 수 있다는 장점이 있다. 
• 순차 탐색은 이름처럼 순차로 데이터를 탐색한다는 의미이다.
• 정렬되지 않은 데이터나 작은 데이터 셋을 탐색해야 할 때 간단히 구현 가능하다.
• 시간복잡도는 O(n)이다.

ex) 순차탐색으로 이름 리스트에서 원하는 이름의 순서 찾기

#sequential_search
def sequential_search(n,target,array) :
  for i in range(n) :
    if array[i] == target :
      return i + 1
name_data = input().split()
n = int(name_data[0])
target = name_data[1]

name_arr = list(input().split())

print(sequential_search(n,target,name_arr))

이진 탐색(Binary Search)

• 데이터가 무작위일 떄는 사용할 수 없지만 , 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있다는 특징이 있다.
• 이진 탐색은 탐색 범위를 절반 씩 좁혀가며 데이터를 탐색하는 특징이 있다. 
• 이진 탐색은 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 게 이진 탐색 과정이다. 

적용

• 이진 탐색은 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘이다.
• 데이터가 정렬되어 있지 않을 때는 정렬과 탐색의 복잡도를 고려하여 선택한다. (sort and search)
• 시간 복잡도는 O(logN)

a = [2,3,6,6,8,12]

left = 0
right = len(a) - 1
mid = (left + right) // 2
while left <= right :
  if a[mid] == 3 :
    print(f'a[{mid}] = 3')
    break
  elif a[mid] > 3 :
    right = mid - 1
  else :
    left = mid + 1

  mid = (left + right) // 2

Binary Search Algorithm

1. 탐색 범위의 왼쪽 포인트, 오른쪽 포인트, 가운데 포인트에 해당되는 변수들을 만들어주고 이 값을 바꿔가는 것으로 탐색 범위가 변경되는 걸 반영한다.
2. 이분탐색을 처음 시작할 때는 전 범위를 탐색하므로 left는 리스트의 시작 index(0)를 , right는 리스트의 마지막 index(len(arr)-1)로 지정했다. (mid는 정 가운데 : (start + end) // 2)
3. 가운데 값이 목표 값보다 크다면 그 오른쪽에 있는 값들은 목표 값보다 더 큰 값들이므로 더 살펴볼 필요가 없다. 목표 값은 반드시 왼쪽 범위에 있으므로 right를 mid-1로 옮긴다.
4. 가운데 값이 목표 값보다 작다면 그 왼쪽에 있는 값들은 목표 값보다 더 작을 테니 살펴볼 필요가 없다. 목표 값은 반드시 오른쪽 범위에 있으므로 left를 mid+1로 옮긴다.

#binary_search
def binary_search(array,target,start,end) : 			# 리스트,찾을 값, 시작인덱스, 종료인덱스 변수를 입력
  if start > end :									# 시작점이 끝점보다 크면 None
    return None 
  mid = (start + end) // 2							# 중간 인덱스 반환
  if array[mid] == target :															
    return mid				
  elif array[mid] > target :							# 중간보다 크다면
    return binary_search(array,target,start,mid-1)
  else :												# 중간보다 작다면
    return binary_search(array,target,mid+1,end)

n,target = list(map(int,input().split()))

array = list(map(int,input().split()))
array.sort()

result = binary_search(array,target,0,n-1)
if result == None :
  print("원소가 존재하지 않습니다")
else :
  print(result + 1)

※ bisect

from bisect import bisect_left,bisect_right

a = [2,3,6,6,6,10,12,15]

l = bisect_left(a,6)    # bisect_left(리스트 , 찾을 원소)
r = bisect_right(a,6)   # bisect_right(리스트 , 찾을 원소)

print(r-l)               # 배열에 목표 값(6)이 몇 개 있는지 확인

• 파이썬에서 bisect 모듈을 import 하면 이분 탐색을 더 효율적이게 할 수 있다.
• bisect_left(sorted_arr,value) : 왼쪽 인덱스 구하기 
• bisect_right(sorted_arr,value) : 오른쪽 인덱스 구하기 
• bisect_right(sorted_arr,value) - bisect_left(sorted_arr,value)  → 리스트 안에 해당 원소의 갯수를 알 수 있다.

※ 이진 탐색 트리(Binary Search Tree)

이진 탐색 트리란 이진 탐색이 동작 할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조이다. 이진 탐색은 다음과 같은 특징을 가진다.

- 부모 노드보다 왼쪽 자식 노드가 작다
- 부모 노드보다 오른쪽 자식 노드가 크다

왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

 

 

매개변수 탐색(Parametric Search)

매개변수 탐색은 최적화 문제를 결정 문제로 바꿔 푸는 탐색 알고리즘이다. 최적화 문제는 문제 상황을 만족하는 변수의 최솟값, 최댓값을 구하는 문제를 의미하며, 결정 문제는 Yes,No 중 하나로 답할 수 있는 문제이다.  

ex) baekjoon-2805

https://www.acmicpc.net/problem/2805

2805번: 나무 자르기

위 문제는 단순히 반복문으로 하면 시간초과가 난다. 이 문제는 이분탐색 변형인 매개변수 탐색으로 풀어야 하는 문제이다.

 

1. 리스트에서 중간값을 결정해주기 위한 start 값과 end 값을 결정 , 보통 start는 0이나 1 , end 값은 리스트에서 가장 큰  값(max(arr))으로 초기화
2. while 조건은 투 포인터와 비슷하게 start <= end로 설정, while 문 안에서 mid = (start + end) // 2 계속 초기화

 

나무 자르기 문제 같은 파라매트릭 서치를 이용해야 할 때는 이렇게 접근 해야 한다.

n,m = map(int,input().split())
height = list(map(int,input().split()))

left, right = 0,max(height)			# 파라매트릭 서치를 위한 left, right
mid = (left+right) // 2				

def get_total_tree(t) :				# 자르고 가져갈 나무의 길이를 구하는 함수
  result = 0
  for h in height :
    if h > t :
      result += h - t 
  return result

result = 0

while left <= right :				# 파라매트릭 서치 종료 조건
  if get_total_tree(mid) >= m :		# 자르고 가져갈 나무의 길이가 m보다 크거나 같으면
    result = mid					# result를 mid로 초기화하고
    left = mid + 1					# left를 mid + 1로 초기화(더 큰 mid 값을 찾기 위해)

  else :
    right = mid - 1
  mid = (left+right) // 2			# mid 값은 계속 while 문 안에서 초기화한다.

print(result)