binary search1 1764번 - 듣보잡 | 시간초과, binary search (C++) 문제 풀이 1. 처음에는 이중 for문을 이용해 풀이했다. 당연히 시간초과 발생 O(n2) ➡ 애초에 최댓값이 50만씩이여서, 50만 x 50만 = 시간 초과가 날 수 밖에 없었음.. 2. 시간초과 문제를 해결하기 위해서는, map 또는 binary search를 사용해야 한다. ➡ map: O(logn), Red-Black Tree, key - valued의 pair로 저장된다. 중복 허용 X ➡ binary search: O(logn), 꼭 정렬을 먼저 해줘야 한다. 나는 binary search를 이용해 문제를 해결했다. 추가로, vector는 데이터 순차 저장이므로 검색 속도가 느리다. 검색에는 hash_map(unordered_map)과 map을 사용하는 것이 빠르다. hash_map(unord.. 2024. 4. 3. 이전 1 다음 반응형
