탐색(Search)

개요

---

탐색 알고리즘은 크게 2가지로 나눌수 있는데 선형 탐색(Linear Search)와 이진 탐색 (Binary Search) 이다. 앞서 구현에서 설명한 완전 탐색을 이용하여 탐색하는 방법도 있겠지만, 탐색할 데이터의 범위가 기하급수적으로 늘어난다면 완전탐색만으로 문제를 풀이하기에는 적합하지 않을 수 있다.

이를 위해 다양한 테크닉을 이용할 수 있는데 종류는 다음과 같다.

종류

---

순차 탐색

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 찾는 방법.
이름 그대로 앞에서부터 순차적으로 데이터를 탐색해 나가므로, 데이터의 개수가 $N$ 이라고 할 때, 순차 탐색의 시간복잡도는 아래와 같다 $O(N)$

lst = [1, 3, 5, 12, 34, 90]
target = 12
idx = -1
for x, i in enumerate(lst):
	if i == target:
    	idx = x
        break
print(target if target >= 0 else "None")

---

이진 탐색

이진 탐색은 탐색범위를 절반씩 줄여가며 탐색하는 방식이다. 위치를 나타내는 변수 3개를 사용하는데 탐색 시작점, 탐색 끝점, 탐색 중간점을 먼저 찾은 뒤, 찾으려는 데이터와 중간점 위치의 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 방식이다.

이진 탐색을 하기 위해서는 데이터가 정렬되어있어야 한다.

이진 탐색은 탐색마다 범위가 절반씩 줄어든다는 점에서 시간복잡도가 $O(\log N)$이다.
이진 탐색은 구현에 따라 재귀 적인 방법과 반복을 이용한 방법을 사용할 수 있다.
코딩테스트를 준비하면서 이진 탐색의 경우 출제빈도가 높고, 난이도가 높은 경우 이진 탐색과 다른 알고리즘의 결합을 이용하여 문제가 출제될 수 있다.

존 벤틀리에 따르면 이진 탐색을 제대로 구현하는 프로그래머는 10% 이내라고 하듯이 구현은 까다로운데 많은 문제를 풀어보면서 익숙해질 필요가 있다.

이진 탐색을 풀이해보며 느낀점은 실버 정도 난이도의 경우 아래 알고리즘과 주로 결합된다.

• 두 포인터 : 기본적으로 느낌이 비슷하다.
• 매개 변수 탐색 : 아래에 설명
• 슬라이딩 윈도우 : 창문이 슬라이드 되듯이 일정한 범위를 탐색하는 방법.

골드 정도 되는 문제에 매개 변수 탐색 또는 이진 탐색 정도의 카테고리를 가진 문제의 경우 탐색 범위를 지정하는것이 상당히 어렵다.

구현 소스 코드는 아래와 같다 (반복 이용)

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

파이썬에서 이진탐색을 라이브러리를 이용하여 구현할 수도 있는데, 바로 bisect 이다.

함수	설명
bisect.bisect_left(target, x)	target 리스트에서 x가 들어갈 가장 왼쪽의 인덱스를 탐색
bisect.bisect_right(target, x)	target 리스트에서 x가 들어갈 가장 오른쪽의 인덱스를 탐색

응용을 하면 아래와 같이 사용할 수 있다.

1. k 보다 크거나 같은 원소의 개수.

len(li) - bisect.bisect_right(li, x-1)

2. k 보다 큰 원소의 개수.

len(li) - bisect.bisect_right(li, x)

3. i와 j 사이의 원소의 개수.

bisect.bisect_right(li, y) - bisect.bisect_left(li, x)

---

매개변수 탐색

최적화 문제를 결정문제로 바꾸어 해결하는 기법.

이름은 다르지만 이진 탐색을 기반으로 하고 있다.
이진 탐색의 경우 탐색의 조건이 내가 찾는 수가 있느냐 이지만, 매개변수 탐색의 경우 또다른 조건에 의해 탐색 범위를 나눈다. 단순 응용이므로 코드 설명보다는 아래 문제를 해설하며 매개변수 탐색에 대해 정리한다.

입국심사 - 3079

• 최적화 문제를 결정문제로 바꾼다 라는 가장 기초적인 개념에서부터 아이디어를 구상하였다.
• start는 0으로, end는 모든 사람이 가장 오래걸리는 창구로 가는 m∗max(lst) 두고 풀기로 결정하였다.
• 이분탐색을 진행하여 mid를 모든 리스트 요소들로 나눈뒤 그 합을 구해 mid시간동안 창구를 이용할 수 있는 사람의 수를 구한다.
• 만약 매개 변수 탐색에서 사람의 수가 m보다 많거나 같으면 end를 줄이고 그 반대라면 start를 올린다.

import sys
input = sys.stdin.readline
n, m = map(int, input().split())
lst = [int(input())for _ in range(n)]
lst.sort()
start, end = 0, max(lst)*m
result = end
while start <= end:
    mid = (start + end) // 2
    if (sum(list(map(lambda x: mid // x, lst)))) >= m:
        end = mid - 1
        result = min(result, mid)
    else:
        start = mid + 1
print(result)

여기서 이분탐색과 다른점은 아래 코드이다

if (sum(list(map(lambda x: mid // x, lst)))) >= m:

해당 부분은 람다식을 이용하여 조건에 맞는 경우 탐색 범위를 낮추고 있다.

매개 변수 탐색과 이분탐색은 거의 붙어있지만 종종 아닌 경우도 있으니 문제에 따라 다른 풀이 전략을 사용하는것이 중요하다.

이진 탐색 트리

⚠🛑 공부중 🛑⚠