[Do it! 자료구조와 함께 배우는 알고리즘 입문 : 파이썬 편] 03. 검색 알고리즘-1

03. 검색 알고리즘

03-1. 검색 알고리즘이란?

검색과 키

키 key : 검색 조건이 주목하는 항목(데이터의 일부)

 

검색의 종류

배열 검색, 연결 리스트 검색, 이진 검색 트리 검색 등

 

배열 검색

선형 검색

무작위로 늘어놓은 데이터 집합에서 검색 수행

 

이진 검색

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

 

해시법

추가 · 삭제가 자주 일어나는 데이터 집합에서 아주 빠른 검색 수행

- 체인법 : 같은 해시값 데이터를 연결 리스트로 연결

- 오픈 주소법 : 데이터를 위한 해시값이 충돌할 때 재해시

 

03-2 선형 검색

선형 검색 linear search

직선 모양(선형)으로 늘어선 배열에서 검색하는 경우, 원하는 키값을 가진 원소를 찾을 때까지 맨 앞부터 스캔하여 순서대로 검색하는 알고리즘

= 순차 검색 sequential search

좌 : 선형 검색 / 우 : 이진 검색, 선형 검색 비교

 

선형 검색의 종료 조건

• 검색 실패 : 검색할 값을 찾지 못하고 배열의 맨 끝을 지나간 경우
• 검색 성공 : 검색할 값과 같은 원소를 찾는 경우

-> 해당 조건을 판단하는 평균 횟수 : 배열 원소의 개수 / 2번

## 선형 검색 pseudo code
i = 0
while True:
    if i == len(a):
        # 검색 실패
    if a[i] == key:
        # 검색 성공(찾은 원소의 인덱스는 i)
    i += 1

# [Do it! 실습 3-1] while 문으로 작성한 선형 검색 알고리즘

from typing import Any, Sequence

def seq_search(a: Sequence, key: Any) -> int:
    """시퀀스 a에서 key값이 같은 원소를 선형 검색(while 문)"""
    i = 0

    while True:
        if i == len(a):
            return -1  # 검색에 실패하여 -1을 반환
        if a[i] == key:
            return i   # 검색에 성공하여 현재 조사한 배열의 인덱스를 반환
        i += 1

if __name__ == '__main__':
    num = int(input('원소 수를 입력하세요.: '))  # num 값을 입력
    x = [None] * num                           # 원소 수가 num인 배열을 생성

    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))

    key = int(input('검색할 값을 입력하세요.: '))  # 검색할 키 key를 입력받기

    idx = seq_search(x, key)                     # key와 같은 원소를 x에서 검색

    if idx == -1:
        print('검색값을 갖는 원소가 존재하지 않습니다.')
    else:
        print(f'검색값은 x[{idx}]에 있습니다.')

# 실행 결과
원소 수를 입력하세요.:5
x[0]: 1
x[1]: 2
x[2]: 3
x[3]: 4
x[4]: 5
검색할 값을 입력하세요.: 3
검색값은 x[2]에 있습니다.

 

while문을 for문으로 리팩토링

# [Do it! 실습 3-2] for 문으로 작성한 선형 검색 알고리즘

from typing import Any, Sequence

def seq_search(a: Sequence, key: Any) -> int:
    """시퀀스 a에서 key값이 같은 요소를 선형 검색(for문)"""
    for i in range(len(a)):
        if a[i] == key:
            return i # 검색 성공(인덱스를 반환)
    return -1       # 검색 실패(-1을 반환)

if __name__ == '__main__':
    num = int(input('원소 수를 입력하세요.: ')) # num 값을 입력
    x = [None] * num                        # 원소 수가 num인 배열을 생성

    for i in range(num):
        x[i] = int(input(f'x[{i}]: '))

        key = int(input('검색할 값을 입력하세요.: ')) # 검색할 키 key를 입력받음

        idx = seq_search(x, key)                  # key와 같은 값의 요소를 x에서 검색

        if idx == -1:
            print('검색 값을 갖는 요소가 존재하지 않습니다.')
        else:
            print(f'검색 값은 x[{idx}]에 있습니다.')

# 실행 결과
원소 수를 입력하세요.: 3
x[0]: 5
검색할 값을 입력하세요.: 2
검색 값을 갖는 요소가 존재하지 않습니다.
x[1]: 4
검색할 값을 입력하세요.: 3
검색 값을 갖는 요소가 존재하지 않습니다.
x[2]: 2
검색할 값을 입력하세요.: 2
검색 값은 x[2]에 있습니다.

 

 

03-3 이진 검색

이진 검색 binary search

원소가 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색할 수 있는 알고리즘

선형 검색보다 빠르게 검색 가능

 

이진 검색 알고리즘을 실행하는 프로그램

# [Do it! 실습 3-3] 이진 검색 알고리즘

from typing import Any, Sequence

def bin_search(a: Sequence, key: Any) -> int:
    """시퀀스 a에서 key와 일치하는 원소를 이진 검색"""
    pl = 0           # 검색 범위 맨 앞 원소의 인덱스
    pr = len(a) - 1  # 검색 범위 맨 끝 원소의 인덱스

    while True:
        pc = (pl + pr) // 2  # 중앙 원소의 인덱스
        if a[pc] == key:
            return pc    # 검색 성공
        elif a[pc] < key:
            pl = pc + 1  # 검색 범위를 뒤쪽의 절반으로 좁힘
        else:
            pr = pc - 1  # 검색 범위를 앞쪽의 절반으로 좁힘
        if pl > pr:
            break
    return -1            # 검색 실패

if __name__ == '__main__':
    num = int(input('원소 수를 입력하세요.: '))
    x = [None] * num  # 원소 수가 num인 배열을 생성

    print('배열 데이터를 오름차순으로 입력하세요.')

    x[0] = int(input('x[0]: '))

    for i in range(1, num):
        while True:
            x[i] = int(input(f'x[{i}]: '))
            if x[i] >= x[i - 1]:
                 break

    ky = int(input('검색할 값을 입력하세요.: '))  # 검색할 ky를 입력

    idx = bin_search(x, ky)                     # ky와 같은 값의 원소를 x에서 검색

    if idx < 0:
        print('검색값을 갖는 원소가 존재하지 않습니다.')
    else:
        print(f'검색값은 x[{idx}]에 있습니다.')

# 실행 결과
원소 수를 입력하세요.: 5
배열 데이터를 오름차순으로 입력하세요.
x[0]: 1
x[1]: 2
x[2]: 3
x[3]: 4
x[4]: 5
검색할 값을 입력하세요.: 3
검색값은 x[2]에 있습니다.

 

복잡도 complexity

종류

시간 복잡도 time complexity : 실행하는 데 필요한 시간 평가

공간 복잡도 space complexity: 메모리(기억 공간)와 파일 공간이 얼마나 필요한지 평가

 

선형 검색의 시간 복잡도

선형 알고리즘의 복잡도 = O(n)

def seq_search(a: Sequence, key: Any) -> int:
i = 0 # 1단계

while i < n # 2단계
	if a[i] == key: # 3단계
    	return i          # 4단계 검색에 성공하여 인덱스를 반환
    i += 1                # 5단계

return -1                 # 6단계 검색에 실패하여 -1을 반환

단계	실행 횟수	복잡도
1	1	O(1)
2	n/2	O(n)
3	n/2	O(n)
4	1	O(1)
5	n/2	O(n)
6	1	O(1)

 

 

이진 검색의 시간 복잡도

선형 알고리즘의 복잡도 = O(log n)

def bin search(a: Sequence, key: Any) -> int:
   """시퀀스 a에서 key와 일치하는 원소를 이진 검색"""
pl = 0                     # 1단계: 검색 범위 맨 앞 원소의 인덱스
pr = len(a) - 1            # 2단계: 검색 범위 맨 끝 원소의 인덱스

while True:
	pc = (pl + pr) // 2    # 3단계: 중앙 원소의 인덱스
    if a[pc] == key:       # 4단계
    	return pc          # 5단계: 검색 성공
    elif a[pc] < key:      # 6단계
    	pl = pc + 1        # 7단계: 검색 범위를 뒤쪽 절반으로 좁힘
    else:
    	pr = pc - 1        # 8단계: 검색 범위를 앞쪽 절반으로 좁힘
    if pl > pr:            # 9단게
    	break
return -1                  # 10단계: 검색 실패

단계	실행 횟수	복잡도
1	1	O(1)
2	1	O(1)
3	log n	O(log n)
4	log n	O(log n)
5	1	O(1)
6	log n	O(log n)
7	log n	O(log n)
8	log n	O(log n)
9	log n	O(log n)
10	1	O(1)

 

이진 검색의 실행 과정 출력하기

# [Do it! 실습 3C-3] 이진 검색 알고리즘의 실행 과정을 출력

from typing import Any, Sequence

def bin_search(a: Sequence, key: Any) -> int:
    """시퀀스 a에서 key와 일치하는 원소를 이진 검색(실행 과정을 출력)"""
    pl = 0           # 검색 범위 맨 앞 원소의 인덱스
    pr = len(a) - 1  # 검색 범위 맨 끝 원소의 인덱스

    print('   |', end='')
    for i in range(len(a)):
        print(f'{i : 4}', end='')
    print()
    print('---+' + (4 * len(a) + 2) * '-')

    while True:
        pc = (pl + pr) // 2  # 중앙 원소의 인덱스

        print('   |', end='')
        if pl != pc:         # pl 원소 위에 <-를 출력
            print((pl * 4 + 1) * ' ' + '<-' + ((pc - pl) * 4) * ' ' + '+', end='')
        else: 
            print((pc * 4 + 1) * ' ' + '<+', end='')
        if pc != pr:         # pr 원소 위에 ->를 출력
            print(((pr - pc) * 4 - 2) * ' ' + '->')
        else:
            print('->')
        print(f'{pc:3}|', end='')
        for i in range(len(a)):
            print(f'{a[i]:4}', end='') 
        print('\n   |')

        if a[pc] == key:
            return pc    # 검색 성공
        elif a[pc] < key:
            pl = pc + 1  # 검색 범위를 뒤쪽의 절반으로 좁힘
        else:
            pr = pc - 1  # 검색 범위를 앞쪽의 절반으로 좁힘
        if pl > pr:  
            break
    return -1            # 검색 실패

if __name__ == '__main__':
    num = int(input('원소 수를 입력하세요.: '))
    x = [None] * num  # 원소 수가 num인 배열을 생성

    print('배열 데이터를 오름차순으로 입력하세요.')

    x[0] = int(input('x[0]: '))

    for i in range(1, num):
        while True:
            x[i] = int(input(f'x[{i}]: '))
            if x[i] >= x[i - 1]:
                 break

    ky = int(input('검색할 값을 입력하세요.: '))  # 검색할 ky를 입력

    idx = bin_search(x, ky)                     # ky와 같은 값의 원소를 x에서 검색

    if idx == -1:
        print('검색값을 갖는 원소가 존재하지 않습니다.')
    else:
        print(f'검색값은 x[{idx}]에 있습니다.')

# 실행 결과
원소 수를 입력하세요.: 11
배열 데이터를 오름차순으로 입력하세요.
x[0]: 1
x[1]: 2
x[2]: 3
x[3]: 4
x[4]: 5
x[5]: 6
x[6]: 7
x[7]: 8
x[8]: 9
x[9]: 10
x[10]: 11
검색할 값을 입력하세요.: 8
   |   0   1   2   3   4   5   6   7   8   9  10
---+----------------------------------------------
   | <-                    +                  ->
  5|   1   2   3   4   5   6   7   8   9  10  11
   |
   |                         <-        +      ->
  8|   1   2   3   4   5   6   7   8   9  10  11
   |
   |                         <+  ->
  6|   1   2   3   4   5   6   7   8   9  10  11
   |
   |                             <+->
  7|   1   2   3   4   5   6   7   8   9  10  11
   |
검색값은 x[7]에 있습니다.