본문 바로가기

Algorithm221

[백준] 3020: 개똥벌레 - JAVA https://www.acmicpc.net/problem/3020 풀이석순과 종유석이 번갈아 나오는 동굴을 장애물을 파괴하면서 지나가야한다. 높이별로 만나는 장애물의 개수를 세어 최솟값을 찾는 문제이다. 처음에 누적합으로 문제를 풀었고, 이분 탐색으로 푸는 방법이 있다고하여 찾아보았다. - 이분 탐색   이분 탐색으로 풀기 위해서는 석순과 종유석을 따로 배열에 담아준다.   bottom배열에 석순을, top배열에 종유석을 담았다.   이분탐색을 위해 배열을 정렬한 뒤 1부터 H까지 높이을 key로 하여 이분탐색을 진행한다.   석순과 종유석을 각각 진행하여 해당 key값(key값보다 크거나 같은 첫번째 인덱스)을 찾아 arr.length - rigth을 반환하면 해당 구간의 장애물의 개수를 구할 수 있다.. 2024. 5. 14.
[백준] 9081: 단어 맞추기 - JAVA https://www.acmicpc.net/problem/9081 풀이C++에 있는 next permutation 함수를 구현하는 문제이다. 어떤 문자가 주어지면 그 문자의 알파벳들로 만들 수 있는 문자들 중 처음 주어진 문자의 다음에 올 문자를 찾는 문제였다. 조합으로 모든 경우를 만들어 set에 넣는 방식으로 구현하였는데 메모리초과로 실패했다. next permutaion이란 방법을 찾아 구현해보았다.1. 뒤에서부터 탐색하여 증가하지 않는 첫번째 인덱스를 찾는다.2. 다시 뒤에서부터 탐색하여 찾은 인덱스의 값보다 처음으로 큰 값이 나오는 인덱스를 찾는다.3. 두 인덱스의 값을 바꾸고 인덱스 뒤 부분을 정렬하여 붙인다.따라서, 주어진 단어를 int배열로 만들어 구현했다. 뒤에서부터 탐색해 값이 감소하는.. 2024. 5. 14.
[백준] 2250: 트리의 높이와 너비 - JAVA https://www.acmicpc.net/problem/2250 풀이트리를 격자모양의 틀에 넣을 때 트리의 깊이별로 너비를 구했을 때 최댓값을 찾는 문제. 입력받으면서 트리를 저장하는데, 부모, 왼쪽 자식, 오른쪽 자식을 저장한다. 입력받아서 저장한 후 부모가 -1로 되있는 것이 루트 노드이다. 루트노드부터 중위순회(왼쪽 - 루트 - 오른쪽)하여 탐색하면 열 번호를 1부터 순서대로 부여할 수 있다. 중위순회할 때 트리의 깊이(level)도 함께 넘겨 각 깊이별로 열 번호의 최대와 최소를 저장한다. 중위순회를 마친 후 깊이별로 너비의 최댓값을 구한다.  메모리: 21176KB시간: 256ms언어: Java 11import java.io.*;import java.util.*;public class Main.. 2024. 5. 14.
[백준] 3025: 돌 던지기 - JAVA https://www.acmicpc.net/problem/3025 풀이주어진 조건에 맞게 위에서부터 돌을 떨어뜨려 최종 상태를 출력하는 문제였다. 단순한 구현으로 하나씩 진행하며 문제를 풀었을 때는 시간초과가 발생했다. 시간초과를 해결하기위해 메모이제이션을 해야했다. 처음 돌을 놓는 열 별로 stack을 만들어 돌이 이동하는 경로를 저장했다. 새로운 돌을 던질 때 stack에 경로가 들어있다면 마지막에서부터 진행하면 된다.1. 돌의 아랫칸이 벽으로 막혀있거나 가장 아랫줄이라면, 돌은 그 자리에 그대로 멈춰 있는다.2. 돌의 아랫칸이 비어있다면, 돌은 아랫칸으로 이동한다.3. 돌의 아랫칸에 돌이 있다면, 돌은 다음과 같이 미끄러진다. 1. 만약 돌의 왼쪽 칸과 왼쪽-아래 칸이 비어있다면, 돌은 왼쪽으.. 2024. 5. 14.
[백준] 1300: K번째 수 - JAVA https://www.acmicpc.net/problem/1300 풀이이차원배열의 각 칸에 i X j 의 숫자들이 들어있다. 이들을 일차원배열에 넣어 정렬했을 때 k번째 숫자를 구해야한다. 풀이 방법이 떠오르지 않아 다른 블로그들의 도움을 받았다. 이차원배열의 각 행들이 구구단으로 이루어져 있다. 구구단을 쭉 나열해보면 다음과 같다.1단: {1, 2, 3, 4, 5, 6, 7, 8, 9}2단: {2, 4, 6, 8, 10, 12, 14, 16, 18}...8단: {8, 16, 24, 32, 40, 48, 56, 64, 72}9단: {9, 18, 27, 36, 45, 54, 63, 72, 81}이 나열된 숫자에서 예를들어 7보다 작거나 같은 숫자가 몇개인지 구하려면 1단에서는 7 / 1 = 7 으로 7개가.. 2024. 5. 14.
[백준] 25307: 시루의 백화점 구경 - JAVA https://www.acmicpc.net/problem/25307 풀이이차원배열에 기둥이 있는 칸, 의자가 있는 칸, 마네킹이 있는 칸, 시작 위치를 입력받는다. 시작 위치에서 의자가 있는 칸까지 거리를 묻는 문제였다. 다만, 기둥이 있는 칸은 지나갈 수 없고, 마네킹과의 거리가 K 이하인 칸들은 지나갈 수 없다. 마네킹이 있는 칸을 입력받을 때 List에 저장해 bfs탐색을 통해 마네킹으로부터 거리가 K 이하인 칸들을 기둥이 있는 칸과 같게 만들었다. 이렇게 0으로된 칸은 모두 지나갈 수 있는 칸이 된다. 시작위치부터 bfs탐색을 통해 의자의 위치가 나오면 거리를 반환하고, 의자에 도달할 수 없으면(bfs의 while문이 끝나면) -1을 반환했다.  메모리: 395276KB시간: 1204ms언어: J.. 2024. 5. 14.
[백준] 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.

티스토리툴바