Algorithm/Baekjoon
[백준] 1766 문제집 - Java
[백준] 1766 문제집 - Java
2022.07.28위상정렬 연습하기 좋은 문제.. 가능하면 쉬운 문제부터 푸는게 좋다고 하니 우선순위 큐를 사용해 낮은거부터 뽑아줬다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringBuilder sb = new StringBuilder(); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); in..
[백준] 9251 LCS - Java
[백준] 9251 LCS - Java
2022.07.27https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence [알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence LCS는 주로 최장 공통 부분수열(Longest Common Subsequence)을 말합니다만, 최장 공통 문자열(Longest Comm..
[백준] 12865 평범한 배낭 - Java
[백준] 12865 평범한 배낭 - Java
2022.07.27dp[N+1][K+1] 행을 증가시키면서 값을 누적시켜 최적 무게를 계산한다. dp의 열 값은 해당 무게만큼 물건을 넣었을 때 가치의 최댓값이다. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int N = Integer.parseInt(st.nextToken()); int K = Integer.parseInt(s..
[백준] 2193 이친수 - Java
[백준] 2193 이친수 - Java
2022.07.26간단한 dp문제다. 이차원 dp배열을 설정해서 풀이한다. [N+1][2] : N은 자릿수 / 2는 0으로 끝나는 수와 1로 끝나는 수. 다음 자릿수의 이친수를 구할 때는 이전 자릿수의 이친수가 0으로 끝난 경우 + 1로 끝난 경우 + 0으로 끝난 경우를 계산해주면 된다.. import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); long[][] dp =..
[백준] 1786 찾기 - Java
[백준] 1786 찾기 - Java
2022.07.19문제가 제발 kmp알고리즘으로 풀어달라고 한다.. kmp알고리즘은 접두사와 접미사가 최대로 같을 수 있는 길이를 찾고... 이 길이를 바탕으로 완전탐색으로 해결할 문제를 훨씬 빠르게 해결할 수 있게 하는 알고리즘인데.. 구현이 까다롭진 않아서 몇 번 해보면 외워진다. 모르면 틀려야되지만 알면 쉽게 풀 수 있는 문제다. import java.util.*; import java.io.*; public class Main { static ArrayList list; public static void main(String[] args) throws IOException{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Strin..
[백준] 13460 구슬 탈출 3 - Java
[백준] 13460 구슬 탈출 3 - Java
2022.07.15지난번에 풀었던 구슬 탈출 2를 조금 변형해서 풀 수 있다. Marble클래스에서 지금까지의 방향을 저장하는 요소인 cmd를 만들고 진행하자. return 직전에 현재 방향을 추가해 return을 진행해 마지막 방향까지 고려 할 수 있도록 했다. import java.io.*; import java.util.*; public class Main { static int N, M; static char[][] map; static boolean[][][][] visit; static int[] dr = {-1,1,0,0}; static int[] dc = {0,0,-1,1}; static int hole_r, hole_c; static Marble red, blue; static String an; stat..
[백준] 13460 구슬 탈출 2 - Java
[백준] 13460 구슬 탈출 2 - Java
2022.07.151. dr dc 설정 후 한 칸씩 이동하지 않고 갈 수 있는 최대한 진행한다. 2. 빨간 구슬과 파란 구슬이 이동한 후 같은 위치에 있으면 방향과 시작 위치에 따라 위치를 설정해준다. 3. 최단거리를 구하는 경우는 bfs를 사용해 탐색을 진행하는게 유리하다. visit배열은 4차원으로 설정한다. 방문 여부를 기록할 때 빨간 구슬의 위치와 파란 구슬의 위치가 서로 영향을 주기 때문.. 3차원배열로 설정해도 잘 처리해주면 괜찮긴 한데 4차원배열을 사용하는 쪽이 좀 더 깔끔하다. import java.io.*; import java.lang.reflect.Array; import java.util.*; public class Main { static int N, M; static char[][] map; st..
[백준] 11066 파일 합치기 - Java
[백준] 11066 파일 합치기 - Java
2022.07.08언뜻 봐서는 파일들을 정렬한 후 그리디 느낌으로 풀어낼 수 있을 것 같지만.. 연속된 경우만 파일을 합칠 수 있다는 조건 때문에 그리디로는 풀 수 없다. 가능한 경우를 모두 탐색하는 방법은 시간이 너무 많이 걸리니.. dp를 사용해야 한다. 우선 i와 j를 설정하자. i는 시작, j는 끝을 의미하고 이차원 배열로 저장한다. dp[i][j] 는 i에서 j까지 파일을 합칠 때 소비되는 최소 비용을 의미한다. 위의 배열을 잘 채워넣은 후 dp[1][j-1]의 값을 답으로 사용하자. 공통점을 찾아보자. 항상 하던대로 "마지막에 어떻게 합치는가?"를 기준으로 구분할 수 있을 것 같다. import java.util.*; import java.io.*; public class Main{ public static v..
[백준] 1418 K-세준수 - Java
[백준] 1418 K-세준수 - Java
2022.07.02에라토스테네스의 체를 이용해서 푸는 방식인데.. 문제에 맞게 잘 변형해서 푼 풀이를 가져와서 공부했다. 원래 방식대로면 시간 초과가 나기 쉬운데 상황에 알맞게 잘 변형해서 푼 좋은 풀이인 것 같다. 공부하자.. import java.util.*; import java.io.*; import java.math.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br.readLine()); int K = Integer.parseInt(br..
[백준] 2579 계단 오르기 - Java
[백준] 2579 계단 오르기 - Java
2022.06.29dp배열에는 해당하는 계단을 밟을 때 얻을 수 있는 최대 점수가 들어간다. 세 번 연속으로 계단을 올라가면 안되는 조건이 있기에 dp배열을 두 개 생성해서 하나는 바로 전 계단을 밟은 배열, 나머지는 바로 전 계단을 밟지 않은 배열으로 설정해서 얻을 수 있는 점수의 최댓값을 구하자. import java.util.*; import java.io.*; import java.math.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int N = Integer.parseInt(br..
[백준] 1463 1로 만들기 - Java
[백준] 1463 1로 만들기 - Java
2022.06.29dp문제이다. 초기값으로 1과 2를 설정해주고, dp배열을 채워서 풀 수 있다. 이 때, 항상 3으로 나누는게 가장 좋은 방법이 아닐 수 있다. 2로 나누기, 1빼기 세 가지를 모두 고려해서 dp배열을 채우자. import java.util.*; import java.io.*; import java.math.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int dp[] = new int[1000001]; dp[1] = 0; dp[2] = 1; for(int i=3; i
[백준] 16928 뱀과 사다리 게임 - Java
[백준] 16928 뱀과 사다리 게임 - Java
2022.06.28"최단거리를 구해라" 라는 발문과 그래프 느낌이 나는 문제를 만나면 BFS를 돌리면서 카운트 배열을 채우는 생각을 해 보자. 이런 유형이 많이 나오니.. 반복해서 풀어서 익숙해져야겠다. import java.util.*; import java.io.*; import java.math.*; public class Main { static int N, M; static int count[] = new int[101]; static int[] object = new int[101]; static boolean visit[] = new boolean[101]; public static void main(String[] args) throws IOException { BufferedReader br = new B..