파이썬과 이진 탐색(Binary Search)
순차 탐색
- 리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법으로, 말 그대로 ‘순차로 데이터를 탐색’한다는 의미이다.
- 리스트 자료형에서 특정한 값을 가지는 원소의 개수를 세는 count() 메서드를 이용할 때도 내부에서는 순차 탐색이 수행된다.
- 순차 탐색을 파이썬 코드로 작성하면 다음과 같다.
def seq_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(seq_search(n, target, array))
이진 탐색 : 반으로 쪼개면서 탐색하기
- 우선, 이진 탐색은 데이터가 정렬되어 있어야만 사용할 수 있다.
- 이진 탐색은 탐색하고자 하는 범위의 시작점, 끝점, 중간점을 정의한 뒤부터 시작된다.
-
즉, 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교해서 원하는 데이터를 찾는 게 이진 탐색 과정이다.
아래의 코드를 보면서 이진탐색을 이해해보자
# 이진 탐색 소스코드 구현(재귀함수) 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) # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인 elif array[mid] < target: return binary_search(array, target, mid + 1, end) # n(원소의 개수)과 target(찾고자 하는 문자열)을 입력받기 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)- 이진 탐색은 코딩 테스트에서 단골로 나오는 문제이니, 여러번 연습해서 외우는 것이 좋다.
- 또한, 이진 탐색의 원리는 다른 알고리즘에서도 폭넓게 적용되는 원리와 비슷하기도 하고, 다루어야 할 데이터의 개수가 많아 O(logN)의 시간 복잡도를 구현해야 하는 경우에 필수적으로 사용된다.
트리 자료구조
- 트리 자료구조는 노드와 노드의 연결로 표현하며, 트리의 규칙은 아래와 같다.
- 트리는 부모 노드와 자식 노드의 관계로 표현된다
- 트리의 최상단 노드를 루트 노드라 한다
- 트리의 최하단 노드를 단말(leaf) 노드라 한다
- 트리에서 일부를 떼어내도 트리 구조이며, 떼어낸 트리를 ‘서브 트리’라고 한다
- 트리는 파일 시스템과 같이 계층적이고 정렬된 데이터를 다루기에 적합하다.
- 따라서, 큰 데이터를 처리하기 위해서는 ‘트리 구조’로 설계하여 ‘이진 탐색’처럼 빠른 탐색 방식으로 탐색하는 것이 필요하다. 이러한 방식을 구현한 것이 ‘이진탐색트리’이다.
이진 탐색 트리
- 이진 탐색 트리는 아래와 같은 규칙이 있다.
- 부모 노드보다 왼쪽 자식 노드가 작다
- 부모 노드보다 오른쪽 자식 노드가 크다
- 이러한 규칙에 의해, 빠른 탐색이 가능하다.
빠르게 입력받기
-
한 줄 입력받아 출력하는 소스코드
import sys # 하나의 문자열 데이터 입력받기 input_data = sys.stdin.readline().rstrip() # rstrip은 right-strip으로, 엔터 키나 스페이스와 같이 불필요한 공백문자를 제거하기 위해 쓴다. print(input_data)
이진 탐색 사용하는 방법
다음 코드를 구현하라.
- 입력
- 첫째 줄에 정수 N이 주어진다
- 둘째 줄에는 공백으로 구분해 N개의 정수가 주어진다.
- 셋째 줄에는 정수 M이 주어진다
- 넷째 줄에는 공백으로 구분해 M개의 정수가 주어진다.
- 출력
- 첫째 줄에 공백으로 구분해, 넷째 줄에서 언급한 정수가 둘째 줄에 언급되었으면 yes, 아니면 no를 출력하라.
입력 예시
5
8 3 7 9 2
3
5 7 9
-----------------------
출력 예시
no yes yes
N이 엄청 클 경우를 대비해서 이진 탐색으로 구현해보자.
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 = int(input())
n_li = list(map(int, input().split()))
n_li.sort()
m = int(input())
m_li = list(map(int, input().split()))
for i in m_li:
if binary_search(n_li, i, 0, n - 1) == None: print('no', end=' ')
else: print('yes', end=' ')
- 입력값이 적으면 ‘굳이 이렇게 짜야 하나?’라는 생각을 할 수도 있지만, 실제 코딩테스트에서는 어마어마한 입력값을 주기 때문에 이진 탐색을 구현하는 방법을 꼭 숙지해야한다.