목록알고리즘/백준 (45)

쫑쫑이의 블로그

백준 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
백준 17404 RGB거리 2 Java [DP]

https://www.acmicpc.net/problem/17404 17404번: RGB거리 2 첫째 줄에 집의 수 N(2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄부터 N개의 줄에는 각 집을 빨강, 초록, 파랑으로 칠하는 비용이 1번 집부터 한 줄에 하나씩 주어진다. 집을 칠하는 비용은 1,000보다 작거나 www.acmicpc.net 저번에 풀었던 RGB거리 문제와 비슷하지만 N번 집과 1번 집이 다른 색으로 칠해져야하는 조건이 추가됐다 첫번째 집에 칠하는 색에 따라 dp를 따로 해서 마지막 줄에서 다른 색 비용을 더한 값 중에서 최소값들을 비교해주면 된다 첫 두줄을 미리 계산하고 다음 줄부터 dp를 해줬다 import java.io.*; import java.util.*; public class ..
알고리즘/백준 2022. 10. 23. 21:01
백준 14003 가장 긴 증가하는 부분 수열 5 Java [LIS]

https://www.acmicpc.net/problem/14003 14003번: 가장 긴 증가하는 부분 수열 5 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) www.acmicpc.net 문제 접근법은 이전에 푼 문제들과 동일하지만 부분 수열을 출력해야한다 A의 요소마다 인덱스값을 저장하는 배열을 만들고 뒤에서부터 값을 하나씩 줄여가면서 size 크기의 배열을 만든다 앞에서부터 만들면 다음 값이 작아지는 구간에 대처하기가 힘들다 뒤에서부터 접근하면 size가 8일때 최초로 등장하는 8미만의 수를 배열에 담아서 출력하면 된다 import java.io...
알고리즘/백준 2022. 10. 22. 16:20
이전 Prev 1 2 3 4 5 6 7 8 Next 다음