이진 탐색

탐색 범위를 반으로 줄여나가면서 데이터를 빠르게 탐색하는 탐색 기법이다.
이진 탐색은 배열 내부의 데이터가 정렬되어 있을 때만 사용할 수 있으며, 이진 탐색 알고리즘에서는 3가지 변수가 사용된다.(시작점, 끝점, 중간점)
시작점, 끝점은 탐색하고자 하는 범위를 나타내기 위해 사용하며, 탐색 범위의 중간점에 있는 데이터와 찾고자 하는 데이터를 비교한다.
ex) 0 ~ 9 중에서 데이터 2를 찾는 과정

 

bisect 클래스

단순히 정렬된 배열에서 특정한 데이터를 찾도록 요구하는 문제에서는 이진 탐색을 직접 구현할 필요 없이 단순히 파이썬의 표준 라이브러리 중에서 bisect 모듈을 사용할 수 도 있다.

• 이진 탐색(Binary Search) 기능을 제공하는 라이브러리이다.
• 정렬된 배열에서 특정한 원소를 찾아야 할 때 매우 효과적으로 사용된다.
• bisect_left(a, x) : 정렬된 순서를 유지하면서 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 메서드
• bisect_right(a, x) : 정렬된 순서를 유지하도록 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는 메서드

from bisect import bisect_left, bisect_right

a = [1,2,4,4,8]
x = 4

print(bisect_left(a,x))
print(bisect_right(a,x))

# 결과
# 2
# 4

count_by_range(a, left_value, right_value)

• 정렬된 리스트에서 값이 [left_value, right_value]에 속하는 데이터의 개수를 반환한다.
• 원소의 값이 x라고 할 때, left_value <= x <= right_value인 원소의 개수를 빅오(logN)으로 빠르게 계산할 수 있다.

from bisect import bisect_left, bisect_right

# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(a, left_value, right_value):
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    return right_index - left_index

# 리스트 선언 (정렬되어야 함)
a = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]

# 값이 4인 데이터 개수 출력
print(count_by_range(a,4,4))

# 값이 [-1, 3] 범위에 있는 데이터 개수 출력
print(count_by_range(a, -1, 3))

# 결과
# 2
# 6

 

문제

Q 27 정렬된 배열에서 특정 수의 개수 구하기

시간 복잡도 O(logN)으로 동작하는 알고리즘을 요구하고 있다.
일반적인 선형 탐색으로는 문제를 해결할 수 없다.
모든 원소가 정렬이 된 상태로 입력되므로, 이진 탐색을 이용하여 값이 x인 원소의 개수를 시간 O(logN)에 찾아 낼 수 있다.
x가 처음 등장하는 인덱스와 x가 마지막으로 등장하는 인덱스를 각각 계산한 뒤에, 그 인덱스의 차이를 계산하여 문제를 해결할 수 있다.
(1) 데이터가 존재한다면 가장 첫 번째 위치를 찾는 이진 탐색 메서드
(2) 데이터가 존재한다면 가장 마지막 위치를 찾는 이진 탐색 메서드
이 2개를 각각 실행한 뒤에 답을 도출할 수 있다.
(이진 탐색을 요구하는 고난이도 문제에서 자주 사용할 수 있는 테크닉으로, 이 문제에서 사용된 코드를 잘 이해하면 도움이 될 것이다.)
소스

# 정렬된 수열에서 값이 x인 원소의 개수를 세는 메서드
def count_by_value(array, x):
    # 데이터의 개수
    n = len(array)

    # x가 처음 등장한 인덱스 계산
    a = first(array, x, 0, n - 1)

    # 수열에 x가 존재하지 않는 경우
    if a == None:
        return 0  # 값이 x인 원소의 개수는 0개이므로 0 반환

    # x가 마지막으로 등장한 인덱스 계산
    b = last(array, x, 0, n - 1)

    # 개수를 반환
    return b - a + 1


# 처음 위치를 찾는 이진 탐색 메서드
def first(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    # 해당 값을 가지는 원소 중에서 가장 왼쪽에 있는 경우에만 인덱스 반환
    if (mid == 0 or target > array[mid - 1]) and array[mid] == target:
        return mid
    # 중간점의 값 보다 찾고자 하는 값이 작거나 같은 경우 왼쪽 확인
    elif array[mid] >= target:
        return first(array, target, start, mid - 1)
    # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인
    else:
        return first(array, target, mid + 1, end)


# 마지막 위치를 찾는 이진 탐색 메서드
def last(array, target, start, end):
    if start > end:
        return None
    mid = (start + end) // 2
    # 해당 값을 가지는 원소 중에서 가장 오른쪽에 있는 경우에만 인덱스 반환
    if (mid == n - 1 or target < array[mid + 1]) and array[mid] == target:
        return mid
    # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인
    elif array[mid] > target:
        return last(array, target, start, mid - 1)
    # 중간점의 값보다 찾고자 하는 값이 크거나 같은 경우 오른쪽 확인
    else:
        return last(array, target, mid + 1, end)


n, x = map(int, input().split())  # 데이터의 개수 N, 찾고자 하는 값 x를 입력받기
array = list(map(int, input().split()))  # 전체 데이터 입력받기

# 값이 x인 데이터의 개수 계산
count = count_by_value(array, x)

# 값이 x인 원소가 존재하지 않는다면
if count == 0:
    print(-1)
# 값이 x인 원소가 존재한다면
else:
    print(count)

 

정렬된 수열에서 특정한 값을 가지는 원소의 개수를 구하기
파이썬의 이진 탐색 라이브러리인 bisect을 적절히 활용하면 손쉽게 문제를 해결할 수 있다.
소스

from bisect import bisect_left, bisect_right


# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(a, left_value, right_value):
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)
    return right_index - left_index


n, x = map(int, input().split())  # 데이터의 개수 N, 찾고자 하는 값 x를 입력받기
list_array = list(map(int, input().split(' ')))  # 전체 데이터 입력받기

# 값이 [x, x] 범위에 있는 데이터의 개수 계산
count = count_by_range(list_array, x, x)

# 값이 x인 원소가 존재하지 않는다면
if count == 0:
    print(-1)
# 값이 x인 원소가 존재한다면
else:
    print(count)

 

Q 28 고정점 찾기

요구사항인 시간 복잡도 O(logN)으로 고정점을 찾으려면 선형 탐색으로는 조건에 맞게 (시간 제한에 맞게) 문제를 해결할 수 없다.
이진 탐색을 수행해서 빠르게 고정점을 찾아야 한다.
이미 배열이 정렬되어 있으므로 바로 이진 탐색을 적용할 수 있다.
이진 탐색을 수행할 때는 '찾고자 하는 값'이 '중간점'과 동일하다고 가정하고, 탐색을 수행하면 된다.

• 중간점이 가리키는 위치의 값보다 중간점이 작은 경우에는 왼쪽 부분을 탐색
• 중간점이 가리키는 위치의 값보다 중간점이 큰 경우에는 오른쪽 부분을 탐색
  하는 것을 반복하면 된다.
  소스

# 이진 탐색 소스코드 구현(재귀 함수)
def binary_search(array, start, end):
	if start > end:
		return None
	mid = (start + end) // 2
	# 고정점을 찾은 경우 인덱스 반환
	if array[mid] == mid:
		return mid
	# 중간점이 가라키는 위치의 값보다 중간점이 작은 경우 왼쪽 확인
	elif array[mid] > mid:
		return binary_search(array, start, mid - 1)
	# 중간점이 가라키는 위치의 값보다 중간점이 큰 경우 오른쪽 확인
	else:
		return binary_search(array, mid + 1, end)
	
n = int(input())
array = list(map(int, input().split()))

# 이진 탐색(Binary Search) 수행
index = binary_search(array, 0, n - 1)

# 고정점이 없는 경우 -1 출력
if index == None:
	print(-1)
# 고정점이 있는 경우 해당 인덱스 출력
else:
	print(index)

 

Q 29 공유기 설치

'가장 인접한 두 공유기 사이의 거리'의 최댓값을 탐색해야 하는 문제로 이해할 수 있다.
이진 탐색으로 '가장 인접한 두 공유기 사이의 거리'를 조절해가며, 매 순간 실제로 공유기를 설치하여 C보다 많은 개수로 공유기를 설치할 수 있는지 체크하여 문제를 해결할 수 있다.
'가장 인접한 두 공유기 사이의 거리'의 최댓값을 찾아야 하므로, C보다 많은 개수로 공유기를 설치할 수 있다면 '가장 인접한 두 공유기 사이의 거리'의 값을 증가시켜서, 더 큰 값에 대해서도 성립하는지 체크하기 위해 다시 탐색을 수행한다.
파라메트릭 서치 문제이지만, 다소 헷갈린다.

공유기 간력 : mid
최소 범위 : left
최대 범위 : right
left : position[1] - position[0]
right : position[n - 1] - position[0]
가운데 값 mid를 공유기의 간격으로 가정 후, 처음 집부터 설치를 진행한다.
position[0] 설치 후, mid : 4만큼 뒤의 값인 좌표가 5인 곳의 설치를 한다.
하지만, 좌표가 5인 곳은 집이 없으므로 5 바로 뒤에 있는, 좌표 8인 곳에 설치한다.
공유기 2개 밖에 설치를 못했기에, 공유기 간격 범위를 좁혀준다.
(중간점이 가리키는 위치의 값보다 중간점이 작은 경우에는 왼쪽 부분을 탐색)
(중간점이 가리키는 위치의 값보다 중간점이 큰 경우에는 오른쪽 부분을 탐색)

공유기 간격 범위를 좁혀 주기 위해서 right = mid - 1로 범위를 좁혀주어 탐색한다.
범위를 좁혀주는 과정이 이진 탐색 과정과 유사하다.
따라서 시간 복잡도는 O(logN)으로 탐색할 수 있다.
right의 범위가 좁혀졋으니, mid 값은 1 ~ 3 중간에 있는 2가 된다.
다시 mid = 2로 집의 설치를 진행한다.

• 좌표 1인 집의 설치 후, 좌표 3의 설치를 해야하지만, 없으므로 좌표 4의 설치를 한다.
• 좌표 6의 설치 해야하는데, 집이 없으므로 8의 설치를 진행한다.
• 공유기를 원하는 개수 3개만큼 설치 완료

하지만, 아직 mid가 2 ~ 4 사이에 있는 3의 값을 탐색하지 않았다.
문제는 최적화를 구해야 하므로, 가장 인접한 공유기 간격의 최대값으로, 3 또한 탐색을 실시한다.

left = mid + 1로 범위를 좁혀준다.
mid는 3이 되고, 집의 설치를 진행하면 좌표 1, 좌표 4, 좌표 8의 설치 할 수 있다.
더 이상 탐색할 수 있는 범위가 없으므로 mid 값 3을 반환한다.

소스

# 집의 개수(N)와 공유기 개수(C)를 입력받기
n, c = list(map(int, input().split(' ')))

# 전체 집의 좌표 정보를 입력받기
array = []

for _ in range(n):
    array.append(int(input()))
array.sort()  # 이진 탐색 수행을 위해 정렬 수행

start = array[1] - array[0]  # 집의 좌표 중에 가장 작은 값
end = array[-1] - array[0]  # 집의 좌표 중에 가장 큰 값
result = 0

while (start <= end):
    mid = (start + end) // 2  # mid는 가장 인접한 두 공유기 사이의 거리(gap)을 의미
    value = array[0]
    count = 1
    # 현재의 mid값을 이용해 공유기를 설치
    for i in range(1, n):  # 앞에서부터 차근차근 설치
        if array[i] >= value + mid:
            value = array[i]
            count += 1
    if count >= c:  # C개 이상의 공유기를 설치할 수 있는 경우, 거리를 증가
        start = mid + 1
        result = mid  # 최적의 결과를 저장
    else:  # C개 이상의 공유기를 설치할 수 없는 경우, 거리를 감소
        end = mid - 1

print(result)

 

Q 30 가사 검색

[문제 풀이 이해]

• 이 문제는 이진 탐색을 이용해서 간결하게 해결할 수 있다.

• 각 단어를 길이를 길이에 따라 나눈다.

• 이후에 모든 리스트를 정렬한 뒤에, 각 쿼리에 대해서 이진 탐색을 수행하여 문제를 해결할 수 있다.

 

ex)

단어 : ['frodo', 'front', 'frost', 'frozen', 'frame', 'kakao']로 구성되어 있을 때

길이가 5인 단어 리스트 : ['frodo', 'front', 'frost', 'frame', 'kakao']

길이가 6인 단어 리스트 : ['frozen']

이를 각각 정렬한다.

길이가 5인 단어 리스트 : ['frame', 'frodo', 'front', 'frost', 'kakao']

길이가 6인 단어 리스트 : ['frozen']

 

방법 1)

'fro??'라는 쿼리가 들어왔다고 가정하면 'fro??'는 길이가 5이므로 길이가 5인 단어 리스트에서 'fro'로 시작되는 모든 단어를 찾으면 된다.

이때 구체적으로 이진 탐색을 이용해서 'fro'로 시작되는 마지막 단어의 위치를 찾고, 'fro'로 시작되는 첫 단어의 위치를 찾아서 그 위치의 차이를 계산하면 된다.

이처럼 이진 탐색을 수행하는 경우 특정한 단어가 등장한 횟수를 계산할 수 있다.

방법 2)

(1) 접미사에 와일드카드가 붙은 경우

'fro??'라는 쿼리가 들어왔을 때, count_by_range() 메서드를 이용하여 'froaa'보다 크거나 같으면서 'frozz'보다 작거나 같은 단어의 개수를 세도록 구현하면 매우 간단하다.

• array

(2) 접두사에 와일드카드가 붙은 경우

'????o'라는 쿼리가 들어왔을 때, 기존 단어를 뒤집어 담고 있는 리스트 또한 별도로 선언해야한다.

('frame', 'frodo', 'kakao') -> ('emarf', 'odorf', 'oakak')

'oaaaa'보다 크거나 같으면서 'ozzzz'보다 작거나 같은 단어의 개수를 세도록 구현하면 매우 간단하다.

• reversed_array

소스

from bisect import bisect_left, bisect_right

# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(a, left_value, right_value):
    right_index = bisect_right(a, right_value)
    left_index = bisect_left(a, left_value)

    # print("a : ", a , "left : ", left_index , " right : ",right_index)
    return right_index - left_index

# 모든 단어를 길이마다 나누어서 저장하기 위한 리스트
array = [[] for _ in range(10001)]
# 모든 단어를 길이마다 나누어서 뒤집어 저장하기 위한 리스트
reversed_array = [[] for _ in range(10001)]

def solution(words, queries):
    answer = []
    for word in words: # 모든 단어를 접미사 와일드카드 배열, 접두사 와일드카드 배열에 각각 삽입
        array[len(word)].append(word) # 단어를 삽입
        reversed_array[len(word)].append(word[::-1]) # 단어를 뒤집어서 삽입

    for i in range(10001): # 이진 탐색을 수행하기 위해 각 단어 리스트 정렬 수행
        array[i].sort()
        reversed_array[i].sort()

    # print("정렬된 결과")
    # print("array : ", array)
    # print("reversed : ", reversed_array)
    for q in queries: # 쿼리를 하나씩 확인하며 처리
        if q[0] != '?': # 접미사에 와일드카드가 붙은 경우
            # print(q, end = ' ')
            # print(q.replace('?','a'), q.replace('?', 'z'))
            res = count_by_range(array[len(q)], q.replace('?', 'a'), q.replace('?','z'))
        else: # 접두사에 와일드카드가 붙은 경우
            # print(q, end = ' ')
            # print(q[::-1].replace('?','a'), q[::-1].replace('?', 'z'))
            res = count_by_range(reversed_array[len(q)], q[::-1].replace('?','a'), q[::-1].replace('?','z'))
        # 검색된 단어의 개수를 저장
        answer.append(res)
    return answer

word = ["frodo","front","frost","frozen","frame","kakao"]
queries = ["fro??","????o","fr???","fro???","pro?"]

print(solution(word,queries))

 

---

참고 자료

• https://coding-food-court.tistory.com/107