분리 집합(Disjoint Set, Union-Find)은 많은 알고리즘 코딩 테스트에서 중요한 자료구조로 나타납니다. 분리 집합은 여러 노드가 서로 중복되지 않는 집합으로 나뉘어 있을 때, 각 집합을 대표하는 노드 하나를 선택해 그 집합을 대표하도록 구성합니다. 분리 집합의 주요한 사용 용도는 다음과 같습니다: 사이클 판별: 주로 그래프에서 사이클이 있는지 확인할 때 사용됩니다. 간선을 하나씩 추가하면서 두 노드의 루트 노드가 같다면 사이클이 생성되는 것입니다. Kruskal 알고리즘에서 최소 신장 트리를 구할 때 사이클 확인 용도로 사용됩니다. 집합의 병합 및 찾기 연산: 두 집합을 하나로 합치거나, 어떤 원소가 어떤 집합에 속하는지 찾을 때 사용됩니다. 네트워크 연결: 여러 네트워크가 연결되어 있을..

https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 풀이 사이클이 생기는지에 대해서 확인해보는 문제. - BFS는 간선을 추가한 그래프를 처음부터 계속 탐색해야하기에 부담이 크다. - 분리 집합을 사용해서 사이클이 생기는지 확인하도록 했다. 분리집합 알고리즘 https://sunghyun98.tistory.com/256 [알고리즘] 분리 집합 분리 집합(Disjoint Set, Union-Find)은 많은 알고리즘 코딩 테스트에서 중요한 자료..

https://www.acmicpc.net/problem/2473 2473번: 세 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 3 이상 5,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 www.acmicpc.net 풀이 투포인터 문제인 용액 시리즈이다. 3개의 용액의 값을 합한 값이 최대한 0에 가깝게 나오도록 용액을 고른 뒤. 값을 오름차순으로 출력하는것이 문제의 목표이다. 1개의 용액은 완전탐색을 통해서 뽑고 나머지 2개의 용액은 투 포인터로 뽑아줄 것이다. 투 포인터 알고리즘 https://sunghyun98.tistory.com/25 [알고리즘] 투 포인터 투 포인터 알고리즘은 ..

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 풀이 조건을 다시 정리하자면 1) 문제 번호는 낮을수록 쉬운 문제이다. 최대한 쉬운 문제를 먼저 풀면서 모든 문제를 풀어야한다. 2) 최대한 쉬운 문제를 먼저 푼다는 얘기는 문제번호가 내림차순으로 풀어야하는 조건이 주어질 수 있다는 얘기이다. - 진입차수가 존재하는 노드가 있다는 얘기이다. 3) 진출차수와 진입차수가 존재하지않는 노드와 진출차수는 존재하지만 진입차수가..

https://www.acmicpc.net/problem/2470 2470번: 두 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 주어진다. 이 수들은 모두 -1,000,000,000 이상 1,000,00 www.acmicpc.net 풀이 투 포인터 알고리즘을 사용해서 풀어주었습니다. 정렬되지않은 용액의 값들이 입력값으로 주어지기에 .sort()를 이용해서 정렬해주었습니다. 투 포인터 알고리즘 https://sunghyun98.tistory.com/25 [알고리즘] 투 포인터 투 포인터 알고리즘은 배열에서 두 개의 포인터를 사용하여 특정 목표를 달성하기 위한 기법입니다. 일반적으로 정렬된 배열..

https://www.acmicpc.net/problem/2467 2467번: 용액 첫째 줄에는 전체 용액의 수 N이 입력된다. N은 2 이상 100,000 이하의 정수이다. 둘째 줄에는 용액의 특성값을 나타내는 N개의 정수가 빈칸을 사이에 두고 오름차순으로 입력되며, 이 수들은 모두 - www.acmicpc.net 풀이 투 포인터 알고리즘으로 문제를 풀어주었습니다. 정렬된 용액의 값들이 들어오기에 따로 정렬해줄 필요는 없습니다. 투포인터 알고리즘 https://sunghyun98.tistory.com/25 [알고리즘] 투 포인터 투 포인터 알고리즘은 배열에서 두 개의 포인터를 사용하여 특정 목표를 달성하기 위한 기법입니다. 일반적으로 정렬된 배열에서 특정 조건을 충족하는 요소를 찾거나 연속된 서브 배열..

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 풀이 위상정렬 알고리즘은 다음과 같다. https://sunghyun98.tistory.com/249 [알고리즘] 위상 정렬 위상 정렬은 방향 그래프의 모든 노드를 방향성을 거스르지 않게 순서대로 나열하는 것입니다. 즉, 어떤 작업을 먼저 해야 다른 작업을 할 수 있는 상황과 같은 "의존성"을 갖는 문제를 표현하고 sunghyun98.tistory.com..

위상 정렬은 방향 그래프의 모든 노드를 방향성을 거스르지 않게 순서대로 나열하는 것입니다. 즉, 어떤 작업을 먼저 해야 다른 작업을 할 수 있는 상황과 같은 "의존성"을 갖는 문제를 표현하고 해결할 때 사용됩니다. 위상 정렬의 전제와 조건 방향 그래프: 위상 정렬은 방향성을 가진 간선으로 이루어진 그래프에서만 수행됩니다. 사이클이 없어야 함: 위상 정렬을 수행할 그래프는 순환이 없어야 합니다. 순환이 있는 경우, 어떤 노드를 먼저 방문해야 하는지 정할 수 없기 때문입니다. 위상 정렬 설명 진입 차수 계산: 각 노드의 진입 차수(들어오는 간선의 수)를 계산합니다. 진입 차수가 0인 노드 찾기: 진입 차수가 0인 노드를 찾고 큐에 넣습니다. 이 노드들은 의존성이 없는 작업이므로 먼저 수행될 수 있습니다. 노..