코딩 테스트/Java26 [백준/Java] 1717 집합의 표현 : 유니온 파인드 1) union 연산 - 각 노드가 속한 집합을 1개로 합치는 연산이다. 노드 a, b가 a ∈ A, b ∈ B일 때 union(a, b)는 A ∪ B를 말한다. 2) find 연산 - 특정 노드 a에 관해 a가 속한 집합의 대표 노드를 반환하는 연산이다. 노드 a가 a ∈ A일 때 find(a)는 A 집합의 대표 노드를 반환한다. - 그래프를 정돈하고 시간 복잡도를 향상시킨다. - find 연산의 작동 원리 1) 대상 노드 배열에 index와 value 값이 동일한지 확인 2) 동일하지 않으면 value 값이 가리키는 index 위치로 이동 3) 이동 위치의 index 값과 value 값이 같을 때까지 1~2번 반복, 반복이므로 이 부분은 재귀 함수로 구현 4) 대표 노드에 도달하면 재귀 함수를 빠져나.. 2023. 4. 12. [백준/Java] 1929 소수 구하기 : 에라토스테네스의 체 문제 M이상 N이하의 소수를 모두 출력하는 프로그램을 작성하시오. 입력 첫째 줄에 자연수 M과 N이 빈 칸을 사이에 두고 주어진다. (1 ≤ M ≤ N ≤ 1,000,000) M이상 N이하의 소수가 하나 이상 있는 입력만 주어진다. 출력 한 줄에 하나씩, 증가하는 순서대로 소수를 출력한다. - 에라토스테네스의 체 원리 1) 구하고자 하는 소수의 범위만큼 1차원 배열을 생성한다. 2) 2부터 시작하고 현재 숫자가 지워지지 않을 때는 현재 선택된 숫자의 배수에 해당하는 수를 배열에서 끝까지 탐색하면서 지운다. 이때 처음으로 선택된 숫자는 지우지 않는다. 3) 배열의 끝까지 2번을 반복한 후 배열에서 남아 있는 모든 수를 출력한다. public static void main(String[] args) {// .. 2023. 4. 12. [백준/Java] 1260 DFS와 BFS 문제 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다. 입력 첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다. 출력 첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다. .. 2023. 4. 12. [백준/Java] 11724 연결 요소의 개수 구하기 : DFS(깊이 우선 탐색) 문제 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오. 입력 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다. 출력 첫째 줄에 연결 요소의 개수를 출력한다. import java.io.*; import java.util.*; public class Main{ static ArrayList[] arr;// 그래프 데이터 저장 리스트(ArrayList: 크기가 가변인 배열) static boolean visited[];// 각 노드 방.. 2023. 4. 12. [백준/Java] 2750 수 정렬하기 : 버블 정렬(2가지 방법) 문제 N개의 수가 주어졌을 때, 이를 오름차순으로 정렬하는 프로그램을 작성하시오. 입력 첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 수가 주어진다. 이 수는 절댓값이 1,000보다 작거나 같은 정수이다. 수는 중복되지 않는다. 출력 첫째 줄부터 N개의 줄에 오름차순으로 정렬한 결과를 한 줄에 하나씩 출력한다. 1. sort() 사용 - 버블 정렬 X import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int arr[] = new int[n]; for (int i .. 2023. 4. 11. [백준/Java] 1253 좋다 : 투 포인터 알고리즘 문제 N개의 수 중에서 어떤 수가 다른 수 두 개의 합으로 나타낼 수 있다면 그 수를 “좋다(GOOD)”고 한다. N개의 수가 주어지면 그 중에서 좋은 수의 개수는 몇 개인지 출력하라. 수의 위치가 다르면 값이 같아도 다른 수이다. 입력 첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수) 출력 좋은 수의 개수를 첫 번째 줄에 출력한다. - A[i] + A[j] > K : j--; - A[i] + A[j] N : sum = sum - start_index; s.. 2023. 4. 11. 이전 1 2 3 4 5 다음 반응형
