킵고잉

코딩테스트 준비

• 1012 C++

  코딩테스트 준비 2025. 2. 17. 17:47

  https://www.acmicpc.net/problem/1012 상하좌우로 인접한 덩어리가 몇 개인지 찾아야 한다.M 따라서 최악의 경우 O(V+E) => 2500 + 10000 = 12500으로 시간 제한(1초) 내에 dfs를 이용해 해결할 수 있다. #include #include bool dfs(int x, int y, const std::vector> &fieldMap, std::vector> &visited) { if (x = fieldMap.size() || y >= fieldMap[0].size()) { return false; } if (visited[x][y] || fieldMap[x][y] != 1) { return false; } ..

  Read More
• C++ 시간 복잡도 계산

  코딩테스트 준비 2021. 5. 12. 00:28

  Big-O 수행 시간(빠름) O($1$) (느림) C++에서는 1초에 약 1억 번 정도의 연산을 수행할 수 있다.시간 제한이 2초면 연산 횟수는 2억 번 이내여야 하는 것이다. 원소 백만 개($10^6$)까지는 O($n$log$n$)으로 커버 가능하다. => stl의 sort 사용 가능원소 천만 개($10^7$)까지는 O($n$)으로 커버 가능하다.   stl 컨테이너set, map과 같은 associative container의 경우 red-black tree 기반으로 노드 검색/삽입/삭제 O(log$n$)이다.자동으로 정렬되지 않는 unordered_set, unordered_map은 해시 기반으로 노드 검색/삽입/삭제 O(1)이다.

  Read More