분류 전체보기242 [백준] 1202: 보석 도둑 - JAVA https://www.acmicpc.net/problem/1202 풀이가방의 용량이 정해져있고, 가방에는 보석을 한개씩 넣을 수 있다. 즉, 가방을 오름차순으로 보면서 넣을 수 있는 보석 중 가치가 가장 큰것을 넣으면서 진행한다. 가방을 오름차순으로 정렬하고 가방의 사이즈보다 보석의 무게가 작다면 우선순위큐에 넣고 우선순위큐에서 위의 것을 빼면 되도록 구현했다. 메모리: 115988KB시간: 1888ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Node { int m; int v; public Node(int m, int v) { this.m .. 2024. 5. 14. [백준] 11066: 파일 합치기 - JAVA https://www.acmicpc.net/problem/11066 풀이파일을 1번부터 K번까지 합쳐야하는데 합치는 순서를 다르게 하여 최소 비용을 구해야 한다. 각 파일마다 비용을 입력받으면서 누적합으로 저장을 했다.(sum[5]는 1~5까지의 누적합) dp배열을 만들어 저장을 하는데 dp[x][y]는 x~y까지 파일을 합치는 최소 비용을 갱신하며 저장한다. x와 y의 차이를 gap으로 하여 gap을 1부터 늘려가면서 계산한다. gap안에서 x와 y의 사이값d를 잡아 x~d, d+1~y의 합과 누적합배열에서 x~y를 찾아 최소비용을 갱신한다. 1~K를 나타내는 dp[1][K]가 답이된다. 메모리: 32180KB시간: 552ms언어: Java 11import java.io.*;import java.ut.. 2024. 5. 14. [백준] 11049: 행렬 곱셈 순서 - JAVA https://www.acmicpc.net/problem/11049 풀이행렬이 여러개 주어지고 어떤 순서로 곱을 했을 때 연산이 최소가 되는지 구하는 문제이다. AxB인 행렬과 BxC인 행렬을 곱할 때 필요한 연산의 횟수는 AxBxC이다. 행렬 A, B, C가 있을 때 각각 0, 1, 2의 번호라고 하면 dp[1][2]는 BxC의 횟수, dp[0][2]는 AxBxC의 횟수를 저장했다. 메모리: 17736KB시간: 256ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = ne.. 2024. 5. 14. [백준] 2410: 2의 멱수의 합 - JAVA https://www.acmicpc.net/problem/2410 풀이dp문제. dp[0], dp[1]을 1로 초기화하고 dp배열을 채운다. dp[i] = dp[i-2] + dp[i/2] 의 점화식으로 진행한다. 메모리: 22032KB시간: 148ms언어: Java 11import java.io.*;public class Main { private static final int MOD = 1_000_000_000; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = I.. 2024. 5. 13. [백준] 1655: 가운데를 말해요 - JAVA https://www.acmicpc.net/problem/1655 풀이숫자를 입력할 때마다 말했던 숫자들 중 중간값을 말해야한다. PriorityQueue 2개를 사용해 left, right로 저장하고 left의 peek이 항상 중간값이 되도록 구현했다. 따라서, left는 내림차순으로 저장 및 출력했다. left가 비어있거나 left의 peek보다 말한 숫자가 작으면 left에 넣었다. 그렇지 않은 경우는 right에 넣는다. left 크기와 right 크기의 차이가 1보다 크면 left에서 빼서 right에 넣어주고, right의 크기가 더 크면 right에서 빼서 left에 넣어주었다. 즉, left의 크기와 right의 크기의 차이가 0, 1이 되도록 유지했다. 그렇게해서 left의 peek값이 .. 2024. 5. 13. [백준] 15681: 트리와 쿼리 - JAVA https://www.acmicpc.net/problem/15681 풀이트리에 속한 간선의 정보가 주어지고, 루트의 번호가 주어진다. 트리의 정점을 포함해 자신보다 하위에 있는 정점들의 개수를 구하는 문제이다. 먼저 간선의 정보를 인접리스트에 담았다. 루트의 번호부터 dfs탐색을 통해 진행하는데 정점의 개수의 최대값이 크다보니 매번 구하면 시간 초과가 발생할 것 같았다. dp배열을 만들어 dfs탐색을 하며 dp에 저장하고 반환하는 식으로 구현했다. 메모리: 77800KB시간: 812ms 언어: Java 11import java.io.*;import java.util.*;public class Main { static ArrayList> tree; static int[] dp; stati.. 2024. 5. 13. [백준] 2146: 다리 만들기 - JAVA https://www.acmicpc.net/problem/2146 풀이그래프 탐색 문제. 서로 다른 두 개의 섬을 연결하는 다리의 최솟값을 구해야 한다. 섬은 1, 바다는 0으로 주어져서 섬들을 구분하기 위한 작업을 우선 거쳤다. 섬마다 번호를 하나씩 부여하고 bfs탐색을 통해 해당 번호를 마킹했다. 그 후 섬들끼리 거리를 bfs탐색을 통해 구했다. 처음 제출에 메모리 초과가 났었다. 섬을 구분하는 함수를 구현할 때 번호가 다른 것으로 방문처리가 된다고 생각하여 방문처리하는 boolean배열을 따로 만들지 않았는데, 방문처리 배열을 도입하여 쓸데없는 동작을 제거해주니 메모리초과가 해결되었다. 메모리: 295940KB시간: 1456ms언어: Java 11import java.io.*;import java.. 2024. 5. 13. [백준] 1005: ACM Craft - JAVA https://www.acmicpc.net/problem/1005 풀이위상정렬을 이용해 건물을 건설하는 시간을 구하는 문제. 어떤 건물을 짓기 위해 우선적으로 지어져야 할 건물이 있다. 특정 번호의 앞에 지어져야할 건물이 여러개가 있다면 그중 가장 오래걸리는 것이 끝난 후 지을 수 있게 된다. 따라서 걸리는 시간을 오름차순으로 하기 위해 우선순위큐를 이용했다. 목표한 건물에 도달했으면 시간을 출력하면 끝. 메모리: 245956KB시간: 864ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Node implements Comparable { int num; int time; .. 2024. 5. 13. [백준] 13418: 학교 탐방하기 - JAVA https://www.acmicpc.net/problem/13418 풀이MST를 구해 오르막길의 개수를 찾는 문제였다. 오르막길을 가중치가 0, 내리막길은 1로 주어지는데 오르막길을 최대로 이용한 경우, 최소로 이용한 경우를 각각 구해야 한다. 오르막길의 가중치가 0이므로 가중치가 작은순으로 프림 알고리즘을 구현하면 최대로 이용한 개수를 구할 수 있고, PriorityQueue의 정렬 조건을 내림차순으로 해주면 오르막길을 최소로 이용한 개수를 구할 수 있다. 메모리: 191972KB시간: 1292ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Node { int point; .. 2024. 5. 13. [백준] 1774: 우주신과의 교감 - JAVA https://www.acmicpc.net/problem/1774 풀이최소 신장 트리를 구하는 문제이다. 정점을 다 연결해야 하는데 이미 연결된 선이 주어진다. 이미 연결된 선은 가중치를 0으로 두고 계산했다. 크루스칼과 프림 알고리즘이 있는데 프림 알고리즘을 사용해봤다. 프림 알고리즘은 하나의 정점에서 연결된 간선들 중에서 하나씩 선택하면서 최소신장트리를 찾는 알고리즘이다 1. 임의 정점을 하나 선택해서 시작한다. 2. 선택한 정점과 인접하는 정점들 중 최소 비용의 간선과 연결된 정점을 선택한다. 3. 모든 정점이 선택될때까지(정점의 개수 - 1개의 간선이 선택될때까지) 1, 2번과정을 반복한다. pq에 방문하지 않은 점들을 넣고 가중치가 작은 순으로 PriorityQueue를 이.. 2024. 5. 13. 이전 1 ··· 15 16 17 18 19 20 21 ··· 25 다음