본문 바로가기

분류 전체보기242

[백준] 28703: Double It - JAVA https://www.acmicpc.net/problem/28703 풀이배열에서 수 하나를 골라 2를 곱하는 동작을 반복한다. 이렇게 동작하는 중에 배열의 최댓값과 최솟값의 차이를 구하는 문제이다. 처음 배열의 최댓값을 저장해놓고 작은 수부터 2를 곱하기 위해 우선순위큐에 수들을 넣었다. 처음 주어진 최댓값이 우선순위큐에서 나오기 전까지 숫자들을 뽑으면서 2를 곱하고 답을 갱신했다.  메모리: 114588KB시간: 1284ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = n.. 2024. 5. 14.
[백준] 11562: 백양로 브레이크 - JAVA https://www.acmicpc.net/problem/11562 풀이일방통행인 길을 양방향으로 바꿔 목적지로 갈 수 있도록 해야한다. 플로이드-워셜 알고리즘을 사용하는데 일방통행인 길은 양방향으로 바꿔줘야하므로 1이라는 가중치를 두고, 양방향길은 0으로 저장한다. 플로이드-워셜 알고리즘으로 u에서 v로 가는데 바꿔야 할 길의 수를 구해놓고 질문이 올 때마다 저장된 배열에서 값을 출력한다.  메모리: 31772KB시간: 440ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br .. 2024. 5. 14.
[백준] 13325: 이진 트리 - JAVA https://www.acmicpc.net/problem/13325 풀이포화이진트리의 에지들에 가중치가 있을 때, 에지들의 가중치를 증가하여 루트에서 리프까지의 거리가 같게 만들어야 한다. 트리의 높이 k 가 주어지는데 이때 트리의 사이즈는 Math.pow(2, k + 1) - 1 이다. 사이즈만큼 배열을 만들어 arr[2]부터 채운다. arr[1]은 루트노드로 값은 0이다. 문제에서는 에지에 가중치가 있다고 표현하고있지만 각 노드들에 가중치를 넣었다. 배열을 채운 후, 루트노드 1 부터 시작하여 dfs탐색을 통해 값을 더한다. 왼쪽 자식 노드와 오른쪽 자식 노드의 값 중 큰 값을 현재 노드의 값에 더해 부모 노드로 반환하고, 답을 저장하는 변수에 현재 노드의 값과 왼쪽 자식, 오른쪽 자식의 차를 더한다.. 2024. 5. 14.
[백준] 1613: 역사 - JAVA https://www.acmicpc.net/problem/1613 풀이사건들의 전후관계를 확인하는 문제이다. 이차원배열을 만들어 a사건 이후에 b사건이 이루어진다면 arr[a][b]를 true로 저장했다. 이때 플로이드-워셜 알고리즘을 사용했다.for (int k = 1; k 배열을 다 채운 후 입력을 받으면서 table[a][b]가 true이면 -1, table[b][a]가 true이면 1, 둘 다 false이면 0을 출력했다.  메모리: 38252KB시간: 472ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { .. 2024. 5. 14.
[백준] 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.
[자바] Stream API Stream API자바8부터 Stream API와 람다식 등을 지원하면서 자바를 이용해 함수형으로 프로그래밍할 수 있게 API를 제공해주고 있다. Stream API는 데이터의 종류에 상관없이 같은 방식으로 데이터를 처리할 수 있어 재사용성을 높일 수 있다. Stream API는 원본 데이터를 변경하지 않고, 일회용으로 한번 사용하면 재사용이 불가능하다. 또한, 내부 반복으로 작업을 처리하는 특징이 있다. Stream API를 사용하지 않은 경우에는 다음과 같이 배열과 리스트를 만들고 사용했다.String[] arr = {"Dog", "Cat", "Penguin", "Lion"};List list = Arrays.asList(arr);// 정렬: 원본 데이터가 정렬됨Arrays.sort(arr);Coll.. 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.

티스토리툴바