플레찍었으니 정리해보는 알고리즘 노트 1 - 이진탐색

이진 탐색 알고리즘이란?

 

이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다. - 위키백과

 

알고리즘의 작동원리 및 구현 방법은 다른 블로그에서 더 잘 설명해줄거니까 생략한다.

def binarySearch(lst,value):
    low = 0
    high = len(lst)-1
    
    while low < high:
        c = int((low+high)/2)
        if lst[c] < value:
            low = c + 1
        elif lst[c] == value:
            return c
        else:
            high = c -1
            
    return False

 

백준 문제를 풀던 중 시간초과가 발생했을 때 첫번째로 확인할 부분은 코드에 시간복잡도를 잡아먹는 부분이 있는가를 찾아봤는데

주로 나왔던 실수는

 

1. 반복문 안에서 배열을 초기화했을 때 배열을 매번 새로 만들면서 시간초과

2. 배열을 순차탐색하는 코드의 존재였다.

 

2번 같은 문제를 해결하는데 가장 유용한 해결책으로 이진 탐색을 자주 사용했다.

 

이진탐색의 응용인 upper_bound, lower_bound를 사용하면 문제가 효과적으로 풀리는 경우도 많이 존재했다.

def lower_bound(lst,value): # value 보다 크거나 같은 숫자가 처음으로 나타나는 위치 반환
    low = 0
    high = len(lst)
    
    while low < high:
        c = int((low+high)/2)
        if lst[c] < value:
            low = c + 1
        else:
            high = c
            
    return low

def upper_bound(lst,value): # value 보다 큰 숫자가 처음으로 나타나는 위치 반환
    low = 0
    high = len(lst)
    
    while low < high:
        c = int((low+high)/2)
        if lst[c] <= value:
            low = c + 1
        else:
            high = c
            
    return low

upper_bound, lower_bound 함수는 배열 안에서 특정 수의 위치를 찾아야하는 상황에서 사용되는데

그냥 이진탐색과 다르게 배열 안에 같은 숫자가 여러개 존재하거나 찾는 숫자가 배열에 존재하지 않을 수도 있을때

즉 여러가지 조건이 붙은 상황에서 탐색할때 굉장히 효과적으로 사용된다.

또 하나의 배열안에 특정한 숫자가 몇개나 있는지 알아야 할 때

upper_bound() - lower_bound() 를 이용하면 빠르게 알아낼 수 있다.

 

 

 

1. 이분탐색

2. 중간에서 만나기, 투포인터

3. GCD, 유클리드 호제법

4. 세그먼트 트리

5. CCW

6. 우선순위큐

7. 유니온파인드, 최소 스패닝 트리, 위상정렬

8. LIS