반응형 이진 탐색1 [C/C++] 백준 #1920 수 찾기(이진 탐색) 주어진 수열에서 M개의 데이터 중에 해당 수가 존재하는지 여부를 가리는 문제입니다. 집합 자료를 이용하면 손쉽게 구현할 수 있고, 또는 정렬 후 이진 탐색을 통해서도 이루어질 수 있습니다. 해시 집합 자료를 이용하면, 이론적으로 \(O(N+M)\)의 효율로 구현될 수 있습니다. 이진트리 집합 자료인 경우에는 \(O((N+M) \log N)\)이 걸립니다. \( \log N \) 자체가 큰 로드가 아니므로 사실상 집합 자료를 사용해도 되고, 정렬 후 이진 탐색을 사용해도 됩니다. 저는 정렬 후 이진 탐색을 이용해서 구현했습니다. 알고리즘 효율은 \(O( (N+M) \log N )\)입니다. 제가 작성한 소스입니다. //------------------------------------------------ .. 2022. 11. 8. 이전 1 다음 728x90
