목록분류 전체보기 (60)

쫑쫑이의 블로그

백준 1766 문제집 Java [위상정렬, 우선순위 큐]

https://www.acmicpc.net/problem/1766 1766번: 문제집 첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 M(1 ≤ M ≤ 100,000)이 주어진다. 둘째 줄부터 M개의 줄에 걸쳐 두 정수의 순서쌍 A,B가 빈칸을 사이에 두고 주 www.acmicpc.net 위상정렬과 우선순위큐를 사용해서 풀이하면 된다 입력 값에 맞게 가중치를 추가해주고 1부터 N까지 가중치가 0인 값만 우선순위큐에 넣어준 후 우선순위큐에서 하나씩 꺼내면서 출력값에 추가하고 꺼낸 값이 방문할 수 있는 문제 번호의 가중치를 감소하고 가중치가 0이 되면 우선순위큐에 넣는 과정을 반복한다 import java.io.*; import java.util.*; p..
알고리즘/백준 2022. 11. 8. 22:09
백준 1005 ACM Craft Java [위상정렬]

https://www.acmicpc.net/problem/1005 1005번: ACM Craft 첫째 줄에는 테스트케이스의 개수 T가 주어진다. 각 테스트 케이스는 다음과 같이 주어진다. 첫째 줄에 건물의 개수 N과 건물간의 건설순서 규칙의 총 개수 K이 주어진다. (건물의 번호는 1번부 www.acmicpc.net 위상정렬을 사용해서 풀이하는데 가중치를 줄일 때마다 건설시간 누적값을 저장한 배열을 비교해줘야한다 각 노드 별 가중치는 0 1 1 2가 되고, 건설시간 누적값은 모두 0으로 초기화 해둔다 2가 완료될 때 건설시간 누적값 11(10 + 1)을 4의 건설시간 누적값 0과 비교해서 최대값 11을 넣고 3이 완료될 때 건설시간 누적값 110(10 + 100)을 4의 건설시간 누적값 11과 비교해서 ..
알고리즘/백준 2022. 11. 7. 23:32
백준 2623 음악프로그램 Java [위상정렬]

https://www.acmicpc.net/problem/2623 2623번: 음악프로그램 첫째 줄에는 가수의 수 N과 보조 PD의 수 M이 주어진다. 가수는 번호 1, 2,…,N 으로 표시한다. 둘째 줄부터 각 보조 PD가 정한 순서들이 한 줄에 하나씩 나온다. 각 줄의 맨 앞에는 보조 PD가 담당한 www.acmicpc.net 위상 정렬을 사용해서 문제를 풀이했다 입력을 예시로 들면 3 1 4 3 일때 3은 뒤에 숫자니까 넘어가고 1 4 3을 각각 다음 나오는 숫자를 tree의 자식노드처럼 추가해뒀다 1의 자식노드 4, 4의 자식노드 3 자식노드를 추가할 때 자식노드들에 가중치를 1씩 줬다 다음 입력들도 마찬가지로 과정을 반복하고나서 가중치가 0인 노드들부터 큐에 넣고 큐에서 한개씩 빼고 카운트하면서..
알고리즘/백준 2022. 11. 6. 15:16
백준 1647 도시 분할 계획 Java [최소스패닝트리, 프림]

https://www.acmicpc.net/problem/1647 1647번: 도시 분할 계획 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2이상 100,000이하인 정수이고, M은 1이상 1,000,000이하인 정수이다. 그 다음 줄부터 M줄에 걸쳐 길의 정보가 A B C 세 개의 정수로 주어지는데 A번 www.acmicpc.net 최소 신장 트리(MST) 문제이다 문제 조건에서 2개의 마을로 분리한다고 했기 때문에 전체 가중치를 구하고 가중치 중에서 가장 큰 값을 빼주면 된다 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { B..
알고리즘/백준 2022. 10. 27. 20:25
백준 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 최소 스패닝 트리(MST)는 최소 신장 트리라고도 하며, 풀이 방법은 2가지 있다 1. 크루스칼 알고리즘 2. 프림 알고리즘 크루스칼 알고리즘은 트리의 간선 중에서 가장 짧은 간선을 고르고 사이클이 생기는지 확인 후 가중치에 더하는 과정을 반복한다 프림 알고리즘은 한 정점에서 시작해서 방문하지 않은 정점으로 갈 수 있는 간선 중에 가장 짧은 간선을 선..
알고리즘/백준 2022. 10. 27. 00:46
백준 1202 보석 도둑 Java [그리디, 우선순위큐]

https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 보석과 가방이 300000개로 NlogN 시간복잡도 안에 처리해야한다 결과값은 최대가치 X N의 최대값 = 100만 x 30만 으로 long타입으로 선언해야한다 가방에 넣을 보석을 찾기 위해 우선순위큐에 가치 기준으로 넣어 줬다 가방의 갯수 체크를 위한 HashMap과 가방 무게 정렬 및 조회, 삭제를 위한 TreeSet 2개의 자료구조..
알고리즘/백준 2022. 10. 24. 23:58
이전 Prev 1 ··· 3 4 5 6 7 8 9 10 Next 다음