이것이 코딩 테스트다 - Chapter7 이진 탐색 정리

"이진 탐색" 이란

탐색 범위를 반으로 좁혀가며 빠르게 탐색하는 알고리즘

 

앞서 정렬의 방법에 대해 알아보았다.

정렬은 사실 "탐색"을 쉽게 하기 위한 선과정에 속하기도 하다.

그 이유에 대해서는 조금뒤에 알아보겠다.

 

먼저 탐색에 대해 알아보겠다.

 

1. 순차 탐색

리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다.

이 방법은 구현하기 간단하며, 시간이 충분하다면 원하는 값을 찾을 수 있다.

def sequential_search(n, target, array) :
  for i in range(n) :
    if array[i] == target :
      return i+1

n개의 데이터를 앞에서부터 하나씩 확인하기 때문에 최대 n번 확인한다는 점이 특징이다

 

시간복잡도 : O(N)

 

하지만, 문제에서 찾는 범위가 10,000,000 이상을 넘어가는 경우엔 시간이 오래 걸리므로 다른방법이 필요하다.

이때 사용되는 탐색이 이진 탐색이다.

 

2. 이진 탐색

찾고자 하는 범위에서 중간값과 비교 후 작거나 큰 경우에 따라 범위를 반으로 축소하며 확인하는 방법이다.

이 방법을 사용하려면 리스트 대상, 범위의 시작점, 끝점, 그리고 찾으려는 데이터가 필요하다.

 

크게 재귀함수 구조와 반복문 구조가 있다.

 

1) 이진탐색 - 재귀함수

def binary_search(array, target, start, end) :
  if start > end :
    return None

  mid = (start+end)//2

  if target == array[mid] :
    return mid
  elif target < array[mid] :
    return binary_search(array, target, start, mid-1)
  else :
    return binary_search(array, target, mid+1, end)

종료조건은 start가 end보다 커지는 시점이며, 찾고자 하는 리스트에서 start, end 값을 토대로 중간값과 비교를 통해 범위를 축소하며 찾는다.

 

2) 이진탐색 - 반복문

def binary_search(array, target, start, end) :
  while start <= end :
    mid = (start+end)//2

    if target == array[mid] :
      return mid
    elif target < array[mid] :
      end = mid-1
    else :
      start = mid+1
  return None

역시 종료조건은 start가 end보다 커지는 시점이다. 재귀함수 구조와 마찬가지로 중간값과 비교를 통해 end, start 값을 조정하며 반복한다.

 

여기까지 배운 이진탐색은 리스트에서 빨리 찾는 방법으로 쓰이는 방법이다.

하지만 데이터가 훨씬 많아지는 경우에는 리스트로 저장하기가 힘들기에 "트리"라는 구조를 사용한다.

"트리 자료구조"를 사용하여 저장하면 데이터가 항상 정렬이 되어 있기 때문이다.

 

이때, 트리 자료구조에서 자료를 찾을 때 역시 이진 탐색 방법이 사용된다. 이를 "이진 탐색 트리"라고 부른다.

 

3. 이진 탐색 트리

트리는 두가지 조건에 따라 저장되기에 탐색 역시 조건에 따라 찾는다

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

 

따라서 찾으려는 값이 있으면 루트노드부터 값을 비교하며 작은 값인 경우 왼쪽 자식 노드로, 큰 값인 경우 오른쪽 자식 노드로 이동하며 찾는다.

 

 

이제 이진탐색을 활용한 문제를 몇가지 살펴보겠다.

 

N을 입력받은 후, N개의 서로다른 숫자를 입력받는다. 그 후, M을 입력받아 M개의 서로 다른 숫자를 입력받은 후, 각 숫자가 N개의 숫자 중에 일치하는 숫자가 있는지 여부를 yes, no로 출력한다.

 

첫번째 방법은 N개의 데이터를 정렬한 후, 이진탐색으로 찾는 방법이다.

def binary_search(array, target, start, end) :
  if start > end :
    return None

  mid = (start+end)//2
  if target == array[mid] :
    return mid
  elif target < array[mid] :
    return binary_search(array, target, start, mid-1)
  else :
    return binary_search(array, target, mid+1, end)

N = int(input())
data = list(map(int, input().split()))
data.sort()
M = int(input())
question = list(map(int, input().split()))

for i in question :
  if binary_search(data, i, 0, N-1) == None :
    print("no", end=" ")
  else :
    print("yes", end=" ")

 

두번째 방법으로, 입력되는 수가 정수이며 범위가 크지 않은 경우 계수정렬을 사용할 수 있다.

N = int(input())
array = [0]*1000001

for i in input().split() :
  array[int(i)] = 1

M = int(input())
question = list(map(int, input().split()))

for i in question :
  if array[i] == 1 :
    print("yes", end=" ")
  else :
    print("no", end=" ")

 

세번째 방법으로, 숫자가 있는지 여부만 고려하므로 set 함수를 사용할 수 있다.

N = int(input())
array = set(map(int, input().split()))

M = int(input())
question = list(map(int, input().split()))

for i in question :
  if i in array :
    print("yes", end=" ")
  else :
    print("no", end=" ")

 

또다른 문제를 하나 더 보겠다.

 

떡의 개수 N과 요청길이인 M을 입력받는다. 그리고 N개의 떡의 길이를 입력받는다. 이때, 높이 H의 칼로 떡을 자른 후 남은 떡의 길이의 합이 M이 되어야 할 때, H의 값을 구하여라.

 

이 문제는 이전 문제들의 이진 탐색방법과는 조금 다른 "파라메트릭 서치"에 관련된 탐색방법 문제이다.

"원하는 조건을 만족하는 가장 알맞은 값을 찾는 문제"에 주로 사용된다.

 

이때, 원하는 값은 "칼의 높이" 이므로, 시작점을 0, 끝점을 N개의 떡중 가장 긴 떡의 길이로 설정한 후

H를 (시작점+끝점)//2로 설정하여 떡의 길이합을 비교하며 이진탐색으로 점차 좁혀가면 된다.

def binary_search(array, target, start, end) :
  H = (start+end)//2
  sum = 0

  for i in array :
    if i > H :
      sum += (i-H)
  
  if target == sum :
    return H
  elif target < sum :
    return binary_search(array, target, H+1, end)
  else :
    return binary_search(array, target, start, H-1)

N, M = map(int, input().split())
data = list(map(int, input().split()))
data.sort()
print(binary_search(data, M, 0, data[N-1]))

 

이런식으로 이진 탐색이 사용된다.

 

깃허브 - github.com/CodingTestStudy/FreeDeveloper_Cote/tree/main/이진탐색

CodingTestStudy/FreeDeveloper_Cote