본문 바로가기

전체 글242

[백준] 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.
[스프링] [JPA] Querydsl 방언 사용하기 MySQL의 FullText Search를 Querydsl을 이용하여 적용하는 방법을 찾아봤다. DialectJPA를 사용하면 데이터베이스의 문법을 잘 알지 못해도 hibernate가 설정한 데이터베이스의 쿼리로 바꿔준다. 이 일을 해주는 것이 Dialect이다. application.properties에 사용하는 DB의 dialect가 설정되어 있다.spring.jpa.database-platform=org.hibernate.dialect.MySQL8Dialect FullText Search는 Dialect에 등록된 함수가 아니었고, 따로 커스텀하여 사용해야 한다. 설정1. CustomDialect 생성import org.hibernate.dialect.MySQL8Dialect;public class .. 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.
[백준] 9252: LCS 2 - JAVA https://www.acmicpc.net/problem/9252 풀이LCS(최장 공통 부분 수열)문제. 두 수열이 주어졌을 때 공통된 부분 수열 중 가장 긴 것을 찾는다. 점화식은 다음과 같다. dp[i][0], dp[0][j]는 0으로 채워진 상태로 시작한다.if (a[i - 1] == b[j - 1]) { dp[i][j] = dp[i - 1][j - 1] + 1;} else { dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);}수열A와 수열B를 한 글자씩 비교한다. 두 문자가 다르다면 dp[i-1][j]와 dp[i][j-1] 중 큰 값으로 하고, 같다면 dp[i-1][j-1] + 1 으로 한다. 이렇게 하면 최장 공통 부분 수열의 길이를 구할 수 있다.. 2024. 5. 12.
[백준] 10942: 팰린드롬? - JAVA https://www.acmicpc.net/problem/10942 풀이수열이 주어지고 수열의 S번째 수부터 E번째 까지 팰린드롬을 이루는지 확인하는 문제. 수열의 1번부터 N번까지의 팰린드롬 여부를 담는 dp배열을 만든다. S, E를 입력받으면서 dp배열에 결과를 저장하면서 판별한다. 팰린드롬 판별은 재귀를 통해 구현했다. S와 E가 같으면 한 자리수이므로 true이고, 아닌 경우 다시 재귀를 통해 S+1과 E-1의 팰린드롬 여부를 판별하도록 했다.  메모리: 219448KB시간: 832ms언어: Java 11import java.io.*;import java.util.*;public class Main { static int[] arr; static boolean[][] dp; pub.. 2024. 5. 12.
[백준] 2251: 물통 - JAVA https://www.acmicpc.net/problem/2251 풀이물통 세 개의 부피가 정해져 있고 초기에는 C물통만 가득 차 있다. A물통이 비어있을 때마다 C물통의 양을 체크하여 저장하면 되는 문제이다. A, B, C물통의 양을 방문처리하기 위해 boolean[][][] 배열을 이용했고, C물통의 양을 오름차순으로 저장하기 위해 TreeSet을 이용했다. dfs탐색을 통해 진행하며 물통의 양을 체크했고, A물통에 물이 있다면 "A물통의 양 + B물통의양"과 "B물통의 용량"을 비교하여 A물통에서 B물통으로 옮기는 경우를 처리했다.  메모리: 23284KB시간: 140ms언어: Java 11import java.io.*;import java.util.*;public class Main { st.. 2024. 5. 12.
[백준] 7682: 틱택토 - JAVA https://www.acmicpc.net/problem/7682 풀이구현 문제였다. 틱택토 게임의 게임판을 보고 이 상태로 종료될 수 있는지 보는 문제. 여러 경우를 처리해야 하는 문제였다. 1. 이차원 배열에 입력받으면서 X와 O의 개수를 세줬다. O가 X보다 많으면 invalid. 2. X의 개수 - O의 개수가 1이나 0이면 3칸을 잇는데 성공한 개수를 센다. 3. 판이 꽉 차있는 경우 O가 이긴다면 invalid. X가 마지막에 놓기 때문이다. 4. 꽉 차있지 않다면 3칸을 잇는데 성공한 개수가 1보다 많으면 invalid. 5. O가 마지막에 놨는데 O가 이기면, X가 마지막에 놨는데 X가 이기면 invalid. 6. 이외의 경우 valid.  메모리: 15048KB시간: 144ms언어: Ja.. 2024. 5. 12.

티스토리툴바