백준

1516번: 게임 개발 첫째 줄에 건물의 종류 수 N(1 ≤ N ≤ 500)이 주어진다. 다음 N개의 줄에는 각 건물을 짓는데 걸리는 시간과 그 건물을 짓기 위해 먼저 지어져야 하는 건물들의 번호가 주어진다. 건물의 번호는 1부 www.acmicpc.net 문제 여러개의 건물이 있을 때 각 건물은 다른 건물이 지어져야 하는 요구사항이 있다. N개의 각 건물이 완성되기까지 걸리는 최소 시간을 출력한다. 풀이 이 문제는 건물이 앞에있는 건물들이 지어졌을 때, 지을 수 있는 건물들이 있다. 따라서 위상정렬을 통해 노드들을 제거해나가면서 시간을 계산하면 된다. 📌 입력 ArrayList[] A = new ArrayList[N]; int[] D = new int[N]; int[] time = new int[N];..

2252번: 줄 세우기 첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의 www.acmicpc.net 문제 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오. 풀이 1번 학생이 3번학생보다 먼저 앞에 서야한다. 이런 식으로 값이 주어지기 때문에 1번 학생을 먼저 출력하고 3번학생을 출력한다. 즉, 위상정렬과 일치한다. 그리고 답이 여러가지라는 의미도 위상정렬을 의미한다. 📌 입력 for(int i=0; i

1043번: 거짓말 지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 www.acmicpc.net 문제 여러 파티에 참여할 때 진실을 알고 있는 사람과 진실을 알고있는 사람과 파티를 하는 사람을 피해 과장된 이야기를 할 수 있는 파티의 최대 수를 구하여라. 풀이 📌 유니온 파인드 static void union(int a, int b){ int x = find(a); int y = find(b); A[y] = x; } static int find(int a){ if(A[a] == a){ return a; }else{ A[a] = find(A[a]); return A[a..

1976번: 여행 가자 동혁이는 친구들과 함께 여행을 가려고 한다. 한국에는 도시가 N개 있고 임의의 두 도시 사이에 길이 있을 수도, 없을 수도 있다. 동혁이의 여행 일정이 주어졌을 때, 이 여행 경로가 가능한 것인 www.acmicpc.net 문제 도시의 개수가 주어지고 각 도시들이 연결되어 있는지 여부가 주여졌을 때 가려고 하는 여행지를 모두 갈 수 있는지 여부를 출력하시오. 풀이 📌 유니온 파인드 static void union(int a, int b){ int x = find(a); int y = find(b); A[y] = x; } static int find(int a){ if(A[a] == a){ return a; }else{ A[a] = find(A[a]); return A[a]; } }..

1717번: 집합의 표현 초기에 $n+1$개의 집합 $\{0\}, \{1\}, \{2\}, \dots , \{n\}$이 있다. 여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다. 집합을 표현하는 프로그램을 작 www.acmicpc.net 문제 집합 0~N+1이 주어졌을 때 합집합 연산과 같은 집합에 속하는지 여부를 체크하여 출력하시오. 풀이 유니온 파인드를 물어보는 문제였다. 📌 입출력 StringBuilder sb = new StringBuilder(); for(int i=0; i

1707번: 이분 그래프 입력은 여러 개의 테스트 케이스로 구성되어 있는데, 첫째 줄에 테스트 케이스의 개수 K가 주어진다. 각 테스트 케이스의 첫째 줄에는 그래프의 정점의 개수 V와 간선의 개수 E가 빈 칸을 사이에 www.acmicpc.net 문제 그래프의 정점을 둘로 나누어 인접하는 정점끼리는 다른 집합에 속하게 분리할 수 있을 때 이분 그래프라고 한다. 주어진 그래프가 이진 그래프인지 판별하여 출력하시오. 풀이 각 정점들을 BFS로 탐색하면서 2가지 “1”과 “-1” 집합으로 담고 인접한 정점이 자신의 집합과 같다면 NO를 출력하도록 구현하였다. 📌 BFS public static void BFS(int start){ Queue q = new LinkedList(); binary[start] = ..

18352번: 특정 거리의 도시 찾기 첫째 줄에 도시의 개수 N, 도로의 개수 M, 거리 정보 K, 출발 도시의 번호 X가 주어진다. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) 둘째 줄부터 M개의 줄에 걸쳐서 두 개 www.acmicpc.net 문제 단방향 도로가 있는 도시들이 있고 출발지가 주어졌을 때 거리가 K인 도시를 모두 출력하시오. 풀이 출발지로부터 깊이를 구하는 문제라고 생각했고 BFS를 통해 문제를 풀었습니다. 입력 for(int i=0; i K) break; } } now값의 depth를 다음 노드에 추가하여 depth들을 만들었습니다. 속도를 더 빠르게 하기 위해서 현재 노드의 depth값이 K보다 커지면 종료했습니..

문제 두 수가 주어졌을 때 최소 공배수를 구하여라. 풀이 이 문제는 최소 공약수로 최대 공배수를 구하는 공식을 사용하여 풀었습니다. 위의 공식으로 해결할 수 있습니다. 최대 공약수, gcd() private static int gcd(int a, int b){ if(a % b == 0) return b; else{ return gcd(b, a%b); } } 유클리드 호제법을 사용하여 재귀 함수로 만들었습니다. a % b = c b % c = d … 를 반복하여 나머지가 0이나왔을 때 b가 최소 공약수가 됩니다. 전체 코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import jav..