[WEEK01] 검색 알고리즘 (선형검색 / 이진검색) + 트리자료구조

[Do it 자료구조와 함께 배우는 알고리즘 입문 with 파이썬] 개념 정리

1) 선형 검색

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

: linear search  / sequential search(순차검색)으로 불림

종료조건 1) if i == len(a) 성립시 스캔종료

종료조건 2) if a[i] == key 성립시 스캔종료

 

보초법 (sentinel method)

: 검색할 값을 배열의 맨 끝에 추가

종료조건 1)  if i == len(a) 성립시 스캔종료 (보초법에서는 필요없음)

종료조건 2) if a[i] == key 성립시 스캔종료 (for문 마지막에 체크해서 맨 끝 값과 같으면 false)

 

 

2) 이진 검색

: 원소가 오름차순이나 내림차순으로 정렬된 배열에서 좀 더 효율적으로 검색가능

: binary search

: 시작점, 끝점, 중간점을 활용하여 찾으려는 데이터(target)과 중간점(middle)을 반복적으로 비교해서 찾음

: 재귀함수나 반복문으로 구현하는데 실제 테스트에서는 어려울 수 있으므로 코드를 반복 수행하는 것이 필요함

: 폭 넓게 사용되는 원리이므로 매우 중요함!

: 시간 복잡도는 O(logn)

: (예를 들어 64개의 원소를 2개씩 나눈다고 생각해보면, 2개씩 나누다가 마지막 1이 되는 순간은 6번째임

     ⇒ log64 = 6이 되므로 O(logn)이 시간복잡도!)

 

pl(맨 왼쪽) / pc(가운데) / pr(맨 오른쪽)

a[pc] < key

: 중앙(pc)에서 오른쪽 한칸 이동하여 새로운 왼쪽 끝 pl 지정

: 검색범위를 뒤쪽 절반으로 좁힘

 

a[pc] > key

: 중앙(pc)에서 왼쪽 한칸 이동하여 새로운 오른쪽 끝 pr 지정

: 검색범위를 앞쪽 절반으로 좁힘

 

종료조건 1) a[pc]와 key가 일치하는 경우

종료조건 2) 검색범위가 더 없는 경우 

 

# 이진 검색 알고리즘

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    
    
    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("검색할 값을 입력하세요.: "))
    
    idx = bin_search(x, ky)
    
    if idx == -1:
        print('검색값을 갖는 원소가 존재하지 않습니다.')
    else:
        print(f'검색값은 x[{idx}]에 있습니다.')

 

시간복잡도

: 검색시 = 평균 O(log(n))

: 검색에 실패할 경우 = log(n+1)

: 검색에 성공할 경우 = log(n-1)

: 2,000만 넘어가면 이진탐색으로 문제 접근 필요

 

3) 트리자료구조

특징

: 트리는 부모노드와 자식노드 관계로 표현됨

: 트리의 최상단 노드 = 루트노드

: 트리의 최하단 노드 = 단말노드

: 트리의 일부를 떼어내도 트리구조이며 이를 서브트리라고 함

: 트리는 파일시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합

 

이진탐색트리

: 왼쪽 자식노드 < 부모노드 < 오른쪽 자식노드가 성립되어야 구현 가능