Algorithm
격자 탐색
격자 탐색
2022.07.21시뮬레이션 유형에서 많이 등장하는 내용이다. dr = {-1, 1, 0, 0} dc = {0, 0, -1, 1} dr dc배열을 선언하고 탐색 시 사용한다. (문제에 따라 숫자를 넣는 순서는 바뀔 수 있다..) ex.1) 배열에 그림과 같이 숫자를 넣는 경우를 생각해보자. import java.io.*; import java.util.*; public class Main { static int[] dr = {1,0,-1,0}; static int[] dc = {0,-1,0,1}; public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System..
[백준] 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..
row, column / x, y
row, column / x, y
2022.07.12이차원 배열을 설정하고 좌표평면을 탐색할 때 r,c로 탐색할지 / x,y로 탐색할지.. 사실 두 가지 모두 같은 말이긴 하다. 문제에 따라서 다른 방법으로 접근하면 좋다. 수학에서 그래프 그리듯 접근할 때는 x y를 사용하고, 행렬 느낌으로 접근할 때는 r c를 사용하면서... 이에 따라서 탐색에 유용한 dx dy dr dc배열도 새롭게 정의해 줄 수 있다. 나는 r,c를 자주 사용하긴 하지만 문제에 따라서는 x,y로 보고 풀어야 할 때도 있다.
dp팁
dp팁
2022.07.09당연한거지만.. 문제 많이 풀어보는게 정말 많이 도움 됨. 점화식 잘 안나오면 하나하나 종이에 하나하나 해보기. 수능수학에서 수열 문제 풀듯.. 일단 적은 후 규칙 찾는 방법 괜찮음. 규칙이 대충 보이면 dp배열 디자인하기.
[백준] 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
Dynamic Programming
Dynamic Programming
2022.06.29문제의 크기를 변화시켜 작은 문제의 결과를 이용해 큰 문제의 정답을 계산하는 알고리즘이다. 우선은 완전탐색으로 풀 수 있는지 확인하고, 시간을 줄일 때 다이나믹 프로그래밍 방법을 적용하는걸 고려해 보자. 1. 작은 문제 정의하기 전체 문제를 바탕으로 좀 더 쉽게 구할 수 있는 작은 문제를 정의한다. 2. 검증 작은 문제가 전체 문제를 해결할 때 도움이 되는지 확인한다. 3. 정의한 작은 문제를 해결할 때 사용되는 초기값을 설정하자. 몇 가지 값들은 쉽게 구할 수 있다. 4. 규칙을 찾아 점화식을 작성한다. 초기값을 이용해 값들의 규칙을 찾고, 이를 식으로 표현해 모든 값들에 대해 답을 얻는다. 5. 큰 문제 해결하기 여기서 점화식을 작성하는게 까다로운데.. 유형이 그렇게 다양하지 않다. 여러 문제를 풀어..
[백준] 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..