[Python] 백준 1920번(수 찾기) 문제 풀이

 

 파이썬의 in 기능을 활용하면 풀릴 것 같아 그렇게 풀었더니 시간 초과가 떴다. 그래서 보니 이 문제는 이진 탐색 알고리즘을 사용해야 풀리는 문제였다.

 

이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.

 

 위키백과에서 인용했다. 이진 검색 알고리즘에 관해서는 다른 포스팅에서 더 자세히 다뤄 보도록 할 것이다.

 

def binary_search(array, x):
    start = 0
    end = len(array) - 1 
    while start <= end:
        middle = (start + end) // 2
        if array[middle] == x:
            return "1"
        elif array[middle] < x:
            start = middle + 1
        else:
            end = middle - 1
    return "0"
    
input()
n = input().split()
n.sort()
input()
m = input().split()
for i in range(len(m)):
    print(binary_search(n, m[i]))

 

 이분 탐색 함수 binary_search()를 만들어 해결했다.