Computer Science/Algorithm

[C/C++] Topology Sort (graph)

백준 14567문제 #include #include #include using namespace std; #define PS_INPUT cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false) #define endl '\n' #define INF 1e9 #define pii pair #define ll long long #define SIZE 1001 int n, m; int inDegree[SIZE]; vector graph[SIZE]; int result[SIZE]; queue q; void initInput() { cin >> n >> m; int a, b; for (int i = 0; i > a >> b; gr..

[C/C++] kruskal algorithm (MST)

백준 1197문제 #include #include #include #include using namespace std; #define PS_INPUT cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false) #define endl '\n' #define INF 1e9 #define pii pair #define ll long long #define SIZE 10001 int V, E; bool check; ll ans; int parent[SIZE]; vector graph; void initInput() { cin >> V >> E; for (int i = 1; i > a >> b >> c; graph.push_back({c, a, b}); } ..

[C/C++] prim algorithm (MST)

백준 1197 문제 #include #include #include #include using namespace std; #define PS_INPUT cout.tie(NULL); cin.tie(NULL); ios_base::sync_with_stdio(false) #define endl '\n' #define INF 1e9 #define pii pair #define ll long long #define SIZE 10001 int V, E; bool visited[SIZE]; ll ans; vector graph[SIZE]; priority_queue pq; void initInput() { cin >> V >> E; int a, b, c; for (int i = 0; i < E; i++) { cin ..

[C/C++] 에라토스테네스의 체

에라토스테네스의 체 알고리즘은 여러 개의 수가 소수인지 아닌지를 판별할 때 사용하는 대표적인 알고리즘이다. 에라토스테네스의 체는 n보다 작거나 같은 모든 소수를 찾을 때 사용할 수 있다. 알고리즘은 다음과 같다. 2부터 n까지 모든 자연수를 나열한다. 남은 수 중에서 아직 처리하지 않은 가장 작은 수 i를 찾는다. 남은 수 중에서 i의 배수를 모두 제거한다.(i는 제거하지 않음) 더 이상 반복할 수 없을 때까지 2번, 3번을 반복한다. 위 과정을 사진과 함께 보자. 1번 과정) 2부터 n(26)까지 모든 자연수를 나열한다. 2번, 3번 과정) 남은 수 중에서 가장 작은 수 i(2)를 찾고 i의 배수를 모두 제거한다. 2번, 3번 과정) 남은 수 중에서 가장 작은 수 i(3)를 찾고 i의 배수를 모두 제거..

[C/C++] BFS(Breadth-First Search)

BFS(Breadth-First Search, 너비 우선 탐색)는 가까운 노드를 먼저 탐색하는 그래프 순회 알고리즘이다. 그래프 탐색(Search)은 임의의 한 노드를 시작으로 다른 노드들을 방문하는 것을 말한다. 그래프 탐색 알고리즘을 알아보기 전에 그래프를 다루는 방법을 알아보자. 그래프는 노드(Node 혹은 정점, Vertex)와 간선(Edge)으로 표현된다. 프로그래밍에서 그래프를 표현하는 방식은 크게 2가지 방식이 있다. 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 graph[i][j]와 같이 노드간의 연결 관계를 빠르게 알 수 있다. 노드 간의 모든 연결 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비된다. 인접 리스트(Adj..

[C/C++] DFS(Depth-First Search)

DFS(Depth-First Search, 깊이 우선 탐색)는 그래프의 깊은 부분을 먼저 탐색하는 그래프 순회 알고리즘이다. 그래프 탐색(Search)은 임의의 한 노드를 시작으로 다른 노드들을 방문하는 것을 말한다. 그래프 탐색 알고리즘을 알아보기 전에 그래프를 다루는 방법을 알아보자. 그래프는 노드(Node 혹은 정점, Vertex)와 간선(Edge)으로 표현된다. 프로그래밍에서 그래프를 표현하는 방식은 크게 2가지 방식이 있다. 인접 행렬(Adjacency Matrix) : 2차원 배열로 그래프의 연결 관계를 표현하는 방식 graph[i][j]와 같이 노드간의 연결 관계를 빠르게 알 수 있다. 노드 간의 모든 연결 관계를 저장하므로 노드 개수가 많을수록 메모리가 불필요하게 낭비된다. 인접 리스트(A..