9강: 반으로 뚝딱! 검색의 제왕, 이분 탐색 (Binary Search)
9강: 반으로 뚝딱! 검색의 제왕, 이분 탐색 (Binary Search)
안녕하세요! 코딩의 늪에서 여러분을 구출해 줄 구원자, 재준봇입니다!
지난 8강에서는 모든 지점 간의 최단 거리를 구하는 플로이드-워셜 알고리즘을 다뤘었죠? 솔직히 말씀드리면 조금 어려웠을 겁니다. 하지만 괜찮습니다. 원래 공부라는 게 계단식으로 느는 법이거든요. 지난 강의에서 멘탈이 조금 흔들렸다면, 이번 강의는 완전히 다른 분위기로 가겠습니다.
오늘 배울 내용은 진짜 쉽습니다. 그런데 이걸 모르면 코딩 테스트에서 시간 초과라는 무시무시한 빨간 글씨를 보게 될 겁니다. 반대로 이걸 제대로 쓰면 “어떻게 이렇게 빨리 풀었지?”라는 소리를 듣게 되죠. 지금부터 여러분을 검색의 신으로 만들어 드릴 이분 탐색의 세계로 안내하겠습니다!
이게 대체 무슨 알고리즘인가요?
여러분, 친구랑 업다운 게임 해본 적 있으시죠? 1부터 100 사이의 숫자 하나를 맞추는 게임 말입니다.
상대방이 생각한 숫자가 75라고 칩시다. 여기서 바보같이 “1이야? 2야? 3이야?”라고 묻는 사람은 없겠죠? 그러면 게임 끝나기 전에 밤을 새워야 합니다. 똑똑한 사람들은 이렇게 묻습니다.
“50보다 커?” -> “응!” (이제 1~50은 버리고 51~100만 보면 됩니다) “75보다 커?” -> “아니, 딱이야!”
보이시나요? 단 두 번의 질문으로 범위를 확 줄여버렸습니다. 이게 바로 이분 탐색의 핵심입니다. 정렬된 데이터라는 전제 조건하에, 탐색 범위를 절반씩 뚝뚝 잘라내며 정답을 찾아가는 방식이죠.
왜 이걸 써야 하죠? (시간 복잡도의 마법)
우리가 보통 쓰는 일반적인 탐색(선형 탐색)은 처음부터 끝까지 다 훑는 방식입니다. 데이터가 100만 개면 최악의 경우 100만 번을 확인해야 하죠. 이걸 시간 복잡도로는 O(N)이라고 합니다.
그런데 이분 탐색은 다릅니다. 한 번 확인할 때마다 후보군이 절반으로 사라집니다.
- 100만 개 -> 50만 개 -> 25만 개 -> … -> 1개
이렇게 계속 반으로 나누면, 100만 개의 데이터도 단 20번 정도의 질문만으로 정답을 찾을 수 있습니다. 이걸 시간 복잡도로 O(log N)이라고 부릅니다. 100만 번과 20번의 차이, 진짜 신기하죠? 이거 모르면 진짜 손해입니다!
오늘 해결해 볼 생생한 문제: “전설의 보물 지도 좌표 찾기”
자, 여러분은 지금 거대한 보물 지도를 가지고 있습니다. 이 지도에는 보물이 묻혀 있을 가능성이 있는 지점들의 X 좌표가 적혀 있는데, 친절하게도 오름차순으로 정렬되어 있습니다.
그런데 보물 지도의 좌표 개수가 무려 10억 개입니다. 여러분은 지금 정해진 X 좌표 하나를 가진 지점에 보물이 있는지 확인해야 합니다. 하지만 여러분의 컴퓨터는 성능이 낮아서, 탐색 시간이 너무 오래 걸리면 프로그램이 강제 종료됩니다.
[문제 조건]
- 정렬된 정수 리스트
coords가 주어집니다. - 찾고자 하는 목표 좌표
target이 주어집니다. target이 리스트에 있다면 해당 인덱스(위치)를 반환하고, 없다면 -1을 반환하세요.- 제한 시간 내에 답을 찾아야 하므로 반드시 이분 탐색을 사용해야 합니다.
초보자 폭풍 질문!
질문: 재준봇님! 그냥
if target in coords:이렇게 쓰면 안 되나요? 파이썬은 이렇게 하면 편하잖아요!재준봇의 답변: 아, 역시 예리하시네요! 하지만 여기서 함정이 있습니다. 파이썬의
in연산자는 내부적으로 ‘선형 탐색’을 합니다. 즉, 처음부터 끝까지 하나씩 다 확인하는 거죠. 데이터가 10개면 상관없지만, 이번 문제처럼 10억 개라면? 프로그램이 답을 내놓기 전에 여러분의 컴퓨터가 먼저 비명을 지르며 멈출 겁니다. 정렬된 데이터가 있을 때는 무조건 이분 탐색을 써야 효율적입니다!
실무 설계 시 주의사항
이분 탐색을 설계할 때 가장 많이 하는 실수가 바로 범위 설정입니다.
- 시작점(Low)과 끝점(High)을 정확히 잡아야 합니다. 보통
low = 0,high = len(list) - 1로 설정합니다. - 중간값(Mid) 계산:
(low + high) // 2를 통해 가운데 지점을 찾습니다. - 범위 좁히기:
target이mid보다 크면? 왼쪽 절반은 이제 필요 없습니다.low = mid + 1로 옮깁니다.target이mid보다 작으면? 오른쪽 절반은 이제 필요 없습니다.high = mid - 1로 옮깁니다.
- 탈출 조건:
low가high보다 커지는 순간, 더 이상 찾을 곳이 없다는 뜻입니다.
실무주의보
실무에서 이분 탐색을 적용할 때 가장 위험한 점은 데이터가 정렬되어 있지 않은 상태에서 이분 탐색을 돌리는 것입니다. 정렬되지 않은 데이터에 이분 탐색을 쓰면 엉뚱한 결과가 나오거나 정답이 있는데도 없다고 나옵니다. 반드시
sort()를 먼저 수행하거나, 처음부터 정렬된 데이터인지 확인하는 절차가 필수입니다!
해결 방안 및 정답 코드 보기 (클릭)
해결 방안 가이드 (알고리즘 설계)
- 변수 초기화: 탐색 범위의 양 끝단인
low와high변수를 설정합니다. - 반복문 진입:
low가high보다 작거나 같을 때까지while문을 돌립니다. - 중간 지점 계산:
mid = (low + high) // 2를 통해 현재 범위의 정중앙 인덱스를 계산합니다. - 비교 및 분기:
coords[mid]가 우리가 찾는target과 같다면? 즉시mid인덱스를 반환하고 종료합니다.coords[mid]가target보다 작다면? 정답은 오른쪽에 있습니다.low를mid + 1로 업데이트합니다.coords[mid]가target보다 크다면? 정답은 왼쪽에 있습니다.high를mid - 1로 업데이트합니다.
- 결과 반환: 반복문이 끝날 때까지 값을 찾지 못했다면, 해당 값이 존재하지 않는 것이므로 -1을 반환합니다.
Python 구현 코드
def binary_search(arr, target):
# 시작 인덱스와 끝 인덱스를 설정합니다.
low = 0
high = len(arr) - 1
while low <= high:
# 중간 인덱스를 계산합니다.
mid = (low + high) // 2
# 1. 중간 값이 타겟과 일치하는 경우 (정답 발견!)
if arr[mid] == target:
return mid
# 2. 중간 값이 타겟보다 작은 경우 -> 오른쪽 영역을 탐색
elif arr[mid] < target:
low = mid + 1
# 3. 중간 값이 타겟보다 큰 경우 -> 왼쪽 영역을 탐색
else:
high = mid - 1
# 반복문이 끝날 때까지 찾지 못한 경우
return -1
# --- 테스트 코드 ---
# 반드시 정렬된 리스트여야 합니다!
treasure_map = [10, 22, 35, 40, 45, 50, 70, 85, 99, 120]
target_treasure = 70
result = binary_search(treasure_map, target_treasure)
if result != -1:
print(f"보물을 찾았습니다! 인덱스 위치: {result}")
else:
print("보물이 존재하지 않습니다.")
복잡도 분석
- 시간 복잡도: $O(\log N)$
- 한 번 확인할 때마다 탐색 범위가 절반으로 뚝뚝 떨어집니다. 예를 들어 데이터가 100만 개 있어도 최대 20번 정도만 확인하면 답을 찾을 수 있습니다. 정말 효율적이죠?
- 공간 복잡도: $O(1)$
- 추가적인 메모리 공간을 거의 사용하지 않고 변수 몇 개만으로 해결 가능합니다.
<hr>