이진탐색, 선택정렬

검색

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

목적하는 탐색 키를 가진 항목을 찾는 것

• 탐색 키(search key): 자료를 구별하여 인식할 수 있는 키

종류

• 순차검색 sequential
• 이진검색 binary
• 해쉬

순차 검색

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

검색과정

-첫 번쨰 원소부터 순서대로 검색 대상과 키 값이 같은 원소가 있는지 비교하며 찾는다

키 값이 동일한 원소를 찾으면 그 원소의 인덱스를 반환한다 find() 쓰면 -1 반환 하는 등으로

자료구조의 마지막에 이를 때까지 검색 대상을 찾지 못하면 검색 실패

정렬되어 있지 않은 경우

찾고자 하는 원소의 순서에 따라 비교회수가 결정됨

• 첫 번째 원소를 찾을 때는 1번 비교, 두번쨰 원소를 찾을 때는 2번 비교
• 정렬되지 않은 자료에서의 순차 검색의 평균 비교 회수
  • 검색 성공의 경우= (1/n) *(1+2+3+…+n) = (n+1) , 실패했을 때는 n번
• 시간 복잡도 : O(n)

# 순차탐색 while 문 def sequential_search(a,n,key)   i<-0   while i 

# 순차탐색 for문 def seq_search(a,n,key):   for i in range(n):     if a[i] == key:       return i   return -1

정렬되어 있는 경우

오름차순에서 정렬된 상태에서 검색을 실시한다고 가정

자료를 순차적으로 검색하면서 키 값 비교해 나감

→ 원소의 키 값이 검색 대상의 키 값보다 크면 찾는 원소가 없다는 말

→ 더 이상 검색 진행하지 않고 검색을 종료

검색 성공의 여부와 별개로 평균적으로 n/2번

정렬을 하고 찾는 것이 어느 시점에서 더 빠를 수 있다. == 고려해봐야 할 사항

 

찾고자 하는 원소의 순서에 따라 비교 회수가 결정됨

• 정렬이 되어있으므로, 검색 실패를 반환하는 경우 평균 비교 회수가 반으로 줄어든다.
• 시간 복잡도 O(n)

def sequential_search2(a,n,key)   i<-0   while i 

이진 탐색 Binary Search

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

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

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

검색 과정

• 자료의 중앙에 있는 원소를 고른다.
• 중앙 원소의 값과 찾고자 하는 목표값을 비교한다.
• 목표값 < 중앙 원소 값 = 자료의 왼쪽 반에 대해서 새로 검색목표값 > 중앙 원소 값 = 자료의 오른쪽 반에 대해서 새로 검색
• 찾고자 하는 값을 찾을 때까지 해당 과정을 반복

구현

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

def binary_search(arr, N, key):   start = 0 # 구간 초기화   end = N -1   while start <= end: # 검색 구간이 유효하면 반복     mid = (start + end) // 2 # 중앙원소 인덱스     if arr[mid] == key:       return mid # 검색 완료 True     elif arr[mid] > key: # 중앙 값이 키보다 크면       end = mid - 1     else: # 중앙 값이 키보다 작으면       start = mid + 1   return -1 # 검색 실패 -1, False, x 등등 start > end 될 때 검색실패

n이 1부터 시작할 때

def countPage(page,goal):   cnt = 0   start = 1 #페이지 수는 양수기 때문에 1<= page<= 400 총 400장   end = page # n-1을 쓰려면 인덱스 0부터 셈이 시작되야된다.   while start <= end:     mid = (start + end) // 2     cnt += 1     if mid == goal:       return cnt     elif mid > goal:       end = mid     else:       start = mid

재귀 함수 이용 (진짜 진짜 참고용)

def binarySearch2(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 binarySearch2(a, low, middle-1, key)     elif a[middle] < key:  return binarySearcch2(a, middle+1, high, key)

인덱스

• Database에서 유래한 단어테이블에 대한 동작 속도를 높여주는 자료 구조를 일컫는다.
• Database 분야가 아닌 곳에서는 Look up table 등의 용어를 사용하기도 함
• 인덱스를 저장하는데 필요한 디스크 공간은 보통 테이블을 저장하는데 필요한 디스크 공간보다 작음왜냐하면 보통 인덱스는 키-필드만 갖고 있고, 테이블의 다른 세부 항목들은 갖고 있지 않기 때문이다.
• 배열을 사용한 인덱스대량의 데이터를 매번 정렬하면, 프로그램의 반응은 느려질 수 밖에 없다.
• 이러한 대량 데이터의 성능 저하 문제를 해결하기 위해 배열 인덱스 사용

배열 인덱스

• 원본 데이터에 데이터가 삽입될 경우 상대적으로 크기가 작은 인덱스 배열을 정렬하기 때문에 속도가 빠르다.
  • 이름 인덱스 배열과 id 인덱스 배열을 원본 데이터 배열에 넣으려고 할 때

  

선택정렬 Selection Sort

포켓볼 순서대로 정렬하기 예시

• 흩어진 당구공을 정리한다고 할 때, 어떻게 할 것인가?
• 대부분 가장 작은 숫자의 공부터 골라서 차례대로 정리할 것이다. = 선택 정렬

 

• 주어진 자료들 중 가장 작은 값의 원소부터 차례대로 선택하여 위치를 교환하는 방식 (오름차순에 대한 설명)
  • 선택 알고리즘을 전체 자료에 적용한 것이다.
• 정렬 과정
  • 주어진 리스트 중에서 최소 값을 찾는다.
  • 그 값을 리스트의 맨 앞에 위치한 값과 교환한다.
  • 맨 처음 위치를 제외한 나머지 리스트(미정렬 리스트)를 대상으로 위의 과정을 반복한다
  • 미정렬 원소가 하나 남은 상황에서는 마지막 원소가 가장 큰 값을 갖게 되므로, 실행을 종료하고 선택 정렬이 완료된다.
• 시간 복잡도 $O(n^2)$

# 알고리즘 for i:0->n-2   min_idx = i   for j : i+j -> N-1     arr[min_idx] <-> arr[i] def SelectionSort(a[],n)   for i from 0 to n-2     a[i]....a[n-1] 원소 중 최소값 a[k] 찾음     a[i] 와 a[k] 교환

# 선택 정렬 코드 def selection_sort(arr,N):   for i in range(N-1): # 구간의 시작 i, 2개의 원소가 남을 때 까지     min_idx = i # 구간의 최소값 위치 min_idx, 첫 원소를 최소로 가정     #min_v 필요없다. 위치값만 있으면 된다.     for j in range(i+1, N):# 실제 최솟값을 찾을 위치 j       if arr[min_idx] > arr[j]: # 더 작은 값이 있으면 바꿔줘         min_idx = j    # if i != min_idx 가 들어가야 될까? 그냥 교환하면되는데, 왜 추가비교하냐     arr[min_idx], arr[i] = arr[i], arr[min_idx]# 최소값을 구간의 맨 앞으로 이동   return #정렬만 하면되서 따로 return이 없음       # 몇 번째 값이 필요하다면 넣으면 됨 # 이거 두개 합치기

셀렉션 알고리즘

• 저장되어 있는 자료로부터 k번째로 큰 or 작은 원소를 찾는 방법
  • 최소값, 최대값 혹은 중간 값을 찾는 알고리즘을 의미
• 선택 과정
  • 설렉션은 아래와 같은 과정을 통해 우리어진다
    • 정렬 알고리즘을 이용하여 자료 정렬하기
    • 원하는 순서에 있는 원소 가져오기

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

• 1번부터 k번째까지 작은 원소들을 찾아 배열의 앞쪽으로 이동시키고, k번째를 반환
• k가 비교적 작을 때 유용하며 O(kn)의 수행시간을 필요로 한다.

def select(arr,k):   for i in range(0,k): #range(n-1)     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]