[ 이것이 코딩테스트다 ] 20일차

안영우·2021년 1월 22일

나동빈 코딩테스트

[ 이것이 취업을 위한 코딩 테스트다. with 파이썬 ]

목록 보기

20/39

✏️ 서론

어제는 정렬 알고리즘을 배웠고, 오늘은 순차탐색과 이진탐색에 대해서 배워보자.

✏️ 본론

리스트 내에서 데이터를 매우 빠르게 탐색하는 이진 탐색 알고리즘을 배우기 전,
가장 기본탐색방법인 순차 탐색에 대해 먼저 이해할 필요가 있다.
그럼, 순차탐색이 무엇인지부터 배워보자.

📍 순차탐색(sequential_search)

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

보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 주로 사용하는데, 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 찾을 수 있다는 장점이있다.
그러나, 코딩테스트에서는 시간을 무한정으로 주지 않는 경우가 많기 때문에 문제를 잘 보고 사용여부를 판단하면 되겠다.

순차 탐색은 이름처럼 순차로 데이터를 탐색한다는 의미이다.
리스트안에 데이터를 하나씩 방문하면서 내가 찾는 문자열과 동일한지 찾는 원리인데,
후에 count() 메소드를 이용할때에도 내부에서는 순차탐색이 사용된다.

코드는 다음과 같은데 어렵지 않다.

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

input_data = input().split()
n = int(input_data[0])
target = input_data[1]

array = input().split()

print(sequential_search(n, target, array))

순차 탐색은 데이터 정렬여부와 상관없이 가장 앞에있는 원소부터 하나씩 확인해야 하는점이 특징이다.
따라서, 데이터의 개수가 N개 일때, 최대 N번의 비교연산이 수행되므로 최악의 경우의 시간복잡도는 O(N)이 되겠다.

📍 이진탐색(binary_search)

오늘의 중요한 내용인 이진탐색을 살펴보자.
이진탐색은 배열 내부의 데이터가 정렬(sort)되어 있어야만 사용할 수 있는 알고리즘이다.

이진 탐색은 퀵 정렬(quick_sort)과 비슷하게 탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다.

이진 탐색은 위치를 나타내는 변수 3개(시작점, 끝점, 중간점)를 사용해서 함수를 만든다.
그래서, 찾으려는 데이터와 중간점(Middle)위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는게이진 탐색 과정이다.

자세한 설명내용은 나동빈강의를 참고하자.

이진탐색은 데이터를 한번 확인할때마다 원소의 개수가 절반씩 감소한다는 점에서 시간 복잡도가 O(logN)이다.

이진탐색을 구현하는 방법에는 2가지(재귀함수, 반복문)가 있는데, 코드는 다음과 같다.

# 재귀함수 호출
'''
10 7
1 3 5 7 9 11 13 15 17 19
'''
def binary_search_recursive(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_recursive(array, target, start, mid-1)
    else:
        return binary_search_recursive(array, target, mid+1, end)

n, target = list(map(int, input().split()))
array = list(map(int, input().split()))
result = binary_search_recursive(array, target, 0, n-1)

if result == None:
    print('찾는 값이 없습니다.')
else:
    print(result + 1)

👉🏽 출력
4

# for문
'''
10 7
1 3 5 7 9 11 13 15 17 19
'''
def binary_search_recursive(array, target, start, end):
    while start <= end:
        mid = (start + end) // 2

        if array[mid] == target:
            return mid
        elif array[mid] > target:
            return end = mid - 1
        else:
            return start = mid + 1
    return None
    
n, target = list(map(int, input().split()))
array = list(map(int, input().split()))
result = binary_search_recursive(array, target, 0, n-1)

if result == None:
    print('찾는 값이 없습니다.')
else:
    print(result + 1)

👉🏽 출력
4

⚡️ 코딩 테스트에서의 이진 탐색

코딩 테스트에서의 이진 탐색문제는 범위가 큰 상황에서 탐색을 가정하는 문제가 많다.
따라서, 탐색 범위가 20,000,000을 넘어가면 이진 탐색으로 문제에 접근해보길 권한다.

처리해야 할 데이터의 개수나 값이 10,000,000 이상으로 넘어가면 이진탐색과 같이 시간 복잡도가 O(logN)의 속도를 내야 하는 알고리즘을 떠올려야 문제를 풀 수 있는 경우가 많다는 점도 기억하자!

⚡️ bisect_range(이진탐색 라이브러리)

bisect_left(a,x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입 할 가장 왼쪽 인덱스를 반환
bisect_right(a,x): 정렬된 순서를 유지하면서 배열 a에 x를 삽입 할 가장 오른쪽 인덱스를 반환

# 값이 특정 범위에 속하는 데이터의 개수 구하기
from bisect import bisect_left, bisect_right

def count_range(array, left_value, right_value):
    right_index = bisect_right(array, right_value)
    left_index = bisect_left(array, left_value)
    return right_index - left_index

array = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]

print(count_range(array, 4, 4))
print(count_range(array, -1, 3))
👉🏽 2 6