unordered_map1 [백준] 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. 이전 1 다음 반응형
