Basic Search Alogrithm

Search Alogrithm

방대한 데이터에서 목적에 맞는 데이터를 찾아내기 위한 알고리즘

Sequential Search

int SequentialSearch(int arr[], int size, int findVal)
{
	int index = 0;
	for (int i = 0; i < size; i++)
	{
		if (arr[i] == findVal)
		//{ 전진 이동법
		//	for (int j = i - 1; j >= 0; j--)
		//		arr[j + 1] = arr[j];
		//}
		//arr[0] = findVal;
		return findVal;
	}
	return 0;
}

배열 또는 리스트에서 특정한 값을 찾는 알고리즘

• 자주 탐색하는 데이터를 배열의 앞쪽에 배치하여 순차탐색의 계산량을 줄이는 방법
• O(n)
  
  
• 자기 구성 순차탐색
  같은 데이터를 여러번 찾는 경우 효율이 떨어지기 때문에
  탐색 빈도가 높은 데이터를 배열의 앞쪽에 배치하여 순차 탐색의 연산량을 줄이는 방법을 사용한다.
  • 전진 이동법 : 탐색된 데이터를 가장 앞쪽에 배치
  • 전위법 : 해당 데이터가 탐색될 때 마다 한 칸씩 앞으로 이동

Binary Search

void BinarySearch(int arr[], int num, int left, int right)
{
	while (left <= right)
	{
		int middle = (left + right) / 2;
		if (num = arr[middle])
			return;
        //
		if (num < arr[middle])
			right = middle - 1;
		else
			left = middle + 1;
	}
}

이미 정렬된 상태의 배열에서 특정한 값을 빠르게 찾는 알고리즘

• 배열의 중간 인덱스에 해당하는 요소와 비교하여 배열의 크기를 절반씩 줄여나가는 형태
• O(log n)

Tree traversal

트리 구조 내의 모든 노드를 특정한 순서로 방문하는 알고리즘

• 전위 순회
• 후위 순회
• 후위 순회
  트리 탐색 참조

Graph Search

• DFS : 깊이 우선 탐색

  깊이를 우선 기준으로 하여 방문하는 알고리즘

  • 정점을 방문한 뒤, 더이상 연결된 정점이 없을 때까지 인접한 정점을 재귀적으로 방문
  • O(n)

• BFS : 너비 우선 탐색

  현재 정점과 인접한 정점부터 우선으로 방문하는 알고리즘

  • 정점을 방문한 뒤, 연결된 정점을 큐에 넣은 다음 큐에서 하나씩 인출하여 방문
  • O(n)

Hashing

임의의 길이의 데이터를 고정된 길이의 데이터로 매핑함으로써 데이터를 빠르게 탐색

• 해시code
  임의의 길이의 데이터를 해시 함수를 통해 변환한 고정 길이의 데이터
• 해시 테이블
  해시 코드와 그에 해당하는 데이터를 연관 컨테이너 형태로 저장하는 자료구조
  • 버킷
    하나의 해시 코드를 저장하는 메모리 공간
  • 슬롯
    하나의 레코드가 저장되는 공간으로 하나의 버킷에 여러 슬롯이 존재할 수 있다.
  • 오버플로
    계산된 해시 코드에 해당하는 버킷 내에 저장할 메모리 공간이 없는 상태
• 해시 함수
  임의의 길이의 데이터를 고정 길이의 해시 코드로 매핑하는 함수
  해시 함수의 성능에 따라 해싱 알고리즘의 효율성이 결정됨
• 해시 충돌
  서로 다른 두 데이터가 동일한 해시 코드로 매밍되는 경우
  • 개방 주소법
    해시 테이블의 다른 버킷에 데이터를 저장해시 주소 변경
    • 선형탐사
      충돌이 일어난 버킷의 다음 버킷에 저장
    • 2차 검색
      충돌이 일어난 버킷으로 부터 정해진 값만큼 건너 뛴 버킷에 저장
    • 이중 해싱
      충돌이 일어났을 때 다른 해시 함수를 이용해 추가 변환
    • 재해싱
      테이블의 리사이징과 함께 새 해시 함수로 새 테이블 생성
  • 폐쇄 주소법체이닝
    충돌 버킷에 연결 리스트를 할당하여 연결 해시 주소 유지