chaper 7. 이진 탐색

1. 순차탐색

데이터를 앞에서부터 차례로 확인하는 방법

시간복잡도가 log(N)

import sys
input=sys.stdin.readline
 
print('생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요')
a, find=input().split()
print('앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.')
arr=list(input().split())
 
for i in range(len(arr)):
    if arr[i]==find:
        print(i+1)
        break

 

 

2. 이진탐색

데이터를 반으로 쪼개며 탐색하는 방법

이미 정렬 돼 있는 데이터 안에서만 가능하다

시간복잡도는 O(logN)

import sys
input=sys.stdin.readline
 
print('생성할 원소 개수를 입력한 다음 한 칸 띄고 찾을 문자열을 입력하세요')
a, find=input().split()
print('앞서 적은 원소 개수만큼 문자열을 입력하세요. 구분은 띄어쓰기 한 칸으로 합니다.')
arr=list(input().split())
 
for i in range(len(arr)):
    if arr[i]==find:
        print(i+1)
        break

 

 

3. 트리 자료구조

이진 탐색은 먼저 데이터를 정렬하고 탐색을 시작해야 되지만

트리 자료구조는 데이터베이스 내부적으로 트리 자료구조를 이용해 항상 데이터가 정렬 돼있다.

이진탐색보다 탐색 속도가 빠르다

왼쪽 자식노드 < 부모노드 <오른쪽 자식노드 순이다.

만약 위의 트리에서 36을 찾으면

① 루트노드와 36을 비교했는데 루트노드가 36보다 작으므로 오른쪽 자식 노드를 방문한다

② 오른쪽 자식노드(45)가 36보다 크므로 45의 왼쪽 자식노드를 방문한다

③ 36 발견

이런식으로 동작한다

 

 

① 부품 찾기

import sys
input=sys.stdin.readline
 
n=int(input())
have=list(map(int, input().split()))
m=int(input())
find=list(map(int, input().split()))
have.sort()
 
 
for i in find:
    check=0
    start = 0
    end = len(have)-1
    while start<=end:
        mid=(start+end)//2
 
        if i==have[mid]:
            print('yes', end=' ')
            check=1
            break
        elif i<have[mid]:
            end = mid - 1
        else:
            start = mid + 1
    if check==0:
        print('no', end=' ')

② 떡볶이 떡 만들기

import sys
input=sys.stdin.readline
 
n, m = map(int, input().split())
arr=list(map(int, input().split()))
 
start=0
end=max(arr)-1
while start<=end:
    result=0
    mid=(start+end)//2
    for i in arr:
        if mid<i:
            result+=i-mid
    #떡 양이 부족한 경우 절단기 높이 줄이기
    if result<m:
        end=mid-1
    else:
        result=mid
        start=mid+1
 
print(result)
 

구하고자 하는 절단기의 높이는 이진 탐색으로 구한다

 

 

 

출처 : 이것이 취업을 위한 코딩 테스트다 with 파이썬 (나동빈 저)