이진탐색2 [백준] 10816번 : 숫자 카드 2 | binary search & unordered map (C++) 문제 풀이 binary_search를 이용해 풀이했다. O(logn) 문제를 맞춘 후, unordered_map을 이용해도 가능한 것을 확인해 사용해보았다. O(1) 이 문제를 풀며 놀라웠던 점은 시간복잡도가 O(logn)인 binary_search가 O(1)인 unordered_map보다 빨랐다는 것이다. 찾아보니 이에 대한 질문 글이 있어 답변을 가져왔다. 현실 세계에서는 N이 무한히 큰 경우가 거의 없기 때문에 O(lgN)과 O(1) 정도의 차이는 N의 크기에 따라 시간복잡도에 붙은 상수로 자주 뒤집어집니다. 가령, 최소한의 비교로 원하는 수를 찾아야 하는 가상의 문제가 있다고 합시다. N에 관계없이 항상 50번의 비교로 수를 찾는 어떤 O(1) 알고리즘과 N에 대해 ceil(lgN)번의 비교를 하.. 2024. 4. 1. [백준] 1920번 : 수 찾기 | binary search (C++) 문제 풀이 C++ 내 내장되어 있는 binary_search( ) 함수를 이용해 풀이했다. 시간복잡도는 O(logn)으로 빠른 속도로 계산할 수 있다. 입력받는 정수의 범위가 2의 31승까지 이므로 long long으로 선언한다. int n, m; long long listnum, findnum; cin >> n; vector을 이용해 입력받은 값을 저장한다. vector listv; for (int i = 0; i > listnum; listv.push_back(listnum); } binary search는 가운데에 있는 값(중간 크기의 값)을 기준으로 정렬하기 때문에, 꼭 오름차순 혹은 내림차순으로 정렬해야 한다. 따라서, sort() 함수를 이용해 정렬한 후 bian.. 2024. 4. 1. 이전 1 다음 반응형
