List 2 (2)

• 검색

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

순차검색, 이진검색, 해쉬 등등

 

• 순차 검색

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

가장 간단하고 직관적이다.

배열, 연결 리스트 등 순차구조로 구현된 자료구조에서 항목을 찾을 때 유용하다.

알고리즘이 단순하여 구현은 쉽지만, 검색 대상 수가 많아지면 수행시간이 급격히 증가한다.

정렬되어 있지 않은 경우와 정렬되어 있는 경우로 나뉜다.

 

1. 정렬되어 있지 않은 경우

순서대로 키 값이 같은 원소가 있는지 비교하며 찾는다. 찾으면 그 원소의 인덱스를 반환한다.

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

결국 찾고자 하는 원소가 어디 순서에 있는지에 따라 비교회수가 결정된다.

시간 복잡도 = O(n)

 

2. 정렬되어 있는 경우

자료가 오름차순으로 정렬되어 있다고 가정하면 자료를 순차적으로 검색하다가 찾는 키 값보다 큰 원소가 나온다면 찾는 원소가 없다는 뜻이므로 탐색을 일찍 종료할 수 있다.

위와 같이 찾고자 하는 원소가 어디 순서에 있는 지에 따라 비교회수가 결정되지만, 정렬이 되어있으므로, 검색 실패를 반환하는 경우 평균 비교 회수가 반으로 줄어든다.

시간 복잡도 = O(n)

 

• 이진 검색

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

→ 값을 찾을 때까지 이진 검색을 반복 수행하여 검색 범위를 반으로 줄여가면서 빠르게 검색이 가능

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

검색과정 :

자료의 중앙에 있는 원소를 고른다. (중앙의 인덱스를 구하면 된다.)

중앙 원소 값과 찾고자 하는 값과 비교한다.

목표 값이 더 작으면 자료의 왼쪽 절반에서 검색하고 크다면 오른쪽 절반에 대해서 검색을 수행한다.

값을 찾을 때까지 위 과정을 반복한다.

반의 반의 반도~~~ 하면서 검색 범위를 계속 절반씩 줄여나갈 수 있다.

구현을 위해서는 검색 범위의 시작점과 종료점을 알아야 하고 자료의 삽입이나 삭제가 발생했을 때

배열의 상태를 항상 정렬 상태로 유지하는 추가 작업이 필요하다.

def binary_search(arr, N, key):
    start = 0 # 구간 초기화
    end = N - 1
    while start <= end:             # 검색 구간이 유효하면 반복
        middle = (start + end) // 2 # 중앙 원소 인덱스
        if arr[middle] == key:
            return middle
        elif arr[middle] > key: # 중앙값이 키보다 클 경우
            end = middle - 1
        else:                   # 중앙값이 키보다 작을 경우
            start = middle + 1
    return -1                   # 검색 실패

 

• 인덱스

테이블에 대한 동작 속도를 높여주는 자료 구조

배열을 사용한 인덱스 → 대량의 데이터를 매번 정렬하면 프로그램의 반응이 느려질 수 밖에 없다.

이러한 문제를 방지하기 위해 배열 인덱스를 사용할 수 있다.

인덱스가 이중으로 있는 느낌이다.

특정 기준에 따른 인덱스와 별개로 항목과 대응하는 원본 데이터의 인덱스도 항목마다 유지함!

 

• 선택 정렬

당구공을 가장 작은 숫자부터 차례대로 정리하는 것과 같은 선택 정렬

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

정렬 과정 :

주어진 리스트 중에서 최소값을 찾는다.

그 값을 리스트의 맨 앞에 위치한 값과 교환한다.

맨 처음 위치를 제외한 나머지 리스트를 대상으로 위의 과정을 반복한다.

미정렬 원소가 하나 남은 상황에서는 마지막 원소가 가장 큰 값을 갖게 되므로, 실행을 종료한다.

시간 복잡도 = O(n**2)

def selectionsort(a, N):
    for i in range(N-1):    # i 주어진 구간의 시작
        min_idx = i         # 맨 앞 원소를 최솟값 위치로 가정
        for j in range(i + 1, N):   # 실제 최솟값 위치 검색
            if a[min_idx] > a[j]:
                min_idx = j
        a[i], a[min_idx] = a[min_idx], a[i]

 

• 셀렉션 알고리즘

저장되어 있는 자료로부터 k번째로 큰 혹은 작은 원소, 최대값, 최솟값, 중간값 등을 찾는 방법

선택 과정 :

정렬 알고리즘을 이용하여 자료 정렬하기

원하는 순서에 있는 원소 가져오기

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

1번부터 k번째까지 작은 원소들을 찾아 배열의 앞쪽으로 이동시키고, 배열의 k번째를 반환한다.

k가 비교적 작을 때 유용하며, O(kn)의 수행시간을 필요로 한다.

def select(arr, K):
    for i in range(K):    # 구간의 시작을 i로 설정
        min_idx = i # 구간의 최솟값 위치 min_idx, 첫 원소를 최소로 가정
        for j in range(i+1, len(arr)): # 실제 최솟값을 찾을 위치 j
            if arr[min_idx] > arr[j]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i] # 최솟값을 구간의 맨 앞으로 이동
    return arr[K-1]

 

• 비트 연산자 (보충)

&(and)

| (or)

<<

(shift)

 

a = 1 = 이진수 1 로 비트에 저장되어 있음.

비트에서 옆으로 한칸 옮기는 것은 이진수 자릿수를 옮기는 것 (2배 or 1/2배)

print(a << 1) = 이진수 10 = 2 (a를 2배)

print(a << 2) = 이진수 100 = 4 (a를 2**2배)

print(10 << 1) = 20 (10을 2배)

print(10 >> 1) = 5

print(5 >> 1) = 2 (가장 오른쪽 비트에 있던 1이 오른쪽으로 밀려서 버려짐. 그래서 2가 된다.)

 

n만큼 << 자리 옮긴다 = 2**n 배를 한다.

 

굳이 나누기, 곱하기 등의 산술연산자가 아니라 비트연산자를 사용하는 이유?

→ 잘난 척 하려는게 아니라 산술 연산자가 cpu를 잡아 먹는데에 비해 비트 연산자는 매우 빠르다!

그래서 실행 속도를 줄이거나 cpu 성능이 안좋은 컴퓨터에서 잘 굴러가게 하려고 할 때

비트 연산자를 많이 쓴다.