이분탐색 (1) 썸네일형 리스트형 [백준] 1920 - 수 찾기 https://www.acmicpc.net/problem/1920 1920번: 수 찾기 첫째 줄에 자연수 N(1≤N≤100,000)이 주어진다. 다음 줄에는 N개의 정수 A[1], A[2], …, A[N]이 주어진다. 다음 줄에는 M(1≤M≤100,000)이 주어진다. 다음 줄에는 M개의 수들이 주어지는데, 이 수들이 A안�� www.acmicpc.net 최대 10만개의 숫자목록을 받은 후, 다음에 입력받는 최대 10만개의 숫자들이 이전의 숫자 목록에 존재하는지의 여부를 확인하는 문제다. 10만개 정도의 input이 주어졌을 때, 시간복잡도가 N^2이 되어도 1000억번의 연산이 필요하다. N log N으로 시간복잡도를 끊어야 하는데, 이 문제의 경우는 검색 대상인 숫자 목록을 정렬을 시켜놓고 이분탐색을.. 이전 1 다음