[Algorithm] 검색 - 완전 검색, 순차 검색, 이진 검색

검색/탐색 알고리즘 (Search Algorithm)

• 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업
• 탐색 키(Search Key) : 자료를 구별하여 인식할 수 있는 키

 

완전 검색(Exaustive Search)

• 문제의 해법으로 생각할 수 있는 모든 경우의 수를 나열해보고 확인하는 기법
• 수행 속도 느리지만 해답 찾아내지 못할 확률 작음
• 경우의 수가 상대적으로 작을 경우 유용
• 문제 풀 때 완전 검색으로 해답 도출 후, 성능 개선 위해 다른 알고리즘 사용하고 해답 확인하는 것이 바람직
• 완전 검색 종류
  1. Brute-force : for문 사용하여 처음부터 끝까지 탐색
     👉 Brute-force 적용해보기
  2. 비트 마스크 : 비트 연산 사용(&, |, ^, ~, <<, >>)
  3. 백트래킹 : 해를 찾아가는 도중 해가 될 가능성이 없는 경로라면 되돌아감
  4. 재귀함수 : 함수 내에서 함수 자기 자신을 계속해서 호출
  5. 순열 : 서로 다른 n개 중에서 r개를 뽑아서 한 줄로 나열
     • nPr = n * (n-1) * (n-2) * ... * (n-r+1) = n! / (n-r)!
  6. BFS(너비 우선 탐색)/ DFS(깊이 우선 탐색)

 

순차 검색 (Sequential Search)

• 일렬로 되어 있는 자료를 순서대로 검색하는 방법, 간단하고 직관적
• 배열이나 연결 리스트 등 순차구조로 구현된 자료구조에서 원하는 항목을 찾을 때 유용
• 검색 대상이 많을 때는 수행시간 급격히 증가

 

• 정렬되어 있지 않은 경우
  • 첫 번째 원소부터 순서대로 검색 대상과 키 값이 같은 원소가 있는지 비교하며 찾음
  • 키 값이 동일한 원소를 찾으면 그 원소의 인덱스 반환
  • 자료구조의 마지막에 이를 때까지 검색 대상을 찾지 못하면 검색 실패
  • 찾고자하는 원소의 순서에 따라 비교 횟수가 결정됨
    • 첫 번째 원소를 찾으면 1번 비교, 두 번째 원소를 찾으면 2번 비교 ...
    • 정렬되지 않은 자료에서의 순차 검색 평균 비교 횟수
    • = (1/n) * (1+2+3+...+n) = (n+1)/2
  • 시간 복잡도 : O(n)

  def sequentialSearch(a, n, key):
      i = 0 
      # i<n : 인덱스 검사 먼저! 유효한 인덱스에서만 while문 진행
      while i<n and a[i] != key:  
      	i += 1 
      if i<n: return i 
      else: return -1​

 

• 정렬되어 있는 경우
  • 자료가 오름차순 정렬된 상태에서 검색을 실시할 경우, 자료를 순차적으로 검색하며 키 값을 비교하여
    원소의 키 값이 검색 대상의 키 값보다 크면 찾는 원소가 없다는 것이므로 더 이상 검색하지 않고 검색 종료
  • 찾고자 하는 원소의 순서에 따라 비교 횟수가 결정됨
    • 정렬이 되어있으므로, 검색 실패를 반환하는 경우 평균 비교 횟수가 반으로 줄어듦
  • 시간 복잡도 : O(n)

  def sequentialSearch(a, n, key):
  	i = 0 
      i += 1 
      while i<n and a[i]<key: 
      	i += 1 
      if i<n and a[i] = key: return i 
      else: return -1​

 

이진 검색 (Binary Search)

• 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법
• 목적 키를 찾을 때까지 이진 검색 반복 수행함으로써 검색 범위를 반으로 줄여가며 보다 빠르게 검색을 수행
• 이진 검색을 하기 위해서는 자료가 정렬된 상태여야함
• 검색 과정
  1. 자료의 중앙에 있는 원소 고름
  2. 중앙 원소의 값과 찾고자 하는 목표 값 비교
  3. 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행, 
     크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행
  4. 찾고자 하는 값을 찾을 때까지 1-3 반복
• 구현
  • 검색 범위의 시작점과 종료점을 이용하여 검색을 반복 수행
  • 자료에 삽입이나 삭제가 발생했을 때, 배열의 상태를 항상 정렬 상태로 유지하는 추가 작업 필요

def binarySearch(a, key):
	start = 0 
    end = len(a) - 1 
    
    while start <= end: 
    	middle = (start + end) // 2 
        
        if a[middle] == key: # 검색 성공 
        	return True 
        elif a[middle] < key :
        	end = middle - 1 
        else: start = middle + 1 
        
    return False # 검색 실패

👉 이진 검색 적용해보기

• 재귀 함수 이용

def binarySearch2(a, low, high, key): 
	if low > high: # 검색 실패 
    	return False 
    else: 
    	middle = (low + high) // 2 
        
        if key == a[middle]: # 검색 성공 
        	return True 
        elif key < a[middle]:
        	return binarySearch(a, low, middle-1, key) 
        elif a[middle] < key: 
        	return binarySearch(a, middle+1, high, key)