문제 링크 1. 많이 풀어 봤던 기본적인 그래프 문제. 유기농 배추 문제와 매우 유사해서 쉽게 풀었다. 테스트 케이스는 다 맞고, 전혀 틀린 부분이 없는데 오답처리가 나길래 골치가 아팠다. 원인은 내가 잠시 수정했던 범위였는데 이런 어이없는 실수는 하지 않도록 주의하자. 2. 풀이는 유기농 배추 문제를 참고하면 될 것 같다. (링크 걸어 놓았음) 단, 이 문제에서는 4 방향이 아닌 8 방향을 모두 검사하여야 한다. 3. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Main { static int w, h; static int[][] area; public static void main(..

문제 링크 1. 처음 문제를 보았을 때, 방향 그래프 인접 행렬이라는 점에서 조금 복잡하게 생각했다. 2. 자료구조 수업시간 때 인접 리스트 구성한 것을 떠올려 보면, 무방향 그래프에서 1에서 2로 가는 간선이 있다면 2에서 1로 가는 간선도 인접 리스트에 추가를 했었다. 방향 그래프라면 1에서 2로 가는 간선만 추가할 것이다. 이를 통해 그냥 배열을 순회하는 기본적인 BFS 문제와 다를 게 없다고 판단했다. 다만 사이클 생기는 부분을 주의해야 할 것이다. $0$번째 행부터 $n-1$번째 행까지 각 행에 대하여 BFS 탐색을 한다. 3. import java.util.LinkedList; import java.util.Queue; import java.util.Scanner; public class Ma..

https://www.acmicpc.net/problem/14502 1. 한 2.5시간 정도 소요되었던 것 같다. 처음 문제를 보았을 때, 지금까지 풀었던 그래프 문제 알고리즘을 모두 적용하면 풀 수 있을 것이라 생각해서 코드를 써내려 갔다. 근데 코드를 써내려 가면서도 이중 for 문이 너무 많이 나와 비효율적이지 않을까 생각했지만, 시간제한이 2초이므로 문제없다고 판단했다. (사실 코드 써 내려가면서 갸우뚱만 3번 정도 한 듯..) 근데 답이 출력되지 않아 고민해보니 벽을 세우는 알고리즘을 잘못 선택했다는 것을 알아챘다. 조합 알고리즘을 잘못 작성하였다. 이 부분은 이전에 풀었던 조합 문제를 떠올려 적용하려고 했지만, 2차원 배열의 조합 구하는 것은 처음 접하여 풀이를 참고하였다. 2. 문제의 메커니..

https://www.acmicpc.net/problem/11724 1. 학교에서 자료구조 수업시간에 배운 내용이다. 시험 준비할 때 중요하다고 생각해서 공부해두었기에 생각이 났다. (정○○ 교수님 수업 정말 알차게 열정적으로 해주셔서 감사합니다..) 2. 기본적인 DFS 탐색을 하되, 연결되지 않은 그래프는 한 번에 탐색되지 않는다. 따라서 방문하지 않은 노드를 찾아 DFS를 수행한다. 수업할 때 공부했던 자료를 참고하자. 3. import java.util.Scanner; public class Main { static int[][] graph; static boolean[] visited; public static void main(String[] args) throws Exception { Sca..

https://www.acmicpc.net/problem/1012 1. 문제를 처음 읽었을 때, 테스트 케이스 2의 결과가 2라는 것이 이해가 가지 않았다. 문제를 다시 천천히 읽어보고 해석해보니 결국 모여있는 배추 집합의 수를 구하는 문제였다. 전에 풀었던 '백준 2667 : 단지 번호 붙이기' 문제와 유사하다는 것을 알 수 있었다. (그때는 C언어로 풀었는데 이번에는 Java로 풀어보게 되네.. 확실히 망할 포인터 쓰는 C보다는 Java가 더 편리한 것 같다.) 2. BFS 방식을 사용했다. 문제를 풀고 DFS 풀이를 찾아보았는데, 코드가 더 깔끔했고 문제의 $N, M$ 범위가 작아 DFS로 풀어도 시간 초과하지 않는다는 것을 알 수 있었다. 문제는 다음과 같은 메커니즘을 택했다. 1. 배열의 모든 ..

https://www.acmicpc.net/problem/11057 1. 무슨 문제인지는 모르겠지만 전에 풀었던 문제와 유사하다는 느낌을 받았다. 점화식 규칙을 찾으려고 공책에 $n=3$ 일 경우까지 모두 적어보았다. 2. dp배열을 2차원으로 구성하는 것이 핵심이다. 행은 n을 나타내고 열은 0부터 9까지의 수를 나타내는데, 각 배열의 원소는 해당 열로 끝나는 숫자로 나타낼 수 있는 경우의 수이다. 위 그림은 $n=3$일 경우 만들어지는 dp 배열이다. 이를 점화식으로 나타내면 다음과 같다. dp[i][j] = (dp[i - 1][j] + dp[i][j - 1]) 왜 이렇게 점화식을 세웠는지 다음 그림을 통해 알아보자. $(3, 2)$ 에서 주황색 부분은 $(2, 2)$의 원소 맨 앞에 $0$을 붙여준..

https://www.acmicpc.net/problem/9465 1. 큰 수를 먼저 선택하면 될까? 반례가 존재하고 DP 문제이기에 잘못된 접근 방식이었다. 큰 문제를 작은 문제로 쪼개어 점화식을 세워야 했는데, 어려웠다. 2. 떼어낼 스티커를 선택하는 방법에는 두 가지가 있다. 1. 왼쪽 대각선에 위치한 스티커를 떼어냈을 경우 2. 왼쪽 왼쪽 대각선에 위치한 스티커를 떼어 냈을 경우 이 두 가지 경우 중 최대값을 선택하여 dp 배열에 저장한다. 여기서 이해가 어려웠던 것은 (1, 3)을 선택하는 경우도 존재 하지 않는가? 였다. 이에 대한 답은, (0, 4)에서 이미 이를 고려했기에 고려하지 않아도 된다. 이 두 가지 방법을 점화식을 나타내면 다음과 같다. dp[0][j] = Math.max(dp[1..

https://www.acmicpc.net/problem/1931 1. 문제를 처음 보았을 때 저번에 프로그래머스에서 풀었던 단속 카메라 문제와 유사하다고 생각했다. 그러나 해당 문제의 풀이법을 잊었을 뿐 더러, 그 문제를 다시 풀어보았지만 이 문제에 적용시키기에 어려움을 느꼈다. 2. 이 문제를 풀기에는 다음과 같이 세 가지의 탐욕적 사고 방법이 있다. 회의 시작 시간을 기준으로 회의 종료 시간을 기준으로 회의 소요 시간을 기준으로 이 세가지 방법 중 첫 번째와 세 번째 방법은 반례가 존재하므로, 두 번째 방법을 선택한다. 회의가 빨리 종료되는 순으로 오름차순 정렬을 하여 선택을 하는데, 다음 선택할 회의의 시작 시간이 그 전 회의의 종료 시간보다 빠르면 선택하지 않는다. 3. import java.u..