본문 바로가기

Algorithm221

[백준] 2011: 암호코드 - JAVA https://www.acmicpc.net/problem/2011 풀이A를 1, Z를 26으로 알파벳 각각 숫자를 매겼을 때, 숫자가 주어지고 그 숫자를 어떤 알파벳 조합으로 해석할 수 있는지 경우의 수를 찾는 문제였다. 현재 보고있는 수와 앞자리수를 붙여 26이하가 나오면 두개를 묶어 하나의 알파벳으로 바꿀 수 있게 된다. 주어진 수를 하나씩 저장해 탐색하면서 현재 숫자가 0이면 앞자리 수가 1일때 10으로 볼 수 있으므로 dp[i-2]값을 가져오고, 앞자리 숫자가 1이 아니라면 0 하나는 어떠한 알파벳으로 볼 수 없으므로 해석할 수 없는 경우로 0을 출력한다. 현재숫자가 0이 아니라면 앞자리 숫자와 붙여 10~26의 경우 dp[i-2]의 값도 가져와야 하고 나머지 경우 dp[i-1]의 값을 가져온다... 2024. 5. 14.
[백준] 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.

티스토리툴바