본문 바로가기

Algorithm/Baekjoon208

[백준] 1915: 가장 큰 정사각형 - JAVA https://www.acmicpc.net/problem/1915 풀이1로 채워진 가장 큰 정사각형을 구하는 문제이다. 주어진 0과 1을 이차원배열에 넣고 dp배열을 만들어 채워나간다. 원래 배열의 값이 0이면 dp배열의 값도 0이 되고, 원래 배열의 값이 1이면 dp배열의 [i-1][j], [i][j-1], [i-1, j-1]값을 확인해야 한다. 저 값들 중 가장 작은 값에 1을 더해주면 현재 위치를 끝으로 하는 정사각형의 길이가 된다. 길이의 최댓값을 갱신하며 dp배열을 채우고 넓이를 구해주면 끝.  메모리: 27708KB시간: 332ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void mai.. 2024. 5. 14.
[백준] 2357: 최솟값과 최댓값 - JAVA https://www.acmicpc.net/problem/2357 풀이구간이 주어지면 그 구간에서 최소, 최댓값을 찾아야 한다. 세그먼트 트리를 이용해 풀었다. 세그먼트 트리는 구간별로 값을 담아서 최댓값, 최솟값, 구간합 등 문제에 유용한 자료구조이다. 최소, 최대를 구해야 하기 때문에 Node라는 class를 만들어 최소, 최댓값을 담았다. Node배열을 만들어 세그먼트 트리로 이용했다. N개의 정수가 주어진다고 하면 트리 배열의 사이즈를 구하는 방법은 다음과 같다.// 트리의 높이int height = (int) Math.ceil(Math.log(arrSize) / Math.log(2));// 트리의 노드 수this.treeSize = (int) Math.pow(2, height + 1);하지만 N.. 2024. 5. 14.
[백준] 1725: 히스토그램 - JAVA https://www.acmicpc.net/problem/1725 풀이각 칸들의 높이가 주어지고, 내부에 가장 큰 직사각형을 구하는 문제이다. 아랫변을 구간으로 나눠 그 구간으로 이룰 수 있는 직사각형의 넓이를 비교해주었다. 세그먼트트리에는 구간별로 최소 높이를 갖는 인덱스를 저장해주었다. 구간으로 탐색할 때 인덱스를 기준으로 나누기 위함이다. (1, N)구간에서 넓이를 구하면 밑변은 (N - 1 + 1)이 되고, 높이는 해당 구간의 최소 높이를 세그먼트트리에서 찾아주면 된다. 이렇게 구한것이 해당 구간에서 만들수있는 직사각형의 최대이다. 위에서 찾은 최소 높이의 인덱스를 idx라고 하면 (1, idx - 1), (idx + 1, N)으로 나누어 계속 진행한다.  메모리: 39272KB시간: 356ms언.. 2024. 5. 14.
[백준] 11000: 강의실 배정 - JAVA https://www.acmicpc.net/problem/11000 풀이수업들의 시작, 종료 시간이 주어지고 강의실을 최소로 배정해야 한다. 수업이 끝나면 해당 강의실을 사용할 수 있다. 수업에 대한 정보를 입력받아 시작 시간을 오름차순으로, 시작 시간이 같다면 종료 시간을 오름차순으로 정렬했다. 우선순위큐에 종료시간을 오름차순으로 담으면서 수업에 대한 정보를 넣어줬다. pq.peek()이 다음 수업의 시작시간보다 작거나 같으면 pq에서 제거해주고 다음 수업을 pq에 넣었다. pq.peek()이 없거나, 다음 수업의 시작시간보다 크다면 answer을 하나 늘려줬다.  메모리: 67960KB시간: 740ms언어: Java 11import java.io.*;import java.util.*;public cl.. 2024. 5. 14.
[백준] 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.

티스토리툴바