IM

작지만 단단하게

탐색 개요

  • 여러 개의 원소로 구성된 데이터에서 원하는 값을 가진 원소를 찾는 것
  • 데이터의 형태 - 리스트, 트리, 그래프 등
  • 내부 탐색 vs 외부 탐색

  • 관련 연산 -> 탐색 + (초기화, 삽입, 삭제)

  • 탐색 방법
    • 리스트 형태 : 순차 탐색, 이진 탐색
    • 트리 형태 : 이진 탐색 트리, 2-3-4 트리, 레드-블랙 트리, B-트리
    • 해시 테이블 : 해시 함수, 충돌 해결 방법

순차탐색

  • 리스트 형태로 주어진 원소들을 처음부터 하나씩 차례로 (“순차”) 비교하면서 원하는 값을 가진 원소를 찾는 방법

탐색 연산

SequentialSearch(A[], n, x){
	i=0;
	while(i<n && A[i]!=x) i = i+1;
	return(i)
}

삽입 연산

SequentialSearch_Insert(A[], n, x){
	A[n] = x; 
	return(A, n+1);
}

삭제 연산

SequentialSearch_Delete(A[], n, x){
	Index = SequentialSearch(A, n, x);
	if(Index == -1) return(A, n);
	A[Index] = A[n-1];
	return(A, n-1);
}

성능 및 특징

  • 탐색 성공 시
    • 1번~n번 비교
    • 평균 (n+1)/2회
  • 탐색 실패 시
    • 항상 n번 비교
    • O(n)

  • 삭제
    • 삭제할 원소의 순차 탐색 O(n) 후, 마지막 원소의 이동
    • O(1)

  • 삽입 연산의 시간 복잡도
    • 리스트의 마지막에 추가하는데 상수 시간만 필요
    • O(1)

  • 정렬되지 않고 크기가 작은 데이터에 적합
  • 모든 리스트 형태의 입력에 적용 가능
    • 비정렬 데이터 탐색에 적합
  • 탐색과 삭제에 O(n) 시간이 필요
    • 데이터가 큰 경우에는 부적합

이진 탐색

이진탐색 개요

  • 정렬된 리스트 형태로 주어진 원소들을 절반씩 줄여 가면서 원하는 값을 가진 원소를 찾는 방법
  • 분할정복 방법이 적용됨

  • 위에서 작성한 ‘리스트’는 오직 배열만 가능

  • 탐색 방법
    1. 배열의 가운데 원소 A[min]를 탐색 키 key를 비교
    2. A[mid] = key : 탐색 성공
    3. key < A[mid] : 이진탐색(원래 크기의 1/2인 왼쪽 부분배열) 순환 호출
    4. A[mid] < key : 이진탐색(원래 크기의 1/2인 오른쪽 부분배열) 순환 호출

  • 탐색을 반복 할 때마다 대상 원소의 개수가 절반으로 감소

탐색 연산

BinarySearch(A[], key, Left, Right){
	if(Left>Right) return(-1);
	mid = (Left+Right)/2;
	if(A[mid] == key) return(mid);
	else if(key<A[mid]) BinarySearch(A, key, Left, mid-1)
	else BinarySearch(A, key, mid+1, Right)
}
  • T(n) = O(logn)

초기화 연산 (정렬이 되어있지 않을 때)

BinarySearch_Initialize(A[], n){ // O(n)
	for(i=0; i<n-1; i++){
		if(A[i]>A[i+1]){
			A=Sort(A,n); // 오름차순으로 정렬되는 메서드라고 가정. O(nlogn)
			break;
		}
	}
	return(A)
}
  • T(n) = O(nlogn)

삽입 연산

BinarySearch_Insert(A[], n, x){
	left = 0; right = n-1;
	while(left <= right) {
		mid = ((right-left+1)/2)+left;
		if(x==A[mid]) return(A,n); // 삽입할 원소가 이미 존재
		else if(x<A[mid]) right = mid-1; // 왼쪽 부분배열 탐색
		else left = mid+1; // 오른쪽 부분배열 탐색
	}
	for(i=n;i>left;i--) A[i]=A[i-1]; //A[left]부터 오른쪽으로 한 칸씩 이동
	A[Left] = x; // 원소 삽입
	return (A,n+1);
}
  • T(n) = O(n)

삭제 연산

BinarySearch_Delete(A[], n, x){
	index = BinarySearch(A[], x, 0, n-1);
	if(index==-1) return (A,n); // 삭제할 원소가 존재하지 않음
	for(i==index; i<n-1; i++) { // 삭제할 위치의 오른쪽 모든 원소를
		A[i] = A[i+1]; // 왼쪽으로 한칸씩 이동(원소 삭제)
	}
	return (A,n-1); 
}
  • T(n) = O(n)

성능과 특징

  • 연결리스트 에서 삽입과 삭제가 용이하다고 생각할 수 있지만 구조상 이진 탐색 자체가 불가능
    • 직접적으로 중앙값을 찾는 단계 자체가 안됨

  • 정렬된 리스트에 대해서만 적용 가능
  • 삽입과 삭제가 빈번한 경우에는 부적합
    • 연산 후 리스트의 정렬 상태를 유지하기 위해 O(n)의 데이터 이동이 필요
    • 데이터가 작은 경우에 적합

  • 탐색 연산 : O(logn)
  • 초기화 연산 : O(nlogn)
  • 삽입 연산 : O(n)
  • 삭제 연산 : O(n)

Updated: