Binary Search

🚨 ‘이것이 취업을 위한 코딩테스트다’ 교재 정리

이진탐색

이진탐색은 데이터의 크기가 클 때 효율적인 탐색 알고리즘이다. 한번 탐색 할 때 마다 탐색 범위를 반 씩 줄여나가면서 값을 찾기 때문에 속도가 매우 빠르다.

이진탐색은 정렬된 자료에 대해서만 사용할 수 있다. 코딩테스트에 자주 출제되는데, 문제에서 탐색해야 할 데이터의 양이 1,000만 단위 이상으로 넘어간다면 이진탐색 사용을 고려해보는 것이 좋다. 그 아이디어만 생각해내도 문제푸는데 도움이 될 것이다.
자주 출제되는 유형인 만큼 코드를 자주 보고 외워두는 것이 좋다.

원리

이진탐색은 start, end, middle 세가지 값을 이용한다. start와 end 사이의 값이 middle 인데, 중간값이 찾고자 하는 target 값보다 큰 경우, middle과 end 사이의 값들은 탐색할 필요가 없기 때문에 그 부분을 탐색 범위에서 빼버리는 것이다.

파이썬 코드

재귀 함수 이용

def bin_search(arr, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    if arr[mid] == target:
        return mid
    elif arr[mid] > target:
        return bin_search(arr, target, start, mid-1)
    else:
        return bin_search(arr, target, mid+1, end)

반복문 이용

def bin_search(arr, target):
    start, end = 0, len(arr)-1
    while start <= end:
        mid = (start + end) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] > target:
            end = mid - 1
        else:
            start = mid + 1

트리 자료구조

트리 자료구조는 이진탐색과 비슷한 방식으로 자료를 탐색한다. 데이터가 많아도 탐색 속도가 빠르기 때문에 대부분의 파일 시스템이 트리 자료구조로 구성되어있다.
트리 자료구조는 노드와 간선으로 이루어져있다.

이진 탐색 트리

이진 탐색 트리란 이진 탐색이 동작 할 수 있도록 고안된 효율적 탐색이 가능한 자료구조이다. 이진 탐색 트리가 되기 위해서는 아래 조건을 만족해야 한다.

왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

위 그림과 같은 트리가 이진 탐색 트리이다.

이진 탐색 트리 탐색 방법

위 이진 탐색 의 원리와 비슷하게 이진 탐색 트리 또한 자료구조의 특성을 사용해 빠르게 탐색 할 수 있다.

예로, 위 사진에서 14를 찾는 과정을 살펴보자.

1. 탐색의 시작은 root 에서 시작한다. 50은 target 값 보다 크기 때문에 다음 탐색 노드는 왼쪽 자식이 된다.
2. 17은 target 값 보다 크다. 또다시 왼쪽 자식 노드로 이동한다.
3. 12는 target 값 보다 작다. 따라서 오른쪽 자식 노드로 이동한다.
4. target 값인 14를 찾았다. 탐색을 종료한다.

이진 트리 탐색을 사용자의 입력을 받아 구현하는 것은 많이 출제되지 않는 편이다.

이진탐색 문제

아래 문제들은 전형적인 이진탐색 문제들로, 파라메트릭 서치 유형의 문제이다. 파라메트릭 서치란 원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제에 주로 사용하는 기법으로, 최적화 문제를 결정 문제로 바꾸어 해결하는 기법이다.

백준-2805. 나무자르기
백준-1654. 랜선자르기
백준-2512. 예산