이진 탐색(Binary Search)

김소정·2023년 4월 5일
algorithm
0

Algorithm

목록 보기
3/3
post-thumbnail

이진 탐색은 리스트 내에서 데이터를 매우 빠르게 탐색하게 돕는 알고리즘이다. 선형 탐색(또는 순차 탐색)의 경우 특정 데이터를 찾기 위해 리스트의 맨 앞에서부터 하나씩 확인하는 반면에, 이진 탐색은 범위를 절반씩 좁혀가며 탐색하기에 시간 측면에서 효율적이다.

선형 탐색

앞서 이야기 했듯이, 선형 탐색은 리스트의 처음부터 순차적으로 확인 및 비교하며 특정 데이터를 찾아가는 방식이다. 구현이 간단하며, 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 유용하다. 하지만 데이터의 양에 비례하여 탐색에 소요되는 시간이 길어지기 때문에 비효율적이다.

데이터의 개수가 NN개일 때 최대 NN번의 비교 연산이 필요하므로 최악의 경우(리스트의 마지막 원소가 찾는 값이었던 경우), 순차 탐색의 시간 복잡도는 O(N)O(N)이다.

Example

예를 들어 다음과 같은 이름 리스트가 존재할 때, 리스트 내 혜윤(hyeyoon)의 위치를 찾고 싶다고 하자.

name = ['sojeong', 'dongwoo', 'sangjun', 'hyeyoon', 'dayeon']

선형 탐색을 이용하게 되면 리스트의 첫 번째(index 0) 원소부터 차례대로 확인하고, target 값과 동일한 값을 찾으면 우리가 원하는 값의 위치를 반환해야 한다.

def sequential_search(n, target, array):
    for i in range(n):
        if array[i] == target:
            return i + 1
        
print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요.")
input_data = input().split()
n = int(input_data[0]) # 원소의 개수
target = input_data[1] # 찾고자 하는 문자열

print("앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.")
array = input().split()

print(sequential_search(n, target, array))
  1. 입력값
    a. n = 원소 개수
    b. target: 찾고자 하는 문자열
    c. array: 배열 정의
  2. for문을 활용하여 0부터 n-1의 인덱스까지 탐색
  3. 현재의 원소가 찾고자 하는 원소와 동일한 경우
  4. 현재의 위치 반환

이진 탐색

이진 탐색은 배열 내부의 데이터가 정렬되어 있을 때만 사용할 수 있다. 배열 내 데이터가 무작위인 경우는 사용할 수 없지만, 정렬되어 있는 배열에 한해서는 빠른 탐색 속도를 보여준다.

이진 탐색에는 위치를 나타내는 변수 세 개, 시작점, 끝점, 그리고 중간점이 사용된다. 찾으려는 데이터와 중간점(mid)를 반복적으로 비교하여 원하는 데이터를 찾는다.

Example

예를 들어, 다음과 같은 배열이 있다고 할 때 우리는 배열 내 15의 위치를 찾고자 한다.

그러면 시작점은 [0], 끝점은 [9], 중간점은 0과 9의 중간(4.5에서 소수점 이하를 버림)인 인덱스 [4]인 9이다.

중간점에 위치한 9는 우리가 찾고자 하는 데이터 15보다 작은 값이므로 값이 9 이하인 데이터, 즉 인덱스가 4 이하인 데이터는 살펴볼 필요가 없다. 따라서 시작점을 mid+1mid+1, 인덱스 5로 변경해준다.

그러면 시작점은 [5], 끝점은 [9], 중간점은 5와 9의 중간인 [7]이 된다.

이 때의 중간점은 우리가 찾으려는 데이터 15와 동일하므로, 탐색이 종료된다.

해당 배열에서 선형 탐색을 이용했다면, 8번의 탐색 끝에 원소 15를 찾을 수 있었을 것이다. 반면에 위에서 확인할 수 있었듯이, 이진 탐색을 통해서 2번의 탐색만으로 해당 값을 찾을 수 있었다.

이진 탐색은 탐색을 한 번 시행할 때마다 확인해야 할 원소의 수가 절반으로 줄어든다. 따라서 NN개의 원소가 있을 때, 시간 복잡도는 O(log⁡2N)O(\log_{2}{N})이 된다. 간단하게 O(log⁡N)O(\log{N})로 표기하기도 한다.

이진 탐색을 구현하는 방법에는 크게 두가지가 있다. 재귀 함수를 이용할 수도 있고, 단순하게 반복문을 이용할 수도 있다.

재귀 함수

어떤 사건이 자신을 포함하고 다시 자기 자신을 사용하여 정의될 때 재귀적(recursive)이라고 한다. 일단 무언가를 설명할 때 자기를 포함한 것이라고 이해하면 편하다.

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 = 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(result + 1)

반복문

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 = 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(result + 1)

cf. 트리 자료구조

데이터베이스는 내부적으로 대용량 데이터 처리에 적합한 트리 자료구조를 이용하여 데이터가 정렬되어있다. 따라서 이진 탐색과 동일하진 않지만, 유사한 방식으로 탐색을 빠르게 수행하도록 설계되어있다.

트리 자료구조는 그래프 자료구조의 일종으로 많은 양의 데이터를 관리하기 위한 목적으로 주로 사용된다, 노드와 노드 간의 연결로 표현할 수 있다. 노드는 정보의 단위로 어떠한 정보를 가지고 있다.

특징

  • 트리는 부모 노드와 자식 노드의 관계로 표현된다.
  • 트리의 최상단 노드를 루트 노드라고 한다.
  • 트리의 최하단 노드를 단말 노드라고 한다.
  • 트리에서 일부를 떼어내도 트리 구조이며 이를 서브 트리라 한다.
  • 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합하다.

이진 탐색 트리

트리 자료구조 중 가장 간단한 형태는 이진 탐색 트리이다. 이진 탐색 트리는 이진 탐색이 동작할 수 있도록 고안된 자료구조로, 이진 트리의 일종이기도 하다.

모든 트리가 이진 탐색 트리는 아니며, 다음과 같은 조건을 만족해야 한다.

a. 한 노드당 최대 두 개의 자식 노드를 가질 수 있다.
b. 부모 노드보다 왼쪽 자식 노드가 작으며, 오른쪽 자식 노드가 크다. (왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드)

ex. 부모 노드 25, 왼쪽 자식 노드 16, 오른쪽 자식 노드 33

이진 탐색은 다음과 같은 과정으로 조회하고자 하는 데이터를 찾는다.

  1. 부모 노드와 찾는 원소값 비교 (부모 노드 = 찾는 값 ➡️ 탐색 종료)
  2. 찾는 값이 부모 노드보다 작다면, 왼쪽 자식 노드와 비교
    찾는 값이 부모 노드보다 크다면, 오른쪽 자식 노드와 비교
  3. 위 과정 반복

문제

1) 부품 찾기

동빈이네 전자 매장에는 부품이 N개 있다. 각 부품은 정수 형태의 고유한 번호가 있다. 어느 날 손님이 M개 종류의 부품을 대량으로 구매하겠다며 당일 날 견적서를 요청했다. 동빈이는 때를 놓치지 않고 손님이 문의한 부품 M개 종류를 모두 확인해서 견적서를 작성해야 한다. 이 때 가게 안에 부품이 모두 있는지 확인하는 프로그램을 작성해보자.

입력

  • 첫째 줄에 정수 N이 주어진다. (1 ≤ N ≤ 1,000,000)
  • 둘째 줄에는 공백으로 구분하여 N개의 정수가 주어진다. 이 때 정수는 1보다 크고 1,000,000 이하이다.
  • 셋째 줄에는 정수 M이 주어진다. (1 ≤ M ≤ 100,000)
  • 넷째 줄에는 공백으로 구분하여 M개의 정수가 주어진다. 이 때 정수는 1보다 크고 1,000,000 이하이다.

출력

첫째 줄에 공백으로 구분하여 각 부품이 존재하면 yes를, 없으면 no를 출력한다.

풀이

해당 문제는 다양한 방법으로 풀이할 수 있다.

  1. 이진 탐색
    하지만 이진 탐색을 활용하게 되면 N개의 부품을 정렬하는 과정에서 O(N×log⁡N)O(N \times \log{N})의 연산, M개의 부품을 찾는 과정에서 O(M×log⁡N)O(M \times \log{N})의 연산이 필요하기에, 최종 시간 복잡도는 O((N+M)×log⁡N)O((N+M) \times \log{N})이다.

    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()))

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

  2. 계수 정렬
    모든 원소의 번호를 포함할 수 있는 크기의 리스트를 만들고, 리스트의 인덱스에 직접 접근하여 특정한 번호의 부품이 매장에 존재하는지 확인할 수 있다.

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

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

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

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

  3. 집합 자료형
    이 문제는 특정 수가 한 번이라도 등장했는지를 확인하면 되므로, 집합 자료형을 이용해서 풀 수도 있다. 집합 자료형 set()은 중복값을 갖지 않으므로, 특정 데이터의 존재 여부를 확인할 때 매우 유용하다.

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

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

for i in x:
    if i in array:
        print('yes', end=' ')
    else:
        print('no', end=' ')

2) 떡볶이 떡 만들기

동빈이네 떡볶이 떡은 떡볶이 떡의 길이가 일정하지 않다. 대신에 한 봉지 안에 들어가는 떡의 총 길이는 절단기로 잘라서 맞춘다. 절단기에 높이(HH)를 지정하면 줄 지어진 떡을 한 번에 절단한다. 높이가 HH보다 긴 떡은 HH 위의 부분이 잘릴 것이고, 낮은 떡은 잘리지 않는다.

예를 들어 높이가 19, 14, 10, 17cm이 떡이 나란히 있고 절단기 높이를 15cm로 지정하면 자른 뒤 떡의 높이는 15, 14, 10, 15cm가 될 것이다. 잘린 떡의 길이는 4, 0, 0, 2cm이고, 손님은 6cm만큼의 길이를 가져간다.

손님이 왔을 때 요청한 총 길이가 M일 때 적어도 M만큼의 떡을 얻기 위해 절단기에 설정할 수 있는 높이의 최댓값을 구하는 프로그램을 작성하시오.

입력

  • 첫째 줄에 떡의 개수 N(1 ≤ N ≤ 1,000,000)과 요청한 떡의 길이 M(1 ≤ M ≤ 2,000,000,000)이 주어진다.
  • 둘째 줄에는 떡의 개별 높이가 주어진다. 떡 높이의 총합은 항상 M 이상이다. 높이는 10억보다 작거나 같은 양의 정수 또는 0이다.

출력

적어도 M만큼의 떡을 집에 가져가기 위해 절단기에 설정할 수 있는 높이의 최댓값을 출력한다.

풀이

최적화 문제를 결정 문제로 바꾸어 해결하는 Parametric Search 유형의 문제이다. 해당 문제는 적절한 높이를 찾을 때까지 절단기의 높이 H를 반복해서 조정하면 된다.

  1. 시작점을 0, 끝점을 가장 긴 떡의 길이로 설정한다.
  2. 중간점을 절단기의 높이 H로 설정했을 때, 얻을 수 있는 떡의 길이를 계산한다.
    a. 얻을 수 있는 떡의 길이가 M보다 크면 시작점을 mid+1로 설정해준다.
    b. 얻을 수 있는 떡의 길이가 M보다 작으면 끝점을 mid-1로 설정해준다.
  3. 얻을 수 있는 떡의 길이를 계산했을 때 M과 같은 값이 도출되면, 그 때의 중간점(mid)이 H이다.

시간이 지날수록 최적의 값을 찾는 것이 특징이기에, 과정을 반복하며 결괏값을 중간점 값으로 갱신해주면 된다. 이와 같은 Parametric Search에서는 이진 탐색을 재귀적으로 구현하는 것보다 반복문을 이용하는 것이 효율적이다.

코드

n, m = list(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
        start = mid + 1
                
print(result)

Reference

나동빈, 『이것이 취업을 위한 코딩 테스트다 with 파이썬』, 한빛미디어(2020)

profile
김소정
Yonsei University, Applied Statistics
이전 포스트

탐욕 알고리즘(Greedy Algorithm)

0개의 댓글