[#5] 이진 탐색 chapter7

순차 탐색

>> 리스트 안에 있는 특정한 데이터를 찾기 위해
앞에서부터 데이터를 하나씩 차례대로 확인
>> 최악의 경우 시간 복잡도 O(N)

이진 탐색

>> 반으로 쪼개면서 탐색하기
>> 찾으려는 데이터와 중간점 위치에 있는 데이터를
반복적으로 비교해서 원하는 데이터 찾기

이진 탐색은 원소의 개수가 절반씩 줄어든다
따라서 시간 복잡도는 O(logN)

이진탐색 구현 방법은 재귀함수 이용, 반복문 이용

처리해야할 데이터의 개수나 값이 1000만 단위 이상이면,
이진 탐색과 같이
O(logN)의 속도를 내는 알고리즘을 떠올려야함

문제에 자주 나오니 외우길 권장

트리 자료구조

>> 큰 데이터를 처리하는 소프트웨어는
대부분 데이터를 트리 자료구조로 저장해서
이진 탐색과 같은 탐색 기법을 이용해
빠르게 탐색 가능

이진 탐색 트리

>> 이진 탐색 트리란 이진 탐색이 동작할 수 있도록 고안된 효율적인 탐색이 가능한 자료구조다

이진 탐색 트리 특징
부모 노드보다 왼쪽 자식 노드가 작고,
부모 노드보다 오른쪽 자식 노드가 크다

이진탐색 트리문제는 출제빈도가 낮다

데이터 입력을 빠르게 받기
>> readline() 함수 이용
input을 사용하면 시간 초과가 일어날 가능성 다분

import sys
input_data=sys.stdin.readline().rstrip()
print(input_data)

rstrip 함수는 줄바꿈 문자 제거함