06 이진 탐색 (설명)
이것이 코딩 테스트다. with 파이썬 - 06 이진 탐색 설명
⭐ 나동빈님의 유튜브를 통해 확인해 주세요!!
순차 탐색
리스트 안에 있는 특정한 데이터를 찾기 위해 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법이다.
- 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용한다.
# 순차 탐색 소스코드 구현
def sequential_search(n, target, array):
# 각 원소를 하나씩 확인하며
for i in range(n):
# 현재의 원소가 찾고자 하는 원소와 동일한 경우
if array[i] == target:
return i + 1 # 현재의 위치 반환(인덱스는 0부터 시작하므로 1 더하기)
print("생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요")
input_data = input().split()
n = int(input_data[0]) # 원소의 개수
target = input_data[1] # 찾고자 하는 문자열
print("앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄워쓰기 한 칸으로 합니다.")
array = input().split()
# 순차 탐색 수행 결과 출력
print(sequential_search(n, target, array))
순차 탐색은 이름처럼 순차로 데이터를 탐색한다는 의미이다. 리스트의 데이터에 하나씩 방문하며 특정한 문자열과 같은지 검사하므로 구현도 간단하다.
이진 탐색
정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색하는 방법
이진 탐색은 시작점, 끝점, 중간점을 이용하여 탐색 범위를 설정합니다.
- 시작점: 0, 끝점: 9, 중간점: 4 (소수점 이하 제거)
- 중간점 데이터와 찾으려는 데이터를 비교한다. 중간점의 데이터가 더 크므로 중간점 이 후의 값은 확인할 필요가 없다. 끝점을 이 전으로 한칸 옮긴다
- 시작점: 0, 끝점: 3, 중간점: 1 (소수점 이하 제거)
- 중간점 데이터는 찾으려는 데이터보다 작으므로 중간점 이 전의 값은 확인할 필요가 없다. 시작점을 중간점기준으로 이 후로 한칸 옮긴다.
- 시작점: 2, 끝점: 3, 중간점: 2 (소수점 이하 제거)
중간점에 위치한 데이터와 찾으려는 데이터가 동일하므로 이 시점에서 탐색을 종료한다.
시간 복잡도
- 단계 마다 탐색 범위를 2로 나누는 것과 동일하므로 연산 횟수는 log^2 N에 비례합니다.
- 이진 탐색은 탐색 범위를 절반식 줄이며, 시간 복잡도는 O(logN)을 보장합니다.
# 이진 탐색 소스코드 구현(재귀 함수)
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(원소의 개수)과 target(찾고자 하는 문자열)을 입력받기
n, target = list(map(int, input().split()))
# 전체 원소 입력받기
array = list(map(int, input().split()))
# 이진 탐색 수행 결과 출력
result = binary_search(array, target, 0, n - 1)
if result is None:
print("원소가 존재 하지 않습니다.")
else:
print(result + 1)
이진 탐색_반복문
# 이진 탐색 소스코드 구현(반복문) def binary_search(array, target, start, end): while start <= end: mid = (start + end) // 2 # 찾은 경우 중간점 인덱스 반환 if array[mid] == target: return mid # 중간점의 값보다 찾고자 하는 값이 작은 경우 왼쪽 확인 elif array[mid] > target: end = mid - 1 # 중간점의 값보다 찾고자 하는 값이 큰 경우 오른쪽 확인 else: start = mid + 1 return None # 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 is None: print("원소가 존재하지 않습니다.") else: print(result + 1)
파이썬 이진 탐색 라이브러리
- 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)) # 2
print(bisect_right(a,x)) # 4
값이 특정 범위에 속하는 데이터 개수 구하기
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))
파라메트릭 서치 (Parametric Search)
- 파라메트릭 서치란 최적화 문제를 결정 문제 (”예” 혹은 “아니오”)로 바꾸어 해결하는 기법이다.
트리 자료구조
이진 탐색은 전체 조건이 데이터 정렬이다.
- 동작하는 프로그램에서 데이터를 정렬해두는 경우가 많은므로 이진 탐색을 효과적으로 사용할 수 있다.
데이터베이스는 내부적으로 대용량 데이터 처리에 적합한 트리(Tree) 자료구조를 이용하여 항상 데이터가 정렬되어 있다.
트리 자료구조는 노드와 노드의 연결로 표현하며 여기에서 노드는 정보의 단위로서 어떠한 정보를 가지고 있는 개체로 이해할 수 있다.
트리 자료구조는 그래프 자료구조의 일종으로 데이터베이스 시스템이나 파일 시스템과 같은 곳에서 많은 양의 데이터를 관리하기 위한 목적으로 사용된다.
- 트리는 부모 노드와 자식 노드의 관계로 표현된다.
- 트리의 최상단 노드를 루트 노드라고 한다.
- 트리의 최하단 노드를 단말 노드라고 한다.
- 트리에서 일부를 떼어내도 트리 구조이며 이를 서브 트리라 한다.
- 트리는 파일 시스템과 같은 계층적이고 정렬된 데이터를 다루기에 적합하다.
큰 데이터를 처리하는 소프트웨어는 대부분 데이터를 트리 자료구조로 저장해서 이진 탐색과 같은 탐색 기법을 이용해 빠르게 탐색이 가능하다.
이진 탐색 트리
이진 탐색 트리란 이진 탐색이 동작할 수 있도록 고안된, 효율적인 탐색이 가능한 자료구조이다.
이진 탐색 트리는 다음과 같은 특징이 있다.
- 부모 노드보다 왼쪽 자식 노드가 작다
- 부모 노드보다 오른쪽 자식 노드가 크다
👉 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드
이진 탐색 트리가 미리 구현되어 있다고 가정하고 다음 그림과 같은 이진 탐색 트리에서 테이터를 조회하는 과정만 살펴본다.
step 1
이진 탐색은 루트 노드부터 방문한다. 루트 노드는 ‘10’이고 찾는 원소값은 ‘14’이다.
step 2
오른쪽 자식 노드인 ‘17’이 이번에는 부모노드 이다. ‘17’은 찾는 원소값인 ‘14’보다 크다.
step 3
현재 방문한 노드의 값인 ‘14’와 찾는 원소값 ‘14’와 동일하다. 따라서 탐색을 마친다.
