검색(Search)

in Blog / 알고리즘

검색 알고리즘 같은 경우 마냥 빠르게 되는것으로만 고려하면 안된다. 데이터의 추가/삭제 같은 작업이 수행될때 들어가는 비용까지 종합적으로 평가해야한다.

검색 알고리즘의 예제들을 아래 나열해 봤다.

예제 : 찾고자 하는 데이터를 정렬된 데이터에서 하나하나 검색을 수행함

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

또는 아래처럼 선형 검색을 받아와서 사용해도 된다.

from ssearch_while import seq_search

seq_search(list : 데이터 집합, x : 찾고자 하는 인수(정수, float, 문자열))

선형 검색 같은 경우 무한루프 방지를 위해 count 변수를 둔다. count 변수 같은 경우 존재하면 계속 계산이 들어가게 되는데, 그걸 방지하고자 보초법이 등장한다.

보초법이 뭐냐, 데이터 집합 끝에 검색하고자 하는 값을 추가 후 해당 값을 찾으면 루프가 종료되게끔 하는 것이다. 아래 예제를 한번 보자

선형 검색(Linear search) with 보초법(Sentinel method)

예제 :

def seq_search(dat: Data, key: any):
    """Data에서 key와 일치하는 원소를 선형 검색(보초법)"""
    a = copy.deepcopy(dat) #dat를 복사
    a.append(key)          #보초 key를 추가

    i = 0
    while True:
        if a[i] == key:
            break
        i += 1
    return -1 if i == len(dat) else i

  • 이진 검색같은 경우 정렬된 데이터에서만 적용이 가능하며, 정수뿐만 아니고 문자열 또는 실수에도 사용이 가능하다. 다만, 실수에 사용시 부동소수점 오차를 방지를 위한 epsilon 을 사용하는것이 좋다.

  • 정렬이 왜 되어 있어야 하냐면, 중앙 원소와 먼저 대소관계 비교를 하고 위쪽 또는 아래쪽의 중앙 원소끼리 대소 관계를 비교하는데, 이 과정이 정렬이 되어 있어야만 적용이 가능하기 때문이다

  • pl과 pr이 존재하며 (pl + pr) //2 인 pc도 존재한다

예제 :

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            # 검색 실패

예제 : DFS 사용

def dfs(path, depth, n):
    if depth == n:
        print(path)
        return
    
    for i in range(1, n+1):
        if i not in path:  # 중복 방지
            dfs(path + [i], depth + 1, n)

dfs([], 0, 3)

129 페이지에 뭔가 신기한 표현법이 있는데, 스킵했다. 나중에 시간되면 보도록 하자

© 2022 JeongHwan Yun.