Algorithm221 [백준] 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. [백준] 20002: 사과나무 - JAVA https://www.acmicpc.net/problem/20002 풀이2차원 누적합을 만들어 값을 찾는 문제였다. 한 변의 길이가 N인 2차원 누적합 배열을 만드려면 N + 1사이즈의 이차원 배열을 만들고 1부터 값을 채운다.int[][] prefix_sum = new int[N + 1][N + 1];for (int i = 1; i 값을 찾으려면 이와 반대로 빼고 더해준다. 메모리: 23072KB시간: 376ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new Buf.. 2024. 5. 13. [백준] 9527: 1의 개수 세기 - JAVA https://www.acmicpc.net/problem/9527 풀이자연수 A부터 B까지 모든 수에 대해 이진수로 표현했을 때 1의 개수를 구해야한다. 자연수의 범위는 10의 16제곱까지였다. 2의 54제곱이 10의 16제곱을 넘어서 이진수로 54자리수까지 담는 배열을 만들었다.dp[i] = (dp[i - 1] 배열의 점화식은 위와 같다. i자리수는 i-1자리수의 모든 경우의 앞에 1을 붙이면 되기 때문이다. B까지의 개수에서 A-1까지의 개수를 빼주면 정답이다. 하지만 예를 들어 자연수 14가 주어지면 3자리까지의 개수를 더하고 나머지를 더 구해줘야 한다. 이진수들을 써본 결과 규칙을 찾았고 다음과 같은 식으로 계산할 수 있었다.return dp[digit - 1] + diff + count(n - .. 2024. 5. 12. [백준] 1937: 욕심쟁이 판다 - JAVA https://www.acmicpc.net/problem/1937 풀이특정 위치에서 시작하여 상하좌우로 움직일 수 있다. 현재 칸보다 숫자가 더 큰 칸으로만 갈 수 있는데 갈 수 있는 최대 칸 수를 구하는 문제. 처음에 dfs로 풀었는데 시간초과가 났다. 모든 칸을 봐야하는데 이미 기록된 칸은 더이상 볼 필요가 없었다. 메모이제이션을 하여 dp배열에 저장된 값이 있다면 그 값을 반환해주고 바로 끝내도록 했다. 메모리: 37148KB시간: 516ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int n; static int[][] forest, dp; static int[][] vector = { { .. 2024. 5. 12. [백준] 14940: 쉬운 최단거리 - JAVA https://www.acmicpc.net/problem/14940 풀이목표지점이 주어지고 지도의 모든 지점에서 목표지점까지의 거리를 구하는 문제이다. 목표지점부터 시작해서 bfs탐색을 통해 거리를 갱신해주었다. 원래 갈 수 없는 땅은 0으로 출력하고 도달할 수 없는 위치는 -1로 해야하는데 bfs탐색 중 처음만난 0은 0으로 처리 되지만 만나지 않는 0들은 -1로 되는 문제가 있어서 입력받을 때 0을 배열에 입력해 놓고 시작했다. 메모리: 51672KB시간: 668ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Node { int r; int c; public .. 2024. 5. 12. [백준] 15683: 감시 - JAVA https://www.acmicpc.net/problem/15683 풀이cctv의 방향을 설정하여 사각지대를 최소로 만들어야 한다. cctv의 종류는 5가지가 있다. 2번 cctv는 방향을 선택할 수 있는 방법이 2가지, 5번 cctv는 1가지였다. 나머지 cctv는 4방향 모두 선택할 수 있다. 입력받으면서 cctv의 위치를 저장했고, 그들의 방향을 저장할 배열을 만들어 각각 어떤 방향을 선택할지 조합을 만들었다. 조합이 완성되면 그 방향에 맞게 빈칸을 채워가면서 체크했다. 처음에 빈칸(0)의 개수를 세어놓고 빈칸을 몇개나 채웠는지를 세어 빼주면 된다. 메모리: 72084KB시간: 304ms언어: Java 11import java.io.*;import java.util.*;public class M.. 2024. 5. 12. 이전 1 ··· 15 16 17 18 19 20 21 ··· 23 다음