검색

---

• 저장되어 있는 자료 중에서 원하는 항목을 찾는 작업

• 목적하는 탐색 키를 가진 항목을 찾는 것
  - 탐색 키 : 자료를 구별하여 인식할 수 있는 키

• 검색의 종류

  • 순차 검색(sequential search)
  • 이진 검색(binary, search)
  • 해쉬(hash)

• 일렬로 되어 있는 자료를 순서대로 검색하는 방법

  • 가장 간단하고 직관적인 검색 방법
  • 배열이나 연결 리스트 등 순차구조로 구현된 자료구조에서 원하는 항목을 찾을 때 유용함.
  • 알고리즘이 단순하여 구현이 쉽지만, 검색 대상의 수가 많은 경우에는 수행시간이 급격해 증가하여 비효율적임

• 2가지 경우

  • 정렬되어 있지 않은 경우
  • 정렬되어 있는 경우

• 검색과정

  • 첫 번째 원소부터 순서대로 검색 대상과 키 값이 같은 원소가 있는지 비교하며 찾는다.
  • 키 값이 동일한 원소를 찾으면 그 원소의 인덱스를 반환한다.
  • 자료구조의 마지막에 이를 때까지 검색대상을 찾지 못하면 검색 실패

정렬되어 있지 않은 경우

• 찾고자 하는 원소의 순서에 따라 비교회수가 결정됨
  • 첫 번째 원소를 찾을 때는 1번 비교, 두 번째 원소를 찾을 때는 2번 비교
  • 정렬되지 않는 자료에서의 순차검색의 평균 비교 회수
  • 시간 복잡도 : O(n) , (n+1)/2
• Ex)

def sequential_seracth(a, n, key):
	i = 0
    while i <n and a[i] != key:
    	i = i + 1
    if i < n : return i
    else : return -1

정렬되어 있는 경우

• 검색과정
  • 자료가 오름차순으로 정렬된 상태에서 검색을 실시한다고 가정
  • 자료를 순차적으로 검색하면서 키 값을 비교하여, 원소의 키 값이 검색 대상의 키 값보다 크면 찾는 원소가 없다는 것이므로 더 이상 검색하지 않고 검색을 종료한다.
• 찾고자 하는 원소의 순서에 따라 비교회수가 결정됨
  • 정렬이 되어있으므로, 검색 실패를 반환하는 경우 평균 비교 회수가 반으로 줄어든다.
  • 시간 복잡도 : O(n)
• Ex)

def seqentialSerach(a, n, key):
	i = 0
    while i < n and a[i] < key:
    	i = i+1
    if i<n and a[i] == key:
    	return i
    else:
    	return -1

이진 검색

• 자료의 가운데에 있는 항목의 키 값과 비교하여 다음 검색의 위치를 결정하고 검색을 계속 진행하는 방법

  • 목적 키를 찾을 때 까지 이진 검색을 순환적으로 반복 수행함으로써 검색 범위를 반으로 줄여가면서 보다 빠르게 검색을 수행함

• 이진 검색을 하기 위해서는 자료가 정렬된 상태여야 한다.

• 검색과정

  • 자료의 중앙에 있는 원소를 고른다.
  • 중앙 원소의 값과 찾고자 하는 목표 값을 비교한다.
  • 목표 값이 중앙 원소의 값보다 작으면 자료의 왼쪽 반에 대해서 새로 검색을 수행하고, 크다면 자료의 오른쪽 반에 대해서 새로 검색을 수행한다.
  • 찾고자 하는 값을 찾을 때까지 위의 과정을 반복한다.

• 구현

  • 검색 범위의 시작점과 종료점을 이용하여 검색을 반복 수행한다.
  • 이진 검색의 경우, 자료에 삽입이나 삭제가 발생했을 때 배열의 상태를 항상 정렬 상태로 유지하는 추가 작업이 필요하다.

• Ex)

def binarySerach(a, N, key):
	start = 0
    end = N - 1
    while start <= end:
    	middle = (start + end) // 2
        if a[middle] == key: # 검색 성공
        	return True
        elif a[middle] > key:
        	end = middle - 1
        else :
        	start = middle + 1
     return false    # 검색 실패

• 재귀 함수 이용

def bianrySearch2(a, low, high, key):
	if low > high:
    	return False
    else :
    	middle == (low + high) // 2
        if key == a[middle]:
        	return True
        elif key < a[middle]:
        	return bianrySearch2(a, low, middle-1, key)
        elif a[middle] < key:
        	return bianrySearch2(a, low, middle-1, key)

---

선택정렬

---

인덱스

• Database에서 유래된 용어로 테이블에 대한 동작 속도를 높여주는 자료구조를 말한다.
• 인덱스를 저장하는데 필요한 디스크 공간은 보통 테이블을 저장하는데 필요한 디스크 공간보다 작다.
• 배열을 사용한 인덱스
  • 대량의 데이터를 매번 정렬하면, 프로그램의 반응은 느려질 수 밖에 없다. 이러한 데이터의 성능 저하 문제를 해결하기 위해 배열 인덱스를 사용할 수 있다.

선택 정렬

• 주어진 자료들 중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식

• 정렬과정

  • 주어진 리스트 중에서 최소값을 찾는다.
  • 그 값을 리스트의 맨 앞에 위치한 값과 교환한다.
  • 맨 처음 위치를 제외한 나머지 리스트들 대상으로 위의 과정을 반복한다.

• 시간 복잡도 : O(n2)

• Ex)

def selectionSort(a, N):
	for i in range(N-1):
    	minIndex = i
        for j in range(i+1, N):
        	if a[minIndex] > a[j]:
            	minIndex = j
        a[i], a[minIndex] = a[minIndex], a[i]

• 저장되어 있는 자료로부터 k 번째로 큰 혹은 작은 원소를 찾는 방법을 설렉션 알고리즘이라고 한다.

• Ex) k번째로 작은 원소를 찾는 알고리즘

def select(arr, k):
	for i in range(0,k):
    	minIndex = i
        for j in range(i+1, len(arr)):
        	if arr[minIndex] > arr[j]:
            	minIndex = j
        arr[i], arr[minIndex] = arr[minIndex], arr[i]
    return arr[k-1]