コーディングテスト合格者になる：C++編を精読する

그래프 미션제출

인접행렬은 노드 수가 늘어날수록 메모리 크기가 제곱으로 늘어나고, 인접리스트는 노드의 개수와 간선의 수를 합친만큼만 메모리를 차지한다. 1.2. DFS: 스택을 사용해서 현재 노드에서 이동 가능한 경로를 전부 스택에 넣고, 가장 마지막에 넣은 노드를 스택에서 하나씩 경로를 빼면서 이동 BFS: 큐를 사용해서 현재 노드에서 이동 가능한 경로를 전부 큐에 넣고, 가장 먼저 넣은 노드부터 하나씩 빼면서 이동   2.1. #include <vector> #include <algorithm> using namespace std; vector<vector<int>> solution(int n, vector<vector<int>> edges) { vector<vector<int>> answer(n + 1); for(auto& edge : edges) { int u = edge[0]; int v = edge[1]; answ

김경민 · 그래프

拍手 0 · コメント 1

집합 미션제출

부모노드의 인덱스를 저장한다 1.2. 매번 부모 노드를 하나씩 찾아가지 않도록 탐색하는 경로의 모든 노드의 parent값을 루트로 갱신하는 기법이다.   2.1. #include <vector> using namespace std; int parent[1001]; int Find(int x) { if (parent[x] != x) parent[x] = Find(parent[x]); return parent[x]; } void Union(int a, int b) { a = Find(a); b = Find(b); parent[a] = b; } vector<bool> solution(int n, vector<vector<int>> operations) { vector<bool> answer; for (int i = 0; i <= n; i++) parent[i] = i; for (auto& ar

김경민 · 집합

拍手 0 · コメント 1

해시 미션제출

키를 고정된 정수로 변환시키는 함수 1.2. 체이닝: 충돌이 발생한 데이터를 같은 슬롯에 linked list로 연결한다 개방 주소법: 충돌이 발생했을 때 다른 인덱스에 데이터를 저장한다 1.3. map: (자료구조: red-black tree), (탐색 시간복잡도: O(logn)) unordered_map: (자료구조: hash table), (탐색 시간복잡도: O(1)) 정렬이 필요없고 빠른 검색이 중요하다면 unordered_map을 써야한다   2.1. #include <string> #include <vector> #include <unordered_set> using namespace std; vector<bool> solution(vector<string> id_list, vector<string> try_list) { vector<bool> answer; unordered_set<string> id_set(id_list.begin(), id_li

김경민 · 해시

拍手 0 · コメント 1