게임알고리즘 8주차 - Search Algorithms, Interpolation Search, Tree

Search Algorithms

검색(Searching) 문제:

- n개의 키를 가진 배열 S와어떤 키 x가 주어졌을 때, x = S[i]가 되는 첨자 i를 찾는다.

- 만약 x가 배열 S에 없을 때는 오류로 처리한다.

 

탐색 알고리즘

저장된 데이터들 중 원하는 값을 찾는 알고리즘

 

탐색 알고리즘의 종류

- Sequential(Linear) Search Algorithm : Array or LInked List

- Binary Search Algorithm : Array

- Interpolation Search Algorithm : Array

 

순차탐색 (Sequential Search)

- 데이터 집합의 처음부터 끝까지 차례대로 모든 요소를 비교하여 데이터를 찾는 탐색 알고리즘

- Linear Search algorithm

- 정렬되어 있지 않은 데이터 집합에 적합함.

 

Sequential Search

문제 : 크기가 n인 배열 S에 x가 있는지 결정하라.

입력 : 정렬되어 있지 않은 배열 S[0..n-1], 찾고자 하는 항목 x

출력 : location (S에서 x가 있는 위치)

 

설계 전략

- 배열의 처음부터 마지막까지 차례대로 x와 비교한다.

- 배열 S의 데이터 중 X와 일치하면 해당 위치를 리턴한다.

// Using array
int SequentialSearch (int S[], int N, int target)
{
    for(int current = 0; current < N; current++)
    {
        if(S[current] == target)
        {
            return current;
    	}
    }
    return -1;
}

// Using linked list
Node * SequentialSearch (Node *head, int target) 
{
    Node * pCurrent = head;
    
    while(pCurrent != null)
    {
        if(pCurrent->data == target)
        {
	        return pCurrent;
        }
        else
        {
	        pCurrent = pCurrent->next;
        }
    }
    return null;
}

 

Sequential Search algorithm을 개선할 Idea

- 최근에 검색한 것을 다시 검색할 확률이 높다

- 이를테면 “워드에서 최근 문서 목록” 처럼…

- 따라서 검색 확률이 높은 것을 가능한 앞쪽에 위치하도록 한다.

 

Method #1 : 최근 검색한 데이터를 가장 앞쪽으로 이동 시킨다.(Move to Front)

int SS_MoveToFront (int S[], int N, int target)
{
    for(int current = 0; current < N; current++)
    {
        if(S[current] == target)
        {
            for(int i=current-1; i>=0; i--)
            {
                S[i+1] = S[i];
            }
            S[0] = target;
            return 0;
        }
    }
    return -1;
}

Method #2 : 최근 검색한 데이터를 한 칸 앞으로 이동 시킨다. (Transpose)

Node * SS_MoveToFront (Node *head, int target)
{
    Node * pCurrent = head;
    Node * prev = null;
    Node * pMatch = null;
    
    while(pCurrent != null)
    {
        if(pCurrent->data == target)
        {
            pMatch = pCurrent;
            
            if(prev != null) 
            { //not the first data
                prev->next = pCurrent->next;
                pCurrent->next = head;
                head = pCurrent;
            }
            break;
        }
        else 
        {
            prev = pCurrent;
            pCurrent = pCurrent->next;
        }
    }
    return pMatch;
}

Method #3 : 검색 빈도수에 따라 데이터를 재배치한다. (Frequency Count)

int SS_Transpose (int S[], int N, int target)
{
    for(int current = 0; current < N; current++)
    {
        if(S[current] == target)
        {
            if(current == 0)
            {
                return current;
            }
            S[current] = S[current-1];
            S[current-1] = target;
            
            return current-1;
        }
    }
    return -1;
}

Interpolation Search, 보간탐색

키 값을 기준으로 키가 있을만한 곳으로 탐색 범위를 제한하는 방법.

이진 탐색 알고리즘(Binary Search Algorithm)의 검색 하한을 개선하기 위한 방법이다.

인덱스와 추가적인 정보(키 값)를 이용한다.

키 값과 인덱스를 기준으로 비례식을 통해 다음 탐색 공간을 찾는다.

-> Linear Interpolation Seaerch (선형보간탐색)

 

Linear Interpolation Search, 선형보간탐색

탐색 위치

이진 탐색 : mid = (1 + 12) / 2 = 6

보간 탐색 : mid = 1 + (12 - 1)(150 - 20) / (170 - 20) = 10

template <class T>
void LinearInterpolation<T>::binarySearch(T S[], T x, int low, int high)
{
	int mid;

	if (low > high) 
	{
		return T();
	}
	else 
	{
		mid = (low + high) / 2;

		if (x == S[mid]) 
		{
			return mid;
		}
		else if (x < S[mid]) 
		{
			return binarySearch(S, x, low, mid - 1);
		}
		else 
		{
			return binarySearch(S, x, mid + 1, high);
		}
	}	
}

template <class T>
int LinearInterpolation<T>::linearInterpolation(T S[], T key, int n)
{
	int low = 0;
	int high = n - 1;
	int mid;

	while (low < high) 
	{
		int denominator = S[high] - S[low];
		if (denominator == 0)
		{
			mid = low;
		}
		else 
		{
			mid = low + (key - S[low]) * (high - low) / denominator;

			if (key == S[mid]) 
			{
				return mid;
			}
			if (key < S[mid]) 
			{
				high = mid - 1;
			}
			else
			{
				low = mid + 1;
			}
		}
	}

	return -1;
}

평균 시간복잡도

아이템이 균등하게 분포되어 있고, 검색 키가 각 슬롯에 있을 확률이 같은 경우

평균시간 복잡도 : A(n) ≈ lg(lg n)

 

최악의 경우

순차검색을 할 경우

Ex : 10개의 아이템이 1, 2, 3, 4, 5, 6, 7, 8, 9, 100일 때, Find 10

    - mid 값은 항상 low 값이 됨 (모든 아이템과 비교함)

 

Robust Linear Interpolation Search

1. gap의 초기값 = (high - low + 1 )^1/2

2. 초기 mid 값을 선형보간법으로 구한다.

3. 다음 식으로 새로운 mid값을 구한다.

    - mid = MIN(high - gap, MAX(mid, low + gap)

 

Tree

비선형 자료구조이다. 순환이 없다.

노드, 루트노드, 자식노드, 부모노드, 자매노드, 조상노드, 후손노드, 리프노드

이진트리, 포화 이진트리, 완전 이진트리

- 균형(balance) : 루트노드를 기준으로 왼쪽 서브트리와 오른쪽 서브트리 간의 높이 차이.

- 균형트리(height balanced tree) : 왼쪽, 오른쪽 서브트리 높이 차가 1이하인 트리.

- 완전균형트리(completely height-balanced tree) : 왼쪽, 오른쪽 서브트리 높이가 완전히 일치하는 트리.

 

Binary Tree의 활용

전위, 후위, 중위, BFS, DFS