시간복잡도3 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. [백준] 2751번 : 수 정렬하기 2 (C++) + 시간초과 & 런타임 에러(OutofBounds) 해결 문제 풀이 첫 번째 코드 - 실패 ➡ 시간복잡도: O(n2), int 배열 사용 // O(n^2), 시간초과 & 배열의 크기가 커 오류 발생 #include #include using namespace std; int main() { int N, num, temp; int arr[1000001]; cin >> N; for (int i = 0; i > num; arr[i] = num; } for (int i = 0; i > num; v.push_back(num); } sort(v.begin(), v.end()); for (int i = 0; i < N; i++) { cout 2024. 2. 21. [C++] Time Complexity (Trival Recursion, Dynamic Programming) Problem 4.1 Trival Algorithm Illustration Pseudo-code 1 function T(n) 2 if n 2023. 12. 13. 이전 1 다음 반응형
