Algorithm

문제 링크 1. 이전에 풀었던 토마토 문제의 응용문제이다. 2차원 배열이었다면 이번에는 3차원 배열.. 3차원 배열을 너무 오랜만에 써서 맨 앞의 인덱스가 행이었나 면이었나 기억이 안 났다. 또 모두 익을 때까지 며칠이 걸리는지 카운트하는 부분에서 살짝 헤맸다. 2. BFS로 풀었다. dx, dy, dz 배열로 이동할 6가지 방향(상, 하, 좌, 우, 앞, 뒤)을 잡아준다. 1. 배열 전체를 순회하며 익은 토마토가 있는 부분을 queue에 넣는다. 2. queue가 empty일 때까지 다음을 반복한다. 2-1. queue에서 원소를 하나씩 빼서 6가지 방향에 대하여 2-2. 해당 방향에 익지 않은 토마토가 있다면 익게 하고 queue에 넣는다. 단, 익게 할 때 단순히 1로 바꾸는 것이 아니라 이동하기 ..

문제 링크 1. 지나왔던 알파벳인지 파악하는 부분에서 조금 헤맸던 문제. list를 사용하여 전체 순회를 하게 할 수도 있지만, 시간 효율성이 떨어진다. visited 배열을 이용하여 풀면 효율적이다. 2. 이동 거리의 최대값을 찾아야 하므로 백트래킹을 써야 한다. 그렇기 때문에 DFS를 사용하는 것이 효과적이다. visited 배열은 boolean[26] 배열로 해당 알파벳 - 'A'를 한 인덱스를 이용하면 된다. 나머지는 코드를 보면 이해가 될 것이다. 3. import java.util.Scanner; public class Main { static int answer = 0, r, c; static char[][] data; static boolean[] visited = new boolean[2..

문제 링크 1. 어떻게 풀지 조금 고민하다가 문제에서 $N$이 10 이하의 자연수라고 하여서 몇 가지 예를 적어보고 규칙을 찾으면 풀 수 있을 것이라 생각했다. 한 5개 정도 직접 써보며 컴퓨터의 입장에서 어떻게 풀지 고민하였더니 풀렸다. 정답률 $56\%$의 문제로 난이도가 다소 낮은 문제이다. 2. 나는 이 예제를 기준으로 문제를 풀었다. input 5 3 3 0 1 0 output 3 5 4 1 2 1. 1번보다 키가 큰 사람의 수가 3이라면 위치가 3일 수 밖에 없다. (arr인덱스의 0부터 계산) arr 0 0 0 1 0 2. 2번보다 키가 큰 사람의 수가 3이라면 arr 인덱스의 0부터 3개의 빈칸을 두어야 한다. 왜냐하면, 3개의 빈칸에 2번보다 키가 큰 사람을 세워야 하기 때문이다. arr..

문제 링크 1. $(0,0)$부터 끝까지 변환 후 같은지 확인하면 될 것 같은데..라고 생각했지만, 그리디 문제라서 뭔가 좀더 그리디스러운 방법이 존재할 거라고 생각했다. 저 방법 말고는 떠오르지가 않아 방법이 맞는지 해설을 봤더니 맞았다.. 2. 내가 생각했던 데로 $(0,0$에서 부터 끝가지 변환하면 되지만 유의해야 할 점이 있다. $3\times3$ 크기의 부분 행렬을 변환하는 것이라서 $N\times M$ 모두 확인할 필요가 없다. $(0,0$ 에서부터 $(N-3,M-3)$ 까지만 변환하면 된다. 그 이상의 변환은 다시 원래대로 바꾸는 것이므로 불필요한 연산이 된다. 이것을 알았다면 구현은 쉽다. 1. $(0,0$에서부터 $(N-3,M-3)$까지 A와 B의 원소가 다르다면 $3\times3$ 크기..

문제 링크 1. 영상제작 외주를 받아서 잠시 공부를 하지 못했다. 오랜만에 문제를 풀었는데, 문제를 잘못 골랐는지 엄청 힘들었다. 나름 규칙을 찾아 점화식을 세웠는데, 틀렸다. 해설을 찾아 보았는데, 자세한 해설을 적어 놓은 사람을 찾기 힘들었고 적었더라도 이해가 되지 않았다. 풀이 이해하는데만 1시간 넘게 걸린거 같다. 머리가 나쁜건지 문제가 어려운건지.. 이 문제의 정답률은 35% 인데, 좀 높게 잡히지 않았나 싶다. 2. 진짜 엄청 상세한 풀이 블로그를 찾아서 참고에 넣어두었다. 천천히 계속 읽어보자. 3. import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scan..

문제 링크 1. 입력 데이터를 어떻게 처리할지에 대한 고민을 조금 했던 문제이다. 데이터 배열을 만들고 난 후에는 단지번호붙이기 문제와 유사해 쉽게 풀 수 있다. 2. 직사각형의 왼쪽 아래 꼭짓점의 $(x, y)$과 오른쪽 위 꼭짓점의 $(x, y)$가 주어진다. 일단 노트에다가 이를 고려해 찍어보았다. 문제는 이 좌표계를 배열화 시켜야 하는 것인데, 고민해보면 다음과 같은 규칙을 찾을 수 있다. $(2, 0)$ ~ $(4, 4)$ 이라면, data[0][2] ~ data[3][3] $(1, 1)$ ~ $(2, 5)$ 이라면, data[1][1] ~ data[4][1] $(4, 0)$ ~ $(6, 2)$ 이라면, data[4][0] ~ data[1][5] 배열 모양은 좌표계를 x축을 기준으로 대칭시킨 모..

문제 링크 1. 처음 보고 정확한 식은 기억이 안 났지만, 고등학교 확통 시간에 배운 내용이 대략적으로 떠올랐다. 이 문제는 수학과 DP를 섞어 푸는 문제이다. 2. 기억이 안났던 식은 다음 식이였다. $_{n}C_{r}=_{n-1}C_{r-1}+_{n-1}C_{r}$ 이 공식은 파스칼의 삼각형에서도 구할 수 있다. 관련 내용은 아래 참고 블로그에서 공부하자. 3. import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int k = sc.nextInt(); int[][]..

문제 링크 1. 이전에 풀었던 동전 1과 유사한 문제. 해당 문제의 풀이를 보고 복습하며 풀었다. 2. 동전 1 문제의 해설을 보고 이 해설을 보도록 하자. 차이점은 동전 1에서는 k 원을 만들 수 있는 모든 경우의 수를 구하지만, 동전 2에서는 최소한의 동전을 사용해서 만들 때 사용한 동전의 개수를 구하는 문제이다. 이를 위해서 다음과 같은 점화식을 세운다. dp[j] = Math.min(dp[j], dp[j - coin[i]] + 1) 유의할 점은 다음과 같다. 1. dp 배열을 모두 100001로 초기화 한다. 사용한 동전의 개수가 최악일 경우 100,000개이다. (동전의 가치가 최대 100,000원이기 때문이다.) 따라서 이 최대 + 1인 100001로 초기화한다. 2. dp[0] = 0이다. ..