줌코딩의 코딩일기

문제 문제 링크 어떻게 접근할 것인가? vector로 링크드 리스트를 구현하고 bfs를 돌렸다. 코드 #include <cstdio> #include <queue> #include <vector> using namespace std; int n, m, n1, n2, answer; int* visited; vector<vector<int> > v; queue<int> q; int main(){ scanf("%d %d", &n, &m); visited = new int[n+1]; for(int i = 0; i...

문제 문제 링크 어떻게 접근할 것인가? 위상정렬을 활용해서 문제를 풀 수 있다. 여기서 중요한 점은 포인터가 아니라 벡터만으로도 충분히 링크드 리스트를 표현할 수 있다는 것이다. 위상정렬 정리 자료 포인터로 링크드 리스트 코드 #include <string> #include <cstdio> #include <queue> using namespace std; int* in; queue<int> q; struct Node { int data;...

위상 정렬(Topological Sort)이란? 여태까지 정렬 기준이 였다면 위상정렬의 정렬 기준은 ‘위상’이다. 여기서 위상이란 incoming edge의 수를 의미한다. 위상 정렬은 Directed Acyclic Graph(DAG)에서만 가능한 정렬방법이다. DAG란 각 edge가 방향을 가지고 있는데 cycle이 발생하지 않는 경우를 말한다. Cycle이 있으면 무한 루프를 발생시킬 것이다!! 보통 일의 순서를 정하는 알고리즘에서 많이 사용된다. Topological Sorting...

문제 문제 링크 어떻게 접근할 것인가? map을 이용해서 값을 각 문자의 횟수를 저장해두었다. 코드 #include <string> #include <cstdio> #include <map> #include <iostream> #include <vector> #include <algorithm> using namespace std; int main(){ vector<string> v; map<string, int> m; string s = ""; int n1, n2; scanf("%d %d", &n1, &n2); for(int i =...

문제 문제 링크 어떻게 접근할 것인가? 집합을 합하고 같은 집합인지 확인하는 문제이다. 이러한 문제는 집합의 교집합과 비교에 능한 Union-Find 알고리즘을 이용하면 뚝딱이다. 근데 강화버전을 활용한다면 훨씬 빠르게 문제를 해결할 수 있다. Union-Find 정리 자료 Union-Find 강화버전 정리 자료 코드 #include <string> #include <algorithm> #include <vector> #include <cstdio> #include <math.h> using...