본문 바로가기

전체 글242

[백준] 21924: 도시 건설 - JAVA https://www.acmicpc.net/problem/21924 풀이도로를 연결해야 한다. 최소한의 비용으로. 즉, 최소 스패닝 트리(MST)에 대한 문제이다. 크루스칼과 프림의 두 가지 알고리즘으로 풀 수 있는데 크루스칼 알고리즘을 선택했다. 크루스칼 알고리즘은 간선을 하나씩 선택해서 최소신장트리를 찾는 알고리즘이다.     1. 처음에 모든 간선을 가중치에 따라 오름차순으로 정렬하고 시작한다.     2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킨다.(이때, 사이클이 존재하게 될 경우 다음으로 가중치가 낮은 간선을 선택한다.)     3. N-1개의 간선이 선택될때까지 2번 과정을 반복한다. 간선을 비용에 따라 정렬해야 하는데 정렬하는 방법으로 PriorityQueue를 이용했다. 크.. 2024. 5. 13.
[백준] 11779: 최소비용 구하기 2 - JAVA https://www.acmicpc.net/problem/11779 풀이출발 도시부터 도착 도시까지 최소 비용으로 가야한다. 다익스트라 알고리즘을 사용하는 문제였다. 최소 비용, 경로에 포함된 도시의 개수, 방문한 도시를 출력해야 했다. 다익스트라 알고리즘으로 최소 비용을 구하고, int 배열로 비용을 저장하지 않고 class 배열을 만들어서 이전의 도시와 비용을 저장해줬다. 최소 비용을 구한 뒤 도착지부터 역추적하여 방문한 경로를 구했다. 역추적 하기 위해 class를 만들어 배열에 넣어준 것이다.  메모리: 54432KB시간: 576ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Node imple.. 2024. 5. 13.
[백준] 24230: 트리 색칠하기 - JAVA https://www.acmicpc.net/problem/24230 풀이트리가 주어지고 트리를 주어진 색으로 칠해야 한다. 한 정점에 색을 칠하면 그 정점의 하위 정점들 모두에게 같은 색을 칠한다. 따라서 루트인 1번 정점부터 시작하여 아래로 내려가면서 색이 다르면 색을 칠해줬다. dfs탐색을 통해 먼저 자식의 부모의 색을 따라서 칠하고 원하는 색과 비교하여 색을 다시 칠했다.  메모리: 111952KB시간: 1684ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int N, ans; static int[] arr, color; static ArrayList> list; static boolean.. 2024. 5. 13.
[백준] 16947: 서울 지하철 2호선 - JAVA https://www.acmicpc.net/problem/16947 풀이서로 연결된 정점들의 번호가 주어진다. 루프를 이루고 있는것을 먼저 찾고 그 루프로부터의 거리를 출력해야한다. dfs탐색을 통해 루프를 탐색했다. 저장된 루프의 정점으로부터 bfs탐색을 통해 루프에 포함되지 않은 정점들이 루프로부터 얼마나 떨어져 있는지 저장하고 출력한다.  메모리: 25788KB시간: 388ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int N; static ArrayList> list; static boolean[] loop; static int[] dist; public static void ma.. 2024. 5. 13.
[백준] 11559: Puyo Puyo - JAVA https://www.acmicpc.net/problem/11559 풀이같은 색 블럭이 4개 이상 연결되어 있으면 한번에 없어진다. 한 라운드씩 진행하여 없어질 수 있는 블럭이 있으면 1연쇄 늘어나고 다음 라운드로 넘어갔다. 라운드를 넘어가기 전에 블럭들을 없앤 후 밑으로 내려주는 작업도 필요했다. 이차원 배열을 탐색하여 '.'이 아닌 경우 bfs탐색을 진행했다. 상하좌우에 같은 색이 있으면 list에 담고 queue에 넣어 계속했다. list에 담긴 개수가 4이상이면 '.'으로 없애주었다. 이번 라운드에 없어진 블럭이 있으면 내려주는 작업을 해야한다. 내려줄때는 열을 먼저 탐색하여 해당 열의 블럭들을 stack에 담아 아래에서부터 채워줬다.  메모리: 14480KB시간: 128ms언어: Java 11i.. 2024. 5. 13.
[백준] 1516: 게임 개발 - JAVA https://www.acmicpc.net/problem/1516 풀이위상 정렬을 이용하는 문제이다. 건물을 지을 때 먼저 지어야 할 건물이 정해져 있다. 즉, 먼저 지어야할 건물의 개수가 0이되면 지을 수 있는 것이다. 인접리스트로 건물을 지은 다음에 지을 수 있는 건물을 저장해놓는다. in_degree 배열에 먼저 지어야 할 건물의 개수를 저장한다. in_degree 배열이 0인 것부터 먼저 queue에 넣고 탐색하여 인접리스트에서 다음 건물의 in_degree값을 하나 빼준다. in_degree 값이 0이되면 queue에 넣는다.  메모리: 21612KB시간: 260ms언어: Java 11import java.io.*;import java.util.*;public class Main { pub.. 2024. 5. 13.
[백준] 12015: 가장 긴 증가하는 부분 수열 2 - JAVA https://www.acmicpc.net/problem/12015 풀이가장 긴 증가하는 부분수열(LIS)의 길이를 구해야 한다. dp로 풀어보았으나 시간초과가 났다. dp로 푸는 풀이는 N^2의 시간복잡도를 갖는다. 이분 탐색으로 푸는 방법을 채택하여 NlogN으로 시간을 줄였다. 배열을 만들어 숫자가 들어갈 위치를 찾아 그 숫자를 배열에 넣는다. 배열의 마지막 값보다 숫자가 크다면 그 다음 칸에 숫자를 넣고, 작다면 이분탐색을 통해 들어갈 위치를 찾아 갱신해 주면 되는 문제였다.  메모리: 95952KB시간: 528ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] .. 2024. 5. 13.
[백준] 15961: 회전 초밥 - JAVA https://www.acmicpc.net/problem/15961 풀이슬라이딩 윈도우를 사용해서 카운트하는 문제였다. 회전 초밥을 연속에서 k개 먹어야하는데 최대한 다양한 종류를 먹으려고 한다. 쿠폰이 하나 주어지고 쿠폰에 적혀진 종류의 초밥을 먹지 않았으면 하나 제공해 준다. 즉, 가장 다양하게 먹으려면 연속된 k개에서 다 다른 초밥을 먹고 쿠폰에 있는 초밥을 제공받아 먹어야 한다. int로 먹은 것을 체크하는 배열을 만들었다. left는 0, right는 k-1부터 시작하여 1씩 늘리면서 체크해준다. 체크 배열에 쿠폰에 있는 초밥이 없으면 bonus를 1로 해주고 cnt + bonus의 최댓값이 정답이 된다.  메모리: 170972KB시간: 548ms언어: Java 11import java.io.*.. 2024. 5. 13.
[백준] 2812: 크게 만들기 - JAVA https://www.acmicpc.net/problem/2812 풀이스택을 이용하는 그리디 문제였다. N 자리 숫자에서 숫자 K 개를 지웠을 때의 최댓값을 구해야 한다. 숫자를 입력받으면서 stack에 하나씩 넣는다. 뺄 수 있는 개수(K)가 남아있고 stack의 끝값이 자신보다 작으면 그 값을 빼고 넣는다. 다만 N이 987654321과 같이 주어지면 stack에 들어가기만 하고 빠지는 숫자는 없다. 따라서 stack의 사이즈 - K 만큼 출력해 주어야 한다. 출력할 때 앞에서부터 빼기 위해서 stack 대신 deque을 이용했다.  메모리: 36464KB시간: 380ms언어: Java 11import java.io.*;import java.util.*;public class Main { pub.. 2024. 5. 13.
[백준] 2565: 전깃줄 - JAVA https://www.acmicpc.net/problem/2565 풀이A와 B기둥에 전깃줄을 연결하는데 서로 겹치는 전깃줄이 없어야 한다. 입력을 받아 A기준으로 오름차순으로 정렬한다. 예제에서 정렬하면 A는 오름차순으로 정렬되고 B는 다음과 같이 된다. {8, 2, 9, 1, 4, 6, 7, 10} 전깃줄을 교차되지 않게 하기 위해 없애야 하는 최소의 개수를 구해야 한다. 즉, 가장 많이 연결이 되어야 한다는 의미이다. 정렬을 하니 주어진 배열에서 가장 긴 증가하는 부분수열(LIS)의 길이를 찾는 문제로 바뀌었다. LIS의 길이를 찾아 N에서 빼주면 없애야 할 전깃줄의 개수가 나온다. LIS를 찾는 방법은 DP를 이용한 방법과 이분 탐색을 이용한 방법이 있다. DP를 이용한 방법은 들어갈 수 있는 인덱.. 2024. 5. 13.

티스토리툴바