본문 바로가기

Algorithm/Baekjoon208

[백준] 11582: 치킨 TOP N - JAVA https://www.acmicpc.net/problem/11582 풀이구간을 나눠 정렬해주면 되는 간단한 문제였다. N/k 길이 씩 구간을 정해 그 구간을 정렬하여 출력한다. 임시로 배열이나 리스트를 만들고 구간의 값을 넣은 뒤 정렬해주었다. 임시로 저장할 공간을 만들 때 세가지 경우를 실험해 보았다. 1. 배열을 매번 새로 선언. 2. 리스트를 전역으로 선언하고 매번 list를 clear. 3. 리스트를 매번 새로 선언. 배열을 매번 선언하는 것이 메모리, 시간이 모두 적게 나왔다. 리스트의 clear를 이용하는 것보다 매번 선언하는 것이 시간이 적게 걸렸다. 리스트의 clear함수는 리스트를 돌면서 null로 채우는 방식인데 list의 사이즈가 클 때는 clear보다 새로 선언하는 것이 더 빠르다... 2024. 5. 11.
[백준] 1756: 피자 굽기 - JAVA https://www.acmicpc.net/problem/1756 풀이구현 + 그리디 문제. 피자 반죽을 오븐의 사이즈에 맞춰서 넣는데 위에서부터 내려가다가 오븐의 사이즈가 피자 사이즈보다 작으면 그 위칸에 위치한다. 예제에서 오븐의 사이즈가 { 5, 6, 4, 3, 6, 2, 3 } 으로 주어졌는데 두번째 칸에는 위에서부터 내려와야 하므로 최대 5 사이즈의 피자가 들어갈 수 있다. 따라서 오븐의 사이즈 배열을 { 5, 5, 4, 3, 3, 2, 2 } 와 같이 바꿔주었다. 단순하게 아래에서부터 탐색하여 위치를 찾는 방법과 이분탐색으로 위치를 찾는 방법이 있었다.  단순 탐색메모리: 64440KB시간: 532ms언어: Java 11import java.io.*;import java.util.*;publi.. 2024. 5. 11.
[백준] 28071: 승형이의 사탕 사기 - JAVA https://www.acmicpc.net/problem/28071 풀이dp문제이다. M개의 사탕 상자를 가져갈 수 있고, 사탕 개수의 총 합은 K로 나누어 떨어져야 한다. 상자의 개수와 나머지에 따라 dp배열을 생성한다. dp[i][j]에서 i를 상자의 개수, j를 나머지라고 하면 dp[i][j]의 값은 i-1개의 상자에서 "j - 현재 사탕상자의 사탕 개수"일때의 dp값을 이용하여 갱신한다. "j - 현재 사탕상자의 사탕 개수"가 음수가 되면 안되기 때문에 Math.floorMod연산을 사용했다. dp배열을 채운 후 나머지가 0인 경우 중 최댓값을 구한다.  메모리: 15152KB시간: 424ms언어: Java 11import java.io.*;import java.util.*;public class.. 2024. 5. 11.
[백준] 1174: 줄어드는 수 - JAVA https://www.acmicpc.net/problem/1174 풀이321, 950처럼 왼쪽부터 자리수가 감소할 때 줄어드는 수를 찾는 문제. 줄어드는 수를 저장해놓고 N번째 줄어드는 수를 출력해주었다. 줄어드는 수 중 가장 큰수는 "9876543210"이다. (long 범위) {9, 8, 7, 6, 5, 4, 3, 2, 1, 0}의 배열을 만들어 놓고 앞에서부터 해당 인덱스를 선택할지 여부를 조합으로 수를 만든다. 만든 수를 list에 넣어 정렬했다. list를 인덱스로 접근하여 출력하면 문제 끝. 조합을 할 때, 재귀로 접근할 수도 있고, 비트마스킹을 이용할 수 있다. 처음에 재귀로 문제를 풀고, 비트로 하는 방법을 찾아봤다.  재귀메모리: 14500KB시간: 152ms언어: Java 11impor.. 2024. 5. 11.
[백준] 21738: 얼음깨기 펭귄 - JAVA https://www.acmicpc.net/problem/21738 풀이그래프 탐색 문제. 펭귄이 얼음 위에 올라가있는데 떨어지지 않으려면 연결된 지지대 얼음 2개가 필요하다. 최소한의 얼음만 남기고 얼음을 깨야한다. 펭귄의 위치로부터 탐색한다. 먼저 발견한 얼음이 가깝다는 것이므로 먼저 발견한 2개의 지지대 얼음을 제외한 나머지 얼음은 깨는 것으로 한다.  메모리: 152136KB시간: 696ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int N, S, P, ans; static ArrayList> list; public static void main(String[] args) throws IOE.. 2024. 5. 11.
[백준] 19699: 소-난다! - JAVA https://www.acmicpc.net/problem/19699 풀이소 M마리의 합이 소수인지 판별하는 문제였다. N마리의 소가 있다. N마리 중 M마리의 조합을 만들어 소수인지 판별해주었다. 소수는 에라토스테네스의 체를 구현하여 미리 배열에 정보를 담아놓았다. 오름차순으로 출력과 중복 제거를 위해 TreeSet을 이용했고, Set출력을 위해 Stream을 이용했다.  메모리: 14296KB시간: 128ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int N, M; static int[] cow, group; static boolean[] prime; static TreeSet ans; .. 2024. 5. 11.
[백준] 3359: 사각 사각 - JAVA https://www.acmicpc.net/problem/3359 풀이DP문제이다. 사각형을 각각 가로로 놓을지 세로로 놓을지 정해서 위쪽 둘레의 최댓값을 찾는다. dp배열을 이차원배열로 만들어 현재 사각형을 가로로 놓는다면 [0]에, 세로로 놓는다면 [1]에 값을 넣는다. 옆면까지 생각해야한다. 이전 dp배열에서 선택안한 변과 현재 선택안한 변의 차이를 더해 최댓값을 현재 dp배열에 더해준다.  메모리: 14480KB시간: 140ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader b.. 2024. 5. 11.
[백준] 3010: 페그 - JAVA https://www.acmicpc.net/problem/3010 풀이구현문제. o가 o 하나를 건너뛰어서 .에 도착하면 정답 개수 하나를 늘린다. o보다 .이 더 적을거라고 생각해서 .을 저장하였다. .주위를 사방탐색하여 o이면 한칸 더 가도 o일 때 정답 개수를 늘렸다.  메모리: 14240KB시간: 120ms언어: Java 11import java.io.*;import java.util.*;public class Main { static class Point { int r; int c; public Point(int r, int c) { this.r = r; this.c = c; } } stat.. 2024. 5. 11.
[백준] 16986: 인싸들의 가위바위보 - JAVA https://www.acmicpc.net/problem/16986 풀이구현문제. 승패가 주어지고, 각각 어떤 어떤 동작을 할지 알려준다. 승패 테이블을 이용해 승,패를 판단하는 문제. 지우가 다른 동작들을 내면서 K승을 쌓으면 성공이다. 지우가 낼 동작을 순열을 통해 작성하고 게임을 진행한다. 지우가 K승 이상 쌓으면 true, 지우가 N번 이상 동작을 하면 같은 동작을 다시 내는 것이므로 false, 경희나 민호가 K승 이상 쌓으면 false이다.  메모리: 37796KB시간: 248ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int N, K; static int[][] table; static.. 2024. 5. 11.
[백준] 16938: 캠프 준비 - JAVA https://www.acmicpc.net/problem/16938 풀이비트마스크를 이용해 조합을 만드는 문제였다. 조합을 만들어 문제의 조건들을 비교해주었다. 비트마스크 조합int N = 3;int[] arr = {1, 2, 3}for(int i = 1; i  공집합을 제외하고 1~7까지 탐색한다. 예를 들어 6을 탐색하면 2진수로 6은 110이므로 배열에서 1번, 2번 인덱스의 값을 꺼낸다.  메모리: 14288KB시간: 128ms언어: Java 11import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { BufferedReader b.. 2024. 5. 11.

티스토리툴바