[알고리즘] 8장. Searching

해당 게시물은 한치근 교수님의 '알고리즘' 강의를 수강하며
학습한 내용을 개인적으로 정리한 글입니다.

---

📌 8-1

* 키의 비교만으로 검색하는 경우 하한

* 검색(Searching) 문제
- n개의 키를 가진 배열 S와 어떤 키 x가 주어졌을 때, x = S[i]가 되는 첨자 i를 찾는다.
- 만약 x가 배열 S에 없을 때는 오류로 처리한다.

* 이분(이진) 검색 알고리즘
- 배열이 정렬이 되어 있는 경우 시간복잡도가 W(n) = lgn + 1이 되어서, 매우 효율적인 알고리즘이라고 할 수 있다.
- 키의 비교만으로 검색을 수행하는 경우에는 이분 검색 알고리즘 보다 더 좋은 알고리즘은 존재할 수 없다.

* 검색의 결정트리(decision tree)
- 큰 마디(내부마디) : 키와 각 아이템을 비교하는 마디
- 작은 마디(잎마디) : 검색 결과
- 뿌리마디에서 잎마디까지의 경로는 검색하면서 비교하는 과정을 보여준다.

* 결정트리는 x를 찾기 위해서 n개의 키를 검색하기에 유효하다.(valid)

* 최악의 경우 하한 찾기
- 깊이(depth) + 1
- lgn + 1
- Binary search is optimal

* 평균의 경우 하한 찾기
- lgn - 1

---

📌 8-2

* <A> 이진검색 (Binary Search)

void binsearch(int n, const keytype S[], teytype x, index& location) {
	index low, high, mid;
	low = 1; high = n; location = 0;
	while (low <= high && location == 0) {
		mid = (low + high) / 2;
		if (x == S[mid])
			location = mid;
		else if (x < S[mid])
			high = mid - 1;
		else
			low = mid + 1;
	}
}

* <A> 보간검색 (Interpolation Search)
- 검색의 하한을 개선할 수 있는가?
- 비교하는 이외에, 다른 추가적인 정보를 이용하여 검색할 수 있다면 가능하다.
- 선형 보간법(linear interpolation)

void interpsrch(int n, const number S[], number x, index& i) {
	index low, high, mid;
	number denominatior;
	low = 1; high = n; i = 0;
	if (S[low] <= x <= S[high])
		while (low <= high && i == 0) {
			denominator = S[high] - S[low];
			if (denominator == 0)
				mid = low;
			else
				mid = low + ((x - S[low])*(high - low))/denominator;
			if (x == S[mid])
				i = mid;
			else if (x < S[mid])
				high = mid - 1;
			else
				low = mid + 1;
		}
}

* 보강된 보간검색 (Robust Interpolation Search)
- gap 변수 사용
- 분석 : 아이템이 균등하게 분포되어 있고, 검색 키가 각 슬롯에 있을 확률이 같다고 가정하면, 보강된 보간검색의 평균 시간복잡도는 A(n) => Θ(lg(lgn))이 되고, 최악의 경우는 W(n) => Θ((lgn)^2)

* 트리 구조를 사용한 동적검색
- 정적검색(static searching) : 데이터가 한꺼번에 저장되어 추후에 추가나 삭제가 이루어지지 않는 경우에 이루어 지는 검색
- 동적검색(dynamic searching) : 데이터가 수시로 추가 삭제되는 유동적인 경우, 예로서 비행기 예약 시스템

* 이진검색트리 (Binary Search Tree)
- 각 마디 마다 하나의 키가 할당되어 있다.
- 어떤 마디 n의 왼쪽부분트리(left subtree)에 속한 모든 마디의 키는 그 마디 n의 키 보다 작거나 같다.
- 어떤 마디 n의 오른쪽부분트리(right subtree)에 속한 모든 마디 n의 키 보다 크거나 같다.
- 시간 복잡도 : A(n) = 1.38lgn

---

📌 8-3

* 검색시간 향상을 위한 트리구조: 균형트리
- AVL 트리 : 아이템의 추가, 삭제, 검색 모두 Θ(lgn)
- B-트리 / 2-3 트리 : 잎마디들의 깊이(수준)를 항상 같기 유지. 아이템의 추가, 삭제, 검색 모두 Θ(lgn)
- red-black tree : 아이템의 추가, 삭제, 검색 모두 Θ(lgn)

* AVL 트리

- 좌, 우 subtree의 높이의 차가 최대 1인 이진검색트리

* B-tree 중 가장 간단한 형태인 2-3 트리

- 각 마디에는 키가 하나 또는 둘 존재. 각 내부마디의 자식 수는 키의 수 + 1. 어떤 주어진 마디의 왼쪽(오른쪽) 부분트리의 모든 키들은 그 마디에 저장되어 있는 마디보다 작거나(크거나) 같다. 모든 잎마디는 수준이 같다. 데이터는 트리 내의 모든 노드에 저장한다.

---

📌 8-4

* 해싱(Hashing)
- 2개 이상의 키가 같은 해시값을 갖는 경우 충돌(collision)이 발생한다.

 

* 충돌 해결법
- open hashing(= closed addressing): chaining, separate chaining
- closed hashing(= open addressing): linear probing, quadratic probing, double hashing

* Open Hashing
- 정리 : n개의 키가 m개의 바구니에 균일하게 분포되어 있다면, 검색에 실패한 경우 비교 횟수는 n/m이다.
- 정리 2 : n개의 키가 m개의 바구니에 균일하게 분포되어 있고, 각 키가 검색하게 될 확률이 모두 같다면, 검색에 성공한 경우 비교 횟수는 n/2m + 1/2이다.

* Closed Hashing (Open addressing)
- k = key, m = hash table 크기

* 단순한 형태의 해시함수
- h(k) = k mod m. (m slots)
- m = 2^p or 10^p는 사용 안한다. -> k의 끝 p자리를 나타낸다.

---

📌 8-5

* 선택문제(selection problem)
- 키가 n개인 리스트에서 k번째로 큰(또는 작은) 키를 찾는 문제
- 키가 정렬되어 있지 않다고 가정

* <A> 최대(max)키 찾기

- 시간복잡도 : T(n) = n-1

void find_largest(int n, const keytype S[], keytype& large) {
	index i;
	large = S[1];
	for (i = 2; i <= n; i++)
		if (S[i] > large)
			large = S[i];
}

* <A> 최소키와 최대키 찾기

- 시간복잡도 : W(n) = 2(n-1)

void find_both(int n, const keytype S[], keytype& small, keytype& large) {
	index i;
	small = S[1];
	large = S[1];
	for (i = 2; i <= n; i++)
		if (S[i] < small)
			small = S[i];
		else if (S[i] > large)
			large = S[i];
}

* <A> 키를 짝지어 최소키와 최대키 찾기

- 시간복잡도 : T(n) => ((n-2)/2)x3

void find_both2t(int n, const keytype S[], keytype& small, keytype& large) {
	index i;
	if (S[1] < S[2]) {
		small = S[1];
		large = S[2];
	}
	else {
		small = S[2];
		large = S[1];
	}
	for (i = 3; i <= n-1; i += 2) {
		if (S[i] < S[i+1]) {
			if (S[i] < small)
				small = S[i];
			if (S[i+1] > large)
				large = S[i+1];
		}
		else {
			if (S[i+1] < small)
				small = S[i+1];
			if (S[i] > large)
				large = S[i];
		}
	}
}

* 차대키 (second largest key) 찾기
- 단순한 방법: 먼저 최대키를 찾고(n-1회 비교), 이후 다음 최대키를 찾음(n-2회 비교). 총 2n-3회 비교.
- Tournament Method:
1. 토너먼트를 시행하여 최대 우승자가 최대키다.
2. 각 시합의 진 팀을 이긴 팀의 리스트로 만든다.
3. 우승팀의 리스트에서 최대값을 찾으면 이것이 차대키다.
- 총 n+lgn-2회 비교.

* <A> k번째 작은 키 찾기 (selection)
- 단순한 방법: 정렬 후 k번째 선택. nlgn
- partition 사용: selection(1,n,k)
quick sort의 partition을 사용
W(n) = n(n-1)/2. A(n) => 3n
- O(n) 방법 SELECT(k, Sn)
1. 데이터를 5개의 묶음으로 만듦
2. 5개의 묶음 내에서 정렬
3. 5개의 묶음의 가운데 값들을 모아 M 생성
4. M에서 M/2번째(가운데)를 찾음
5. m보다 작은 데이터 S1, 같은 데이터 S2, 큰 데이터 S3를 생성
6. if S1 >= k, then return SELECT(k, S1)
   else if S1+S2 >= k, then return m
   else return SELECT(k-S1-S2, S3)
7. 작아진 문제에 대해 SELECT 수행
- T(n) <= T(n/5) + T(3n/4) + cn = 20cn => O(n)

- 시간복잡도 :
W(n) = W(n-1) + n-1
B(n) = B(n/2) + n-1
A(n) => 3n

keytype selection(index low, index high, index k) {
	index pivotpoint;
	if (low == high)
		return S[low];
	else {
		partition(low, high, pivotpoint);
		if (k == pivotpoint)
			return S[pivotpoint];
		else if (k < pivotpoint)
			return selection(low, pivotpoint-1, k);
		else
			return selection(pivotpoint+1, high, k);
	}
}

void partition(index low, index high, index& pivotpoint) {
	index i, j;
	keytype pivotitem;
	pivotitem = S[low];
	j = low;	
	for (i = low+1; i <= high; i++)
		if (S[i] < pivotitem) {
			j++;
			exchange S[i] and S[j];
		}
	pivotpoint = j;
	exchange S[low] and S[pivotpoint];
}

* selection vs select
- selection : 단순 partition을 사용한 경우
임의의 pivot item 선정
- select : median of median 방법
한 쪽의 데이터 개수를 3/4 n으로 한정

---

📌 8-6

* 문자열 매칭
- 입력 문자열에서 패턴을 찾는 문제

* <A> 원시적인 매칭 방법

naiveMatching(A, p) {
	for i = 1 to n-m+1
		if (p[1..m] == A[i..i+m-1])
			matching is found at A[i]
}

* <A> 오토마타를 이용한 방법

FiniteAutomataMatcher(A, δ, f) {
	q = 0;
	for i=1 to n
		q = δ(q, A[i]);
		if (q = f)
			matching is found at A[i-m+1]
}

* <A> Rabin-Karp 알고리즘

basicRabinKarp {
	v = 0; a1 = 0;
	for i = 1 to m
		v = dv + p[i];
		a1 = da1 + A[i];
	for i = 1 to n-m+1
		if (i != 1) ai = d(ai-1 - (d^m-1)A[i-1]) + A[i+m-1];
		if (v = ai) matching is found at i
}

RabinKarp {
	v = 0; b1 = 0;
	for i = 1 to m
		v = (dv + p[i]) mod q;
		b1 = (db1 + A[i]) mod q;
	h = (d^m-1) mod q
	for i = 1 to n-m+1
		if (i != 1) bi = (d(bi-1 - (d^m-1)A[i-1]) + A[i+m-1]) mod q;
		if (v == bi)
			if (p[1..m] == A[i..i+m-1]) matching is found at i
}

* <A> Boyer-Moore 알고리즘

BoyerMooreHorspool(A, p) {
	computeJump(p, jump);
	i = 1;
	while (i <= n-m+1) {
		j = m;
		k = i + m - 1;
		while (j > 0 and p[j] == A[k]) {{
			j--;
			k--;
		}
		if (j == 0)
			a matching is found at A[i];
		i = i + jump[A[i+m-1]];
	}
}​

---