탐색 알고리즘

• 컴퓨터 세계에서 탐색 : 데이터를 찾는다

순차탐색

• 처음부터 끝까지 모든요소를 검사하는 전략
• 정렬되지 않은 데이터set에서 원하는 항목을 찾을 수 있는 유일한 방법

자기구성법

• 자주 사용되는 항목을 데이터 앞쪽에 배치함으로써 순차 탐색의 검색 효율을 끌어올리는 방법 ex) Word 최근탐색문서

전진 이동법

• 탐색된 항목을 데이터set 가장 앞으로 옮김

VitaminQuiz 6-1

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int MoveToFront(int Dataset[], int length,int target);

int MoveToFront(int Dataset[], int length,int target)
{
	int index = 0;
	for (int i = 0; i < length; i++)
	{
		if (Dataset[i] == target)
		{
			index = 1;
			memmove(&Dataset[1], &Dataset[0], sizeof(Dataset[0]) * i);
			Dataset[0] = target;
		}
	}
	return index;
}

int main(void) {
	int arr[] = { 5,6,1,41,515,2 };
	int length = sizeof(arr) / sizeof(arr[0]);
	for (int i = 0; i < length; i++)
	{
		printf("%d ", arr[i]);
	}
	int TF = MoveToFront(arr, length, 6);

	printf("\n=================\n\n");
	for (int i = 0; i < length; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n=================\n\n");
	if (TF)
	{
		printf("Find!!!\n\n");
	}
	else
	{
		printf("Fail!!!\n\n");
	}
}

• output

5 6 1 41 515 2
=================

6 5 1 41 515 2
=================

Find!!!

---

전위법

• 탐색된 항목을 바로 이전 항목과 교환
• 자주 탐색된 항목을 조금씩 앞으로 옮김 → 자주 탐색되는 항목들이 앞으로 모임

VitaminQuiz 6-2

int TransPose(int Dataset[], int length, int target)
{
	int isFind = 0;
	for (int i = 0; i < length; i++)
	{
		if (Dataset[i]==target)
		{
			if (i > 0)
			{
				Swap(&Dataset[i - 1], &Dataset[i]);
			}
			isFind = 1;

		}
	}

	return isFind;
}

• output

5 6 1 41 515 2
=================

5 6 1 515 41 2
=================

Find!!!

계수법

• 탐색된 횟수를 별도의 공간에 저장해두고 탐색된 횟수가 높은 순으로 데이터 재구성
• 계수 결과를 저장하는 별도 공간 필요
• 계수 결과에 따라 데이터 재배치 해야함

VitaminQuiz 6-3

Node* SLL_FrequencyCount(Node** head, int target) // 계수법 LinkedList
{
	Node* Current = (*head);
	Node* Match = NULL;
	while (Current != NULL)
	{
		if (Current->data == target)
		{
			(Current->frequency)++;
			Match = Current;
			break;
		}
		else
		{
			Current = Current->nextNode;
		}
	}

	if (Match != NULL)
	{
		SLL_SortByFrequency(head); // 찾았다면 변경된 계수에 따라 데이터 재배치
		return Match;
	}


}

void SLL_SortByFrequency(Node** head) // 계수에 따라 데이터 재배치
{
	Node* Current = *head;
	Node* before = NULL;
	Node* bbfore = NULL;
	Node* after = NULL;
	int length = SLL_GetNodeCount(*head);

	for (int i = 0; i < length-1; i++)
	{
		for (int j = 0; j < length-i-1; j++)
		{
			if (SLL_GetNodeAt(*head,j)->frequency < SLL_GetNodeAt(*head,j+1)->frequency)
			{
				before = SLL_GetNodeAt(*head, j);
				after = SLL_GetNodeAt(*head, j+1);
			

				if (before == *head)
				{
					after->count = length;
					before->nextNode = after->nextNode;
					after->nextNode = before;
					*head = after;
				}
				else
				{
					bbfore = SLL_GetNodeAt(*head, j - 1);
					bbfore->nextNode = after;
					before->nextNode = after->nextNode;
					after->nextNode = before;

				}
			}
		}
	}

}

• Output

List[0] : -2
List[1] : -1
List[2] : 0
List[3] : 1
List[4] : 2
List[5] : 3
List[6] : 4

After FrequencyCount...


2x2 , 0x2 , 3x1

List[0] : 2
List[1] : 0
List[2] : 3
List[3] : -2
List[4] : -1
List[5] : 1
List[6] : 4

#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

#define BOUND 7; // 수의 범위

int FrequencyCount(int Dataset[],int Count[], int length, int target);

void _Swap(int* a, int* b)
{
	int temp = *a;
	*a = *b;
	*b = temp;
}

int main(void) {
	int arr[] = { 1,2,3,4,5,6,7 };
	int count[] = { 0,0,0,0,0,0,0 };
	int length = sizeof(arr) / sizeof(arr[0]);
	for (int i = 0; i < length; i++)
	{
		printf("%d ", arr[i]);
	}

	FrequencyCount(arr, count, length, 4);
	FrequencyCount(arr, count, length, 7);
	FrequencyCount(arr, count, length, 7);
	FrequencyCount(arr, count, length, 7);
	printf("\nAfter Count...\n\n");

	for (int i = 0; i < length; i++)
	{
		printf("%d ", arr[i]);
	}
}

int FrequencyCount(int Dataset[],int Count[], int length, int target) // 계수법 배열
{
	int isFind = 0;
	for (int i = 0; i < length; i++)
	{
		if (Dataset[i] == target)
		{
			Count[target - 1]++;
			isFind = 1;
			break;
		}
	}

	if (isFind)
	{
		for (int i = 0; i < length-1; i++)
		{
			for (int j = 0; j < length-1-i; j++)
			{
				if (Count[Dataset[j]-1] < Count[Dataset[j+1] - 1])
				{
					_Swap(&Dataset[j], &Dataset[j + 1]);
				}
			}
		}
	}

	return isFind;
}

• Output

1 2 3 4 5 6 7
After Count...

7 4 1 2 3 5 6

---

이진탐색

• 정렬된 데이터에서 탐색범위를 1/2 씩 줄여나가며 탐색

이진탐색 성능측정

• 데이터가 하나만 남았을때 탐색 종료
• 탐색을 한단계 수행할 때 마다 데이터의 크기는 절반으로 준다.
• 1 = n*(1/2)^X (N : 데이터 크기, X : 탐색반복횟수)

이진탐색트리

Red-Black Tree

연습문제

1. 순차 탐색 : 데이터가 정렬되어있지 않다.
2. 가능하지만 매우 비효율적이다. 중앙값을 바로 접근할 수 없기 때문에 n/2 만큼 진행해야한다.
3. 잎 노드까지 진행하는
   최소 경로 : all black
   최대경로 : red, black 번갈아 가며 진행

잎 노드까지 블랙노드 갯수는 동일 + 레드노드의 자식은 반드시 블랙
최대 경로는 최소경로의 2배 이하이므로
트리가 한쪽방향으로 기형적으로 자랄 수 없다.