[Algorithm] 이진 탐색(binary search), 이진 탐색 트리 알고리즘과 예시

 

 

이번에는 이진 탐색에 대해 알아보겠습니다.

이진 탐색은 대체로 검색 범위가 어마어마하게 많을 경우 사용합니다.

시간을 절약(?) 하기 위해 사용하는 느낌인 것 같습니다.

 

이진 탐색보다는 일반적으로 순차 탐색을 했었는데,
리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법입니다.

하지만 이럴 경우 데이터가 많아지면 시간이 너무 오래 걸린다는 단점이 있어서 그럴 경우 이진 탐색을 사용합니다.

 

이 녀석도 알고리즘을 외워두면 조금 편하게 사용할 수 있습니다.

이제 이진 탐색에 대해 알아보도록 합시다.

 

 

---

 

1. 이진 탐색(binary search)

간단히 말해서 반으로 쪼개면서 탐색하는 알고리즘입니다.
배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있습니다.

변수 3개(시작점, 끝점, 중간점)를 사용하여 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교하여 원하는 데이터를 찾습니다.
단골 문제이므로 외워두도록 합시다.

처리할 데이터의 수가 1000만 단위 이상으로 넘어가면 이진탐색을 사용하는 것이 좋습니다.

 

이제 구현하는 두가지 방법을 알아보도록 하겠습니다.

우선 재귀함수로 구현하는 방법입니다.

 

# 재귀함수로 구현하기

def binary_search(array, target, start, end):
  if start > end:
    return None
  mid = (start + end) // 2

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

# n(원소의 개수)과 target(찾고자 하는 문자열)을 입력 받기
n, target = list(map(int, input().split()))
# 전체 원소 입력받기
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n-1)
if result == None:
  print('원소가 존재하지 않습니다.')
else:
  print('answer : ', result+1)

10 7

1 3 5 7 9 11 13 15 17 19

answer : 4

 

 

 

다음으로는 반복문으로 구현하는 방법 입니다.

 

# 반복문으로 구현하기

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

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

# n(원소의 개수)과 target(찾고자 하는 문자열)을 입력 받기
n, target = list(map(int, input().split()))
# 전체 원소 입력받기
array = list(map(int, input().split()))

result = binary_search(array, target, 0, n-1)
if result == None:
  print('원소가 존재하지 않습니다.')
else:
  print('answer : ', result+1)

10 7

1 3 5 7 9 11 13 15 17 19

answer : 4

 

---

 

2. 이진 탐색 트리(binary search tree)

이진 탐색과 같이 등장하는 이진 탐색 트리에 대해 알아보도록 하겠습니다.

이진탐색과 연결리스트(linked list)를 결합한 자료구조의 일종입니다. 

트리의 형식으로 되어 있다고 생각하면 됩니다.

트리가 있을때 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드가 성립해야지 이진 탐색 트리라고 할 수 있습니다.

 

 

이진 탐색 트리는 입력이 많을 수 있기 때문에 sys 라이브러리를 사용하길 권장합니다.

 

import sys

input_data = sys.stdin.readline().rstrip()

 

rstrip()를 꼭 넣어주도록 합시다.
소스코드에 readline()을 입력하면 줄 바꿈이 자동으로 입력되어 이를 제거해 주는 역할을 하는 것입니다.

 

 

 

이제 소스코드로 이진 탐색 트리를 알아봅시다.

 

 

 

▶ 부품 찾기

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

n = int(input())
array = list(map(int, input().split()))
array.sort()

m = int(input())
x = list(map(int, input().split()))

print('answer :', end=' ')
for i in x:
  result = binary_search(array, i, 0, n-1)
  if result != None:
    print('yes', end=' ')
  else:
    print('no', end=' ')

5

8 3 7 9 2

3

5 7 9

no yes yes

 

 

 

▶ 떡볶이의 떡 만들기

파라메트릭 서치 유형의 문제 : 최적화 문제를 결정 문제로 바꾸어 해결하는 기법으로, 원하는 조건에 가장 알맞은 값을 찾는 문제입니다.

 

n, m = map(int, input().split())
array = list(map(int, input().split()))

start = 0
end = (max(array))

result = 0
while (start<=end):
  total = 0
  mid = (start + end) // 2
  for x in array:
    if x > mid:
      total += (x-mid)
  
  if total < m :
    end = mid-1
  else:
    result = mid # 최대한 덜 잘랐을 때가 정답이므로, 여기에서 result 기록
    start = mid + 1

print('answer : ', result)

4 6

19 15 10 17

answer : 15