[알고리즘] 사전 ADT

사전 구현에 따른 탐색 기법

무순 사전

• 사전 항목들을 임의의 순서로 리스트에 저장

• insertItem() : 맨 앞 또는 맨 뒤에 삽입 => O(1)

• findElement() or removeElement() : 최악의 경우(항목이 존재 안하는 경우) 리스트 전체 순회 => O(n)

• 사용 ) 소규모의 사전 , 삽입은 빈번하지만 탐색이나 삭제는 드문 사전 (ex : 서버의 로그인 기록)

• 선형 탐색 사용 (단순히 리스트 전체를 순회하며 원소를 찾음) => O(n)

순서 사전

• 사전 항목들을 정렬된 순서로 저장

• findElement() : 이진 탐색 이용 => O(log n) 시간 소요

• insertItem() : 공간 확보를 위해 최악의 경우 n개의 항목 이동이 필요 => O(n)

• removeElement() : 항목이 삭제된 공간을 기존 항목들로 메꾸기 위해 최악의 경우 => O(n)

• 사용 ) 소규모 사전, 탐색은 빈번하지만 삽입이나 삭제는 드문 사전 (ex : 전화번호부, 신용카드 사용승인)

• 이진 탐색 사용

이진 탐색

• 키로 정렬된 배열에 기초한 리스트로 구현된 사전에 대해 findElement 수행
• 재귀가 발생할 때마다 탐색해야할 원소의 수가 반감 => 최대 log(n)회 실행 됨

// 중복된 숫자가 없는 정렬된 배열에서의 탐색

// x = k 인 숫자 index 찾기
int rFE(int * arr, int k, int l, int r) {
	int mid = (l + r) / 2;

	if (l > r) return -1;

	if (k == arr[mid]) return mid;
	else if (k < arr[mid]) rFE(arr, k, l, mid - 1);
	else rFE(arr, k, mid + 1, r);
}

// x <= k 만족하는 숫자 index찾기
int rFE(int* arr, int k, int l, int r) {
	int mid = (l + r) / 2;

	if (l > r) return -1;

	if (k == arr[mid]) return mid;
	//왼쪽 보ㅓ기
	else if (k < arr[mid]) return rFE(arr, k, l, mid - 1);
	//오른쪽 보기
	else
	{
	    if (mid == r) return mid;
		if (arr[mid + 1] > k) return mid;
		else return rFE(arr, k, mid + 1, r);
	}
}
int findElement(int* arr, int n, int k) {
	return rFE(arr, k, 0, n - 1);
}

// + 비재귀 x>=k 만족하는 숫자 index 찾기 
int findElement(int* arr, int n, int k) {

	int l = 0, r = n - 1;
	int mid;

	while (l <= r) {
		mid = (l + r) / 2;
		if (arr[mid] == k) return mid;
		else if (k < arr[mid]) {
			if (mid == l) return mid;
			if (arr[mid - 1] < k) return mid;
			r = mid - 1;
		}
		else {
			l = mid + 1;
		}
	}
	return n;
}