알고리즘!/Graph25 [C/C++] 백준 20040: 사이클 게임 (Union-Find) https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 해설! 이 문제는 최소 스패닝 트리를 구하기 위해서 필요한 연산인 Union-Find를 이용하면 쉽게 풀리는 문제였다. 이 문제를 Map이나 c++ 내부에 있는 자료구조를 이용하여 풀 경우에는 사실상 해결이 불가능한데 그 이유는 점의 개수가 최대 500,000개이며 진행되는 연산이 최대 1,000,000이기 때문이다. 그렇기 때문에 Union-find를 이용하여 그 연산시간이 O(logn) .. 2023. 10. 12. [C/C++] 백준 2252: 줄 세우기 (위상정렬) https://www.acmicpc.net/problem/2252 2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 이 문제를 풀기 위해서는 위상 정렬에 대한 이해가 필요하다! 위상 정렬? 위상 정렬은 사이클이 없는 방향 그래프의 모든 노드를 방향성에 거스르지 않도록 순서대로 나열하는 것을 의미하며 정렬 알고리즘의 일종이다. 위 문제와 같이 1은 3보다 먼저 와야하고 2는 3보다 먼저 들어와야 한다는 방향성이 있을 때 사용 가능하는 알고리즘이다. 따라서 위상 정렬의 결.. 2023. 10. 11. [C/C++] 백준 1197: 최소 스패닝 트리 (Kruskal 알고리즘) https://www.acmicpc.net/problem/1197 1197번: 최소 스패닝 트리 첫째 줄에 정점의 개수 V(1 ≤ V ≤ 10,000)와 간선의 개수 E(1 ≤ E ≤ 100,000)가 주어진다. 다음 E개의 줄에는 각 간선에 대한 정보를 나타내는 세 정수 A, B, C가 주어진다. 이는 A번 정점과 B번 정점이 www.acmicpc.net 최소 스패닝 트리는 크게 프림의 알고리즘과 크루스칼 알고리즘을 통해 구현이 가능하다. 이 문제에서는 크루스칼 알고리즘을 이용하여 최소 스패닝 문제를 해결했다! 크루스칼(Kruskal 알고리즘)? 크루스칼 알고리즘의 가장 기본적인 아이디어는 사이클이 만들어지지 않는 한에서 간선을 가중치의 오름차순으로 정렬한 뒤, 스패닝 트리에 하나씩 추가하는 것이다. .. 2023. 10. 10. [C/C++] 백준 5639: 이진 검색 트리 (backtrack을 통한 후위순회) https://www.acmicpc.net/problem/5639 5639번: 이진 검색 트리 트리를 전위 순회한 결과가 주어진다. 노드에 들어있는 키의 값은 106보다 작은 양의 정수이다. 모든 값은 한 줄에 하나씩 주어지며, 노드의 수는 10,000개 이하이다. 같은 키를 가지는 노드는 없다 www.acmicpc.net 풀이!! 맨 처음에는 괄호를 이용한 후위 표기식 문제와 같이 stack에 넣음으로써 문제를 해결하려고 했지만 그렇게 할 경우 코드가 너무 복잡해지고 구현할 수가 없어 다른 방법을 모색하였다. 전위 순회의 특성상 루트-왼쪽 자식-오른쪽 자식 순으로 이동하기 때문에 전체의 루트를 하나만 잡았을 때 배열이 루트(1)-왼쪽자식 (n개)-오른쪽 자식(m)개가 된다. 예를 들어 50 30 24 .. 2023. 9. 26. 이전 1 2 3 4 ··· 7 다음
