2. Searching(탐색)_Linear, Binary

1. Search Algorithms

이 글에서 Search, 즉 탐색을 하는 방법에 대한 알고리즘 2가지를 소개하고자 한다. 첫번째는 Linear search(선형 탐색)이고, 두번째는 Binary search(이진 탐색)이다.

Linear Search는 처음부터 끝까지 하나씩 구먹구구식으로 탐색하는 것을 말하고, Binary search는 계속해서 반으로 쪼개서 탐색을 하는 방법을 말한다. 이렇게만 말해도 구현은 단순한 Linear Search가 쉽지만, 시스템이 복잡해질수록 구현하는 데에 있어서는 Linear Search보다는 복잡하지만 시간 복잡도는 확실히 Binary Search가 단축시켜줄 것만 같은 느낌이다.(느낌만 그런 것이 아니라 실제로도 그렇다.)

 

1-1. Linear search Algorithm

• 왼쪽부터 순서대로 확인하는 방식
• 정렬되지 않는 데이터들을 순차적으로 접근하여 원하는 데이터를 찾는 경우 사용(뒤에서 설명하겠지만 Binart Search를 이용하려면 데이터들이 정렬되어 있어야 한다!
• 시간 복잡도 : O(n)

 

• 장점1. 간단하고 구현이 쉽다. 2. 목록이 작거나 검색하려는 요소가 목록의 시작 부분에 있을 경우 효율적 (아다리만 맞으면 ㄱㅇㄷ)                            3. 목록에 대한 순차적 엑세스만 필요하므로 요소를 반복할 수 있는 모든 데이터 컬렉션에서 작업할 수 있음
• 단점1. 소요시간이 목록의 크게에 따라 linear하게 증가한다. 2. 목록이 크거나 찾고자 하는 요소가 뒷부분에 있을 경우 비효율적이다.

import random # 실습 데이터를 만들기 위한 모듈

def search(unordered_list, target):
    for i in range(len(unordered_list)):
        if target == unordered_list[i]:
            return i
    return None

test = []
for _ in range(10):
    # random integer n such that 1 <= n <= 15
    n = random.randint(1, 15)
    test.append(n)
print(test)

_target = 11 #local varible과 global variable 간의 차이를 두기 위함(pycharm에서는 오류이기 때문)
result = search(test, _target)
if result is None: # equality(==)는 그 안의 값을 비교해야 하기 때문에 is 보다 더 오래걸림
    print("%s is not found." % _target) # % _target : 중간에 띄어쓰기에 유의!
else:
    print("%s is at index %s" %(_target, result))

 

 

1-2. Binary search Algorithm

모든 알고리즘에서와 마찬가지로 기존의 Linar search Algorithm 보다 복잡하지만 효율적이다.(시간복잡도가 낮다.)

Binary search에서 주의해야 할 것은 리스트의 정렬이 반드시 보장되어 있어야 한다는 것이다!

 

시작, 끝, key(가운데) 값이 존재한다. target을 V라고 하면 Key와 V의 대소에 따라 상대적 위치를 파악한다.

Binary search의 대략적인 흐름을 그림으로 살펴보면 위와 같다.

 

• 시간 복잡도 : O(logn)

목록의 크기가 커질수록 목록의 요소를 검색하는데 걸리는 시간이 더 느리게 증가하지만 목록을 정렬해야 하므로 검색 프로세스에 추가 단계가 필요하다.

Linear search에 비해 구현이 복잡하지만 재귀를 사용하여 성능을 최적화할 수 있다.

def binary_search(ordered_list, target):
    left, right = 0, len(order_list)-1

    while left <= right: # left와 right가 교차하기 전까지
        mid = (left + right) // 2

        if target < ordered_list[mid]:
            right = mid - 1
        elif target > ordered_list[mid]:
            left = mid + 1
        else:
            return mid

     return None #위 반복문에서 return하지 못했다면 찾지 못한 것이기 때문에 None 객체를 반환한다.

# random sampling with replacement(중복을 허용한다.)
test = random.choices(range(1, 15), k = 10) # choices() vs. sample() : k를 반드시 정해야 함.
test.sort()
print(test)

+) choices 함수 관한 내용은 아래 블로그를 참고하면 된다.

https://codingdog.tistory.com/entry/%ED%8C%8C%EC%9D%B4%EC%8D%AC-sample-vs-choices-%EC%9D%98-%EC%B0%A8%EC%9D%B4%EB%A5%BC-%EC%95%8C%EC%95%84%EB%B4%85%EC%8B%9C%EB%8B%A4

파이썬 sample vs choices 의 차이를 알아봅시다.

 

 

 

1-3. Bisect 모듈 - Array bisection algorithm

• bisect.bisect_left(a, x, lo=0, hi=len(a))
  • x라는 point를 a리스트에 삽입을 하는데 order를 유지한 채 삽입할 수 있는 위치를 알려준다.
  • lo라는 파라미터와 hi라는 파라미터를 통해 서브리스트를 만들 수 있는 start, end index를 각각 정할 수 있다.
    • default 세팅은 리스트 전체 범위에 대해 보는 것으로 한다.(0 ~ len(list))
  • 만약 리스트 안에 이미 들어있는 값과 동일한 값에 대하여 삽입을 원하는 경우 가장 왼쪽값으로 넣게 된다.
  • 해당 모듈에 대한 자세한 설명은 아래 링크에서 확인하시면 됩니다.
  • bisect — Array bisection algorithm — Python 3.8.7 documentation

 

한마디로 binary search 구현을 좀 더 편리하게 할 수 있는 모듈이라고 생각하면 된다.

-> 이분 탐색 예제 코드

import bisect

# initializing test
li = [1, 3, 4, 4, 4, 6, 7]

# using bisect_left() to find index to insert new element
# return 2 (left most possible index)
print(bisect.bisect_left(li, 4))
# 출력값 : 2

 

import random
import bisect

def binary_search(ordered_list, target):
    index = bisect.bisect_left(ordered_list, target)

    # 주어진 리스트 안의 범위만 확인하도록(out of index 방식)
    if index < len(ordered_list) and ordered_list[index] == target:
        return index
    else:
        return None

test = random.choices(range(1, 15), k = 10)
test.sort()
print(test)

_target = 11
result = binary_search(test, _target)
if result is None:
    print('%s is not found.' % _target)
else:
    print('%s is at index %s' % (_target, result))
# 리스트 값은 랜덤하게 변할 수 있음을 참고하자.
# [4, 6, 6, 8, 8, 9, 10, 11, 12, 12]
# 11 is at index 7

 

 

지금까지 쭉 linear search, binary search에 이어 bisect 모듈을 활용하여 탐색(Search)과 관련된 알고리즘 공부를 하였다. 백준 문제를 통해 지금까지 배워 본 개념들을 적용해보며 감을 확실히 잡고 가도록 하겠다.

 

 

https://www.acmicpc.net/blog/view/109

문제를 푸는 데 감이 슬슬 잡히지 않아서 오늘은 컨디션이 불량인 관계로 금요일에 이 글을 보며 개념과 문제 풀이를 하도록 하자.

 

 

참고

https://cdragon.tistory.com/entry/%EC%9E%90%EB%A3%8C%EA%B5%AC%EC%A1%B0%EC%99%80-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Searching-and-Complexity%EB%B3%B5%EC%9E%A1%EB%8F%84

[자료구조와 알고리즘 | 파이썬] Searching(탐색)과 Complexity(복잡도) + 빅오표기법

https://velog.io/@glad415/%EC%84%A0%ED%98%95%EC%9D%B4%EC%A7%84-%ED%83%90%EC%83%89-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98by-Python

② 선형•이진 탐색 알고리즘(by Python)

https://programming119.tistory.com/196

[Python] bisect 사용법👀 / 이분탐색 / 코딩테스트

https://noahlogs.tistory.com/27

빅오 표기법 (big-O notation) 이란