[이진 탐색 알고리즘] 범위를 반씩 좁혀가는 탐색

순차 탐색

- 리스트 안에 있는 특정한 데이터를 찾기 위하여 앞에서부터 데이터를 하나씩 차례대로 확인하는 방법

- 보통 정렬되지 않은 리스트에서 데이터를 찾아야 할 때 사용

- 리스트 내에 데이터가 아무리 많아도 시간만 충분하다면 항상 원하는 데이터를 찾을 수 있음

- 이름처럼 순차로 데이터를 탐색한다는 의미

- 리스트의 데이터에 하나씩 방문하며 특정한 문자열과 같은지 검사하므로 구현도 간단

- 리스트에 특정 값의 원소가 있는지 체크할 때 사용

- 데이터의 개수가 N개일 때 최대 N번의 비교 연산이 필요하므로 최악의 경우 시간 복잡도는 O(N)

 

이진 탐색

- 배열 내부의 데이터가 정렬되어 있어야만 사용할 수 있는 알고리즘

- 데이터가 무작위일 때는 사용할 수 없지만, 이미 정렬되어 있다면 매우 빠르게 데이터를 찾을 수 있음

- 탐색 범위를 절반씩 좁혀가며 데이터를 탐색

- 위치를 나타내는 변수 3개를 사용 (탐색하고자 하는 범위의 시작점, 끝점, 중간점)

- 찾으려는 데이터와 중간점 위치에 있는 데이터를 반복적으로 비교

- 한 번 확인할 때마다 확인하는 원소의 개수가 절반씩 줄어든다는 점에서 시간 복잡도가 O(logN)

- 절반씩 데이터를 줄어들도록 만든다는 점은 앞서 다룬 퀵 정렬과 공통점이 있음

- 코딩 테스트에서 단골로 나오는 문제

- 높은 난이도의 문제에서는 이진 탐색 알고리즘이 다른 알고리즘과 함께 사용

- 탐색 범위가 큰 상황에서의 탐색을 가정하는 문제가 많음

- 탐색 범위가 2,000만을 넘어가면 이진 탐색으로 문제에 접근

- 처리해야 할 데이터의 개수가 1,000만 단위 이상으로 넘어가면 이진 탐색과 같이 O(logN) 속도의 알고리즘으로 문제 해결

 

트리 자료구조

- 노드와 노드의 연결로 표현하며 노드는 정보의 단위로서 어떠한 정보를 가지고 있는 개체

- 그래프 자료구조의 일종으로 데이터베이스 시스템이나 파일 시스템과 같은 곳에서 많은 양의 데이터를 관리하기 위한 목적으로 사용

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

 

이진 탐색 트리

- 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드가 성립해야지 이진 탐색 트리

 

빠르게 입력받기

- 이진 탐색 문제는 입력 데이터가 많거나 탐색 범위가 매우 넓은 편

- 데이터의 개수가 1,000만 개를 넘어가거나 탐색 범위의 크기가 1,000억 이상이라면 이진 탐색 알고리즘을 의심

- 입력 데이터의 개수가 많은 문제에 input() 함수를 사용하면 동작 속도가 느려 시간 초과로 오답 판정을 받을 수 있음

- 입력 데이터가 많은 문제는 sys 라이브러리의 readline() 함수를 이용하면 시간 초과를 피할 수 있음

- sys 라이브러리를 사용할 때는 한 줄 입력받고 나서 rstrip() 함수를 꼭 호출해야 함

- 소스 코드에 readline()으로 입력하면 입력 후 엔터가 줄 바꿈 기호로 입력되는데, 이 공백 문자를 제거하려면 rstrip() 함수를 사용해야 함

 

import sys

# 하나의 문자열 데이터 입력 받기
input_data = sys.stdin.readline().rstrip()
# 입력 받은 문자열 그대로 출력하기
print(input_data)