코딩테스트 [킬링캠프]

2.5 이진 탐색 (Binary Search)

zozni 2024. 1. 3. 19:14

728x90

SMALL

탐색 알고리즘(Search Algorithm)

탐색 알고리즘(Search Algorithm)이란 주어진 데이터 안에서 원하는 값을 찾는 알고리즘을 말합니다. 간단한 예시를 들자면, 만약 다음과 같이 나열된 숫자가 주어졌습니다.

[2, 93, -2, 0, 84, 2039]

이 상황에서 어떻게 0을 찾을 것인지에 대한 방법론을 만드는 것이 저희의 목표이고, 그러한 방법을 모두 일컬어 탐색 알고리즘이라고 부릅니다. 종류로는 선형 탐색(Linear Search), 이진 탐색(Binary Search), DFS 또는 BFS가 해당하는 비선형 탐색(Non-linear Search)이 있습니다. 그중 이번에 살펴볼 탐색 알고리즘은 코딩 테스트에서 자주 사용되는 이진 탐색입니다.

이진 탐색(Binary Search)

이진탐색.m4v

이진 탐색(Binary Search)는 정렬된 데이터를 담은 리스트에서 원하는 값의 위치를 찾는 알고리즘입니다. 여기서 가장 주목해야 하는 단어는 바로 정렬입니다. 오름차순 혹은 내림차순 모두 상관없습니다. 다만 정렬되어 있지 않은 리스트에 대해서 이진 탐색 알고리즘을 적용하면 아무런 쓸모가 없습니다. 반드시 알고리즘 사용 전에는 데이터를 정렬을 해야한다는 전제조건이 있습니다.

이진 탐색 알고리즘 순서

그 이후 알고리즘 진행 순서는 다음과 같습니다.

리스트의 중간값을 선택한다.
중간값과 원하는 값을 비교한다.
1. 중간값이 원하는 값인 경우
  - 알고리즘을 종료한다.
2. 중간값이 원하는 값과 다른 경우
  - 중간값보다 원하는 값이 큰 경우 (중간값 < 원하는 값)
  - : 중간값보다 큰 값들의 집합을 새로운 탐색 영역으로 설정한다.
  - 중간값보다 원하는 값이 작은 경우 (중간값 > 원하는 값)
  - : 중간값보다 작은 값들의 집합을 새로운 탐색 영역으로 설정한다.
새로운 탐색 영역의 중간값을 선택하고, 2번 과정으로 넘어가서 반복한다.

이진 탐색 알고리즘 구현

이진 탐색 알고리즘은 (1)반복문과 (2)재귀, 총 2가지 방식으로 구현할 수 있습니다. 각 방식에 따른 구현 코드는 다음과 같습니다. 다시 한번 강조하자면, 아래의 코드는 주어진 리스트가 오름차순 정렬되었다는 가정을 내포하고 있습니다. 다음과 같은 상황이 주어졌다는 가정을 두고 구현된 2가지 코드를 보여드리겠습니다.

n = [38102, 4, 7, 2, 0, 18, 2098, 582]
target = 18

이진 탐색 알고리즘 - 반복문

def bin_search(nums, target):
    nums.sort()
    print(f"Sorted List : {nums}")
    l, r = 0, len(nums) - 1
    while l <= r:
        mid = (l + r) // 2  # // 사용!
        print(f"Current Mid : {nums[mid]}")
        if target > nums[mid]:
            l = mid + 1
        elif target < nums[mid]:
            r = mid - 1
        else:
            print("Found!")
            return
    print("No target in the list")
    return

nums = [2, 6, 9, 14, 15, 17, 19, 22, 25, 26, 37, 45, 58, 67, 82]
bin_search(nums, 58)

결과
Sorted List : [2, 6, 9, 14, 15, 17, 19, 22, 25, 26, 37, 45, 58, 67, 82] Current Mid : 22 Current Mid : 45 Current Mid : 67 Current Mid : 58 Found!

이진 탐색 알고리즘 - 재귀

def bin_search(nums, target, l, r):
    if l > r:
        print("No target in the list")
        return
    mid = (l + r) // 2  # // 사용!
    print(f"Current Mid : {nums[mid]}")
    if target > nums[mid]:
        bin_search(nums, target, mid + 1, r)
    elif target < nums[mid]:
        bin_search(nums, target, l, mid - 1)
    else:
        print("Found!")
        return

nums = [2, 6, 9, 14, 15, 17, 19, 22, 25, 26, 37, 45, 58, 67, 82]
nums.sort()
print(f"Sorted List : {nums}")
bin_search(nums, 58, 0, len(nums) - 1)

결과
Sorted List : [2, 6, 9, 14, 15, 17, 19, 22, 25, 26, 37, 45, 58, 67, 82] Current Mid : 22 Current Mid : 45 Current Mid : 67 Current Mid : 58 Found!

이진 탐색 알고리즘 시간복잡도

이진 탐색은 새로운 탐색 영역을 기존 탐색 영역의 $1/2$로 나누는 것을 반복하여 원하는 값을 찾습니다. 분할 정복(Divide-and-Conquer)의 방식을 갖고 있으며, 시간복잡도는 $O(\mathrm{log}\,n)$ 입니다. 순수 이진 탐색 알고리즘의 시간복잡도가 $O(\mathrm{log}\,n)$일 뿐, 데이터 정렬에 대한 시간 복잡도는 계산되지 않았다는 점을 유의하시기를 바랍니다.

만약 문제에서 이미 정렬된 리스트를 제공한다면 이진 탐색의 시간 복잡도 $O(\mathrm{log}\,n)$만 소요되지만, 정렬을 우리가 직접 해야한다면 $O(n\mathrm{log}\,n)$의 시간 복잡도가 걸리는 정렬을 하고 난 후 $O(\mathrm{log}\,n)$이 소요되는 이진탐색을 하기 때문에 결과적으로 $O(n\mathrm{log}\,n)$의 시간이 걸리게 될 것입니다.

코딩테스트 활용

bisect

파이썬에서는 bisect 라이브러리를 사용해서 이진 탐색 알고리즘을 구현할 필요 없이 사용할 수 있습니다. 서로 기능이 매우 유사한 2가지 함수, bisect_left() 그리고 bisect_right() (또는 bisect())을 설명하겠습니다. 이 함수들도 주어진 리스트의 정렬 순서를 유지한 상태로 원하는 값의 위치 혹은 (새로운 값이라면) 삽입 위치를 반환하기 때문에, 실질적인 이진 탐색을 수행하고 싶다면, 정렬이 선행되어야 합니다.

우선 bisect 라이브러리를 불러옵니다.

import bisect

# 바로 함수 이름만 사용하고 싶다면,
# from bisect import bisect_left, bisect_right, bisect

bisect_left()

원하는 값이 해당 리스트에 존재한다면, 해당 값의 가장 왼쪽 인덱스를 반환합니다. 주어진 값이 리스트에 존재하지 않는 값이라면, 리스트에 삽입할 위치 인덱스를 반환합니다. 탐색 범위를 lo , hi 매개변수를 통해 설정할 수 있지만, 기본값으로 전체 리스트를 탐색 영역으로 설정합니다.

사용 형식 : bisect_left([list], [value], lo=0, hi=len([list])-1)

n = [1, 2, 5, 7, 9, 9, 10, 10, 10, 11, 12, 13, 13]

# 기존에 존재하지 않는 값
print(bisect.bisect_left(n, 4))

# 기존에 존재하지 않는 값 - 리스트의 모든 값들보다 작은 경우
print(bisect.bisect_left(n, 0))

# 기존에 존재하지 않는 값 - 리스트의 모든 값들보다 큰 경우
print(bisect.bisect_left(n, 299))

# 기존에 존재하는 값
print(bisect.bisect_left(n, 9))

결과
2 0 13 4

bisect_right() (또는 bisect())

bisect_left() 와 기능이 매우 유사합니다. 하지만 해당 함수는 원하는 값이 해당 리스트에 존재한다면, 해당 값의 가장 오른쪽 인덱스를 반환합니다. 주어진 값이 새로운 값이라면, 리스트에 삽입할 위치 인덱스를 반환합니다. 이 함수 역시 탐색 범위를 lo , hi 매개변수를 통해 설정할 수 있지만, 기본값으로 전체 리스트를 탐색 영역으로 설정합니다. 위의 예시와 비교하기 위해 함수만 바꿔서 예시 코드를 실행해 보겠습니다.

사용 형식 : bisect_right([list], [value], lo=0, hi=len([list])-1)

n = [1, 2, 5, 7, 9, 9, 10, 10, 10, 11, 12, 13, 13]

# 기존에 존재하지 않는 값
print(bisect.bisect_right(n, 4))

# 기존에 존재하지 않는 값 - 리스트의 모든 값들보다 작은 경우
print(bisect.bisect_right(n, 0))

# 기존에 존재하지 않는 값 - 리스트의 모든 값들보다 큰 경우
print(bisect.bisect_right(n, 299))

# 기존에 존재하는 값
print(bisect.bisect_right(n, 9))

결과
2 0 13 6

소제목에서 보신 바와 같이 bisect() 는 bisect_right() 와 똑같습니다. 이 함수는 bisect 라이브러리와는 구분되는 엄연한 함수이기 때문에 bisect 라이브러리만 불러오셨다면, bisect.bisect() 와 같이 사용하셔야 합니다. 두 함수 중 원하시는 함수를 사용하시면 되는데, 반환 인덱스 위치를 명시해 주는 bisect_right() 함수가 매우 직관적이라 사용하시는 것을 권장해 드립니다.

bisect()를 사용했을 경우

n = [1, 2, 5, 7, 9, 9, 10, 10, 10, 11, 12, 13, 13]

# 새로운 값
print(bisect.bisect(n, 4))

# 새로운 값 - 리스트의 모든 값들보다 작은 경우
print(bisect.bisect(n, 0))

# 새로운 값 = 리스트의 모든 값들보다 큰 경우
print(bisect.bisect(n, 299))

# 기존에 존재하는 값
print(bisect.bisect(n, 9))

결과
2 0 13 6

<aside> 💡 bisect_left() vs bisect_right() (또는 bisect())

결론부터 말씀드리면, 코딩테스트에서 bisect_left() 함수를 사용하는 것이 가장 좋습니다. 두 함수 모두 찾고자 하는 데이터가 없는 경우 같은 인덱스를 반환하지만, 중복되는 데이터가 존재할 경우 각 함수의 반환값에 차이가 발생합니다. bisect_left()의 경우, 중복되는 데이터의 존재 여부와 상관없이 항상 같은 인덱스를 반환합니다. 반대로 bisect_right()는 중복되는 데이터의 개수에 따라서 반환하는 인덱스가 달라집니다. 따라서 실수를 줄이기 위해서 bisect_left()를 사용하는 것이 좋습니다. 아래 코드로 두 함수의 상황별 차이를 확인해 보시죠.

</aside>

import bisect

# 찾고자하는 데이터가 존재하지 않는 경우
l1 = [1, 3, 7, 9, 10, 12, 12, 15]
print("------------------")
print("target :", 8)
print("bisect :", bisect.bisect(l1, 8))
print("bisect_right :", bisect.bisect_right(l1, 8))
print("bisect_left :", bisect.bisect_left(l1, 8))
print("------------------")

# 찾고자하는 데이터가 존재하는 경우
print("target :", 9)
print("bisect :", bisect.bisect(l1, 9))
print("bisect_right :", bisect.bisect_right(l1, 9))
print("bisect_left :", bisect.bisect_left(l1, 9))
print("------------------")

# 찾고자하는 데이터가 중복으로 존재하는 경우
l2 = [1, 3, 7, 9, 9, 9, 12, 12, 15]
print("target :", 9)
print("bisect :", bisect.bisect(l2, 9))
print("bisect_right :", bisect.bisect_right(l2, 9))
print("bisect_left :", bisect.bisect_left(l2, 9))
print("------------------")

결과
------------------ target : 8 bisect : 3 bisect_right : 3 bisect_left : 3 ------------------ target : 9 bisect : 4 bisect_right : 4 bisect_left : 3 ------------------ target : 9 bisect : 6 bisect_right : 6 bisect_left : 3 ------------------

방대한 데이터 안에서 특정 값 존재 여부 판단하기

이진 탐색 알고리즘이 자주 사용되는 이유 중 하나는 획기적인 $O(\mathrm{log}\,n)$의 시간복잡도입니다. 빠르게 원하는 데이터의 존재 여부 판단과 함께 bisect 라이브러리처럼 원하는 데이터의 위치를 파악할 수 있습니다. 정렬되어 있어야 한다는 전제조건만 충족하면, 이진 탐색 알고리즘은 빠른 속도로 탐색을 수행합니다. 대표적인 예시로는 2024 카카오 Tech Internship 3번 문제를 들 수 있습니다.

728x90

LIST

저작자표시 비영리 변경금지 (새창열림)

'코딩테스트 [킬링캠프]' 카테고리의 다른 글

2.7 힙 (Heap - Priority queue) (2)	2024.01.03
2.6 트리 (Tree) (0)	2024.01.03
2.4 재귀 (Recursion) (1)	2024.01.03
2.3 해시테이블 (Hash Table) (0)	2024.01.03
2.2 큐 & 스택 (Queue & Stack) (0)	2024.01.03

현재글2.5 이진 탐색 (Binary Search)

250x250

to become a NLP researcher ! 세상을 바꾸기 위해 무엇을 하고 있는가?

AI, 파이썬기초, 파이썬공부, 백준, Python, 코딩, xai, nlp, GPT, 컴퓨터공학과, 자연어처리, COT, 파이썬, LangChain, 네트워크공부, Prompt, 오류, Rag, LLM, 구글애드센스,

Today :
Yesterday :

zo_zni's Blog

2.5 이진 탐색 (Binary Search)

탐색 알고리즘(Search Algorithm)

이진 탐색(Binary Search)

이진 탐색 알고리즘 순서

이진 탐색 알고리즘 구현

이진 탐색 알고리즘 - 반복문

이진 탐색 알고리즘 - 재귀

이진 탐색 알고리즘 시간복잡도

코딩테스트 활용

bisect

bisect_left()

bisect_right() (또는 bisect())

방대한 데이터 안에서 특정 값 존재 여부 판단하기

'코딩테스트 [킬링캠프]' 카테고리의 다른 글

'코딩테스트 [킬링캠프]'의 다른글

티스토리툴바

« 2025/07 »
일	월	화	수	목	금	토
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

2.5 이진 탐색 (Binary Search)

탐색 알고리즘(Search Algorithm)

이진 탐색(Binary Search)

이진 탐색 알고리즘 순서

이진 탐색 알고리즘 구현

이진 탐색 알고리즘 - 반복문

이진 탐색 알고리즘 - 재귀

이진 탐색 알고리즘 시간복잡도

코딩테스트 활용

bisect

bisect_left()

bisect_right() (또는 bisect())

방대한 데이터 안에서 특정 값 존재 여부 판단하기

'코딩테스트 [킬링캠프]' 카테고리의 다른 글

'코딩테스트 [킬링캠프]'의 다른글

관련글

티스토리툴바