이진 탐색, 이진 탐색 트리.

이진 탐색 

이진 탐색 = 반으로 쪼개면서 탐색하기. 시작점 인덱스, 끝점 인덱스를 입력 받아서 이 둘을 합쳐서 2로 나눈 값을 중간 값으로 설정한 후, 중간 값이 타겟 값보다 크면 중간값 이상의 값을 모두 버리고 중간값 이하 부분에서 똑같이 반복. 시간 복잡도는 O(logN). 탐색 범위가 2000만이 넘어가면 거의 무조건 이진 탐색을 써야한다고 보면 된다. 정말 중요한 코드이므로 꼭 암기해 두자!!!!

 

------------------------------------------------------------------------

 

트리 자료구조

데이터베이스는 내부적으로 대용량 데이터 처리에 적합한 트리 자료구조를 이용하여 항상 데이터가 정렬되어 있다. 트리 자료구조는 그래프 자료구조의 일종으로 데이터베이스 시스템이나 파일 시스템과 같은 곳에서 많은 양의 데이터를 관리하기 위한 목적으로 사용한다.  즉 큰 데이터를 처리하는 소프트웨어는 대부분 데이터를 트리 자료구조로 저장해서 이진 탐색과 같은 기법을 이용해 빠르게 탐색이 가능하다. 

이진 탐색 트리

1. 부모 노드보다 왼쪽 자식 노드가 작다.

2. 부모 노드보다 오른쪽 자식 노드가 크다.

 

실전 문제 

떡볶이 떡 만들기

떡의 개수N, 요청한 떡의 길이 M이 첫 줄에 주어짐

둘째 줄에 각 떡의 길이가 주어짐

절단기의 길이를 h로 설정하면 h보다 긴 떡은 잘리고 짧은 떡은 안 잘림. 

결과:

4 6
19 15 10 17
15

실전 문제 

백준 1920 수 찾기