이분 탐색의 원리 + 백준 1920 수 찾기

이분 탐색의 이분은 '둘로 나눈다'는 뜻이다. 탐색할 자료를 둘로 나누어 찾는 값이 있을 법한 곳만 탐색하기 때문에

자료를 하나하나 찾아야 하는 순차 탐색보다 원하는 자료를 훨씬 빨리 찾을 수 있다.

 

 

600page 책을 펼치는 과정으로 예시를 들면

 

1. 책 510쪽을 펴야한다고 가정.

2. 책의 중간쯤 펼쳐 300쪽이 나옴

3. 찾고자 하는 510은 300쪽보다 뒤에 있음. 따라서 300쪽 앞인 1~300쪽은 더 이상 찾을 필요가 없다.

4. 301~600 사이에 중간쯤을 또 펼쳐 450p가 나옴. 510은 더 뒤에 있음. 301~450 배제.

5. 이 과정을 반복하며 원하는 510쪽이 나오면 탐색을 멈춘다.

 

이렇게 하게되면 이분 탐색의 계산 복잡도는 O(logn)으로, 순차 탐색의 계산 복잡도인 O(n)보다 훨씬 효율적이게 된다.

 

이를 코드로 하면

 

import sys
num = int(input())
#모든 책 페이지가 리스트 형태로 주어진다고 가정
bookNum = list(map(int,sys.stdin.readline().split()))
#이분 탐색은 리스트가 정렬되어 있어야함.
# 1,7,3,4 이런식으로 되어있으면 이분탐색은 이루어질 수 없다
bookNum.sort()

start=0
end = len(bookNum)-1
result=1  # 시도한 횟수
while start<=end:
    mid=(start + end) // 2
    if num == bookNum[mid]:
        print(result)
        break
    elif num > bookNum[mid]:
        start = mid + 1
        result+=1
    else:
        end = mid - 1
        result+=1

이런 식으로 코드가 짜여지게 된다.

이를 활용해 백준의 1920번을 풀 수 있게 된다.

import sys
n=int(input())
num1=list(map(int,sys.stdin.readline().split()))
n2=int(input())
num2=list(map(int,sys.stdin.readline().split()))

num1.sort()

for i in num2:
    start=0
    end=len(num1)-1
    while start <= end:
        mid = (start+end) // 2
        if i == num1[mid]:
            print(1)
            break
        elif i > num1[mid]:
            start = mid+1
        else:
            end=mid-1
    else:
        print(0)

이런 식으로 이분탐색을 해서 정답을 맞았는데....

N = int(input())
A = set(input().split())
M = int(input())
num = input().split()

for i in num:
    if i in A:
        print("1")
    else :
        print("0")

다른사람의 것을 보니 안해도 됐었다는 것은 비밀.......