자료구조 - 3장 검색 알고리즘

 

- 검색의 종류

   1. 배열 검색

   2. 연결 리스트 검색

   3. 이진 검색 트리 검색

 

 

- 배열 검색   ( 해당 조건에 맞게 알맞게 선택)

  1. 선형 검색 

  2. 이진 검색 - 일정한 규칙으로 늘어놓은 데이터 집합에서 빠른 검색 수행

  3. 해시법  - 추가 및 삭제가 빈번히 일어나는 데이터 집합에서 빠른 검색 수행

---

1. 선형 검색 (가장 기본적인 알고리즘)

 - 원하는 값을 찾을때까지 맨 앞부터 순서대로 검색하는 알고리즘

 - 정렬되지 않은 배열에서 검색할 때 사용하는 유일한 방법

1)

arr=[.....]

i=0

while True:

 if i == len(arr): return -1 // 검색 실패 시

 if arr[i]== key: return i  // 검색 성공 시 해당 인덱스 번호 반환 

 i+=1

 

2)

for i in range(len(arr)):

   if i==key: return i

return -1

 

보초법 : 찾는 답을 마지막 배열에 추가하여 과정의 반복을 반으로 줄이는 방법

           (검색 실패의 조건을 없애 과정을 줄인다)

arr=[.....]

i=0

while True:

if a[i] == key: break

i+=1

return -1 if i==len(arr) else i // 검색에 실패할 때 -1 반환 

---

 2. 이진 검색 

- 정렬이 된 배열에서 좀 더 효율적으로 검색할 수 있는 알고리즘 

 

1. right, left, mid 범위를 지정한다  left=0 ,  right=len(배열)-1, mid =(right+left)//2 

2. mid 값과 key값 비교한다.

  2.1 mid > k  right =mid-1

  2.2 mid < k  left = mid+1 

3.  left > right가 될 때까지 1,2번 과정을 반복 한다.

   3.1 종료 

 

while True:

       pc=(pl+pr)//2

       if arr[pc]==find:

            print(f'arr[{arr[pc]}]는 {pc}에 위치합니다.')

            break

      elif arr[pc] < find : 

            pl=pc+1

     else:

           pr=pc-1

---

 

복잡도 - 알고리즘 성능을 객관적으로 평가하는 기준

1. 시간 복잡도 : 실행하는 데 필요한 시간을 평가

   n에 비례하는 횟수 만큼 실행되는 경우의 복잡도는 O(n) 

   전체 복잡도는 차원이 가장 높은 복잡도이다. 선형 검색 알고리즘 복잡도는 =O(n)

  작다 <- 1 - log n - n - n log n - n2 - n3 - n4 - 2n -> 크다

ex) N=16

O(1) : 1

O(logN) : 16-> 4*4, =4

O(N) : 16

O(N log N) :  16 log 16 = 4*16

...

2. 공간 복잡도 : 메모리와 파일 공간이 얼마나 필요한지를 평가

 

index() 함수 - 배열.index(찾을 문자,left,right) - 배열에서 문자를 찾아서 인덱스번호를 반환, left,right 는 생략 가능,

                   문자 없으면 오류

 

---

3. 해시법 

- 데이터가 추가 , 삭제도 효율적으로 수행할 수 있는 검색 알고리즘

 

정렬된 배열에서 원소 추가하기

  1. 이진 검색법으로 추가 할 수 있는 인덱스 번호를 찾는다.

  2. 찾은 인덱스 번호 이후의 모든 원소를 한 칸씩 뒤로 이동함

  3. 찾은 인덱스 번호에 원소 추가

->  한 칸 씩 뒤로 이동하기 때문에 많은 비용이 소요된다.

 

해시법 : 원소에 있는 모든 값을 원소 개수 만큼 나눈 나머지값으로 바꾼다.

   - 해시값 : 나눈 나머지 값 (인덱스 번호) 

   - 해시테이블 :  해시법을 사용해서 새로 저장한 배열 

   - 버킷 : 해시테이블에서 만들어진 원소 

   - 해시 함수 : 해시법을 사용하여 변환하는 과정 

   - 해시 충돌 (저장할 버킷이 중복되는 현상)

      1. 체인법 : 해시값이 같은 원소를 연결리스트로 관리

        - 저장하는 개념이 아니라 해시값으로 하는 노드를 참조하는 것이다.

 

      2. 오픈 주소법  : 빈 버킷을 찾을 때까지 해시를 반복 

       - (값)%크기 -> 충돌 -> (값+1)%크기 -> 충돌 -> (값+2)%크기 ....->빈 버킷을 찾으면 추가