개발/코딩테스트30 백준 1197번: 최소 스패닝 트리 [JAVA] 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 풀이 최소 신장 트리는 크루스칼 알고리즘과 프림 알고리즘으로 해결할 수 있다. 나는 그 중 크루스칼 알고리즘을 풀었다. Edge 클래스를 만들어 각 간선의 정점, 가중치 값을 담고 가중치 오름차순으로 정렬했다. 가중치가 작은 것부터 시작해서 간선이 잇는 두 정점이 같은 그룹이 아니라면 선택하는 방식이다. 두 정점이 이미 같은 그룹이라면 다시 선택했을 .. 2023. 3. 27. 백준 14621번: 나만 안 되는 연애 [JAVA] https://www.acmicpc.net/problem/14621 14621번: 나만 안되는 연애 입력의 첫째 줄에 학교의 수 N와 학교를 연결하는 도로의 개수 M이 주어진다. (2 ≤ N ≤ 1,000) (1 ≤ M ≤ 10,000) 둘째 줄에 각 학교가 남초 대학교라면 M, 여초 대학교라면 W이 주어진다. 다음 M개의 www.acmicpc.net 풀이 크루스칼 알고리즘을 이용해 최소 신장 트리를 구하되, 간선을 선택할 때 여초와 여초, 남초와 남초가 이어진 경우는 제외한다. 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.Arrays; import.. 2023. 3. 27. 백준 1325번: 효율적인 해킹 [JAVA] https://www.acmicpc.net/problem/1325 2023. 3. 27. 백준 1717번: 집합의 표현 [JAVA] https://www.acmicpc.net/problem/1717 1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 풀이 유니온 파인드 알고리즘을 쓰는 문제이다. 초기에는 0부터 n까지 각각의 숫자만 담은 집합이기 때문에, 부모 배열에 자기 자신을 넣는다. 부모를 찾는 find 함수와 두 원소의 부모를 합치는 union 함수를 만든다. find 함수의 경우, 부모노드가 자기자신인 루트노드를 찾을 때까지 재귀하는 형태이다. union함수의 경우 원소 두 개의 부모를 각각 찾아.. 2023. 3. 27. 이전 1 2 3 4 ··· 8 다음
