아이디어 백트래킹 알고리즘을 이용해서 현재 위치에서 더 이상 이동할 수 있는 칸이 없다면 이전 칸으로 복귀해 다른 경로를 탐색하는 방식으로 문제를 풀 수 있다. 추가로 문제에서 동일한 경로 상 동일한 알파벳을 여러 번 방문하는 것이 불가능하므로 이를 표현하기 위해 0 : A 25 : Z 를 의미하는 boolean 배열을 visited 배열로 활용하면 문제를 해결할 수 있다. 풀이코드 import java.io.*; import java.util.*; public class Main { static int result = 0; static int[] dx = {-1, 1, 0, 0}; static int[] dy = {0, 0, -1, 1}; static char[][] board; static boole..

아이디어 1. 1 번 노드에서 N 번 노드까지 주어진 두 정점을 반드시 지나치는 경로는 2개가 존재함 - 1 -> node1 -> node2 -> N - 1 -> node2 -> node1 -> N 2. 플로이드-워셜 알고리즘을 사용하면 모든 정점 간의 최단 경로를 알 수 있고 이를 활용해 (1 -> node1) + (node1 -> node2) + (node2 -> N) (1 -> node2) + (node2 -> node1) + (node1 -> N) 값을 비교해 최단 경로를 출력하면 된다. * 시간복잡도가 O(N^3) 이긴 하지만 N의 최대 크기가 800 이므로 800 * 800 * 800 = 64,000,000 이라 1초라는 제한 조건(보통 연산 1억번)을 통과할 수 있을 것이라 예상했는데 아니었..

아이디어 이 문제의 핵심은 크게 2가지이다. 1) 진실을 알고 있는 사람은 함께 파티에 참여한 사람에게 진실을 전파한다 2) 거짓말과 진실을 번갈아 듣는 사람이 있어서는 안된다 따라서 초기에 진실을 알고 있는 사람이 함께 파티에 참여한 사람에게 진실을 전파하고, 이 사람들이 또 파티에 함께 참여한 사람들에게 진실을 전파하는 구조인 것이다. 따라서 함께 파티에 참여한 사람들을 그래프 형태로 만들고 dfs 를 활용해 진실을 전파하면 '진실을 들어야 하는 사람들' 을 알 수 있게 된다. 이후 파티 참가자들을 확인하면서 '진실을 들어야 하는 사람'이 포함된 파티는 진실을 말하고 그렇지 않은 파티는 거짓말을 하면 된다 풀이코드 import java.io.BufferedReader; import java.io.IO..

아이디어 전위 순회 결과를 토대로 이진 트리를 만들고 후위 순회한 결과를 출력하면 된다. 이 때 문제에서 주어지는 이진 트리는 3가지 조건을 만족하는 이진 트리인데 1) 노드의 왼쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 작다 2) 노드의 오른쪽 서브트리에 있는 모든 노드의 키는 노드의 키보다 크다 3) 왼쪽, 오른쪽 서브트리도 이진 검색트리이다. 전위 순회한 결과에서는 가장 먼저 출력된 것이 루트가 되는 노트이고 그 후로 나오는 값들 중 루트보다 작은 것들은 왼쪽 서브트리, 큰 것들은 오른쪽 서브트리에 위치하게 된다. 예제로 주어진 전위 순회 결과에서는 50 이 가장 최상단에 위치한 노드가 되는데 30 < 50 이므로 30 은 50 의 왼쪽 서브 트리에 추가가 된다. 24 < 50 이므로 왼쪽..

아이디어 A 의 한 글자를 골라 문자열의 가장 앞으로 옮기는 연산만을 통해서 A 를 B 로 변환해야 하기 때문에 B 의 마지막 문자부터 탐색해서 A 의 어디에 위치하는지를 알아내고 해당 위치보다 뒤에 있는 문자들은 모두 옮기는 연산을 수행해줘야 한다. BCA CBA 와 같이 문자열이 주어진다면 B[2] 인 'A' 가 동일하게 A[2] 에 위치해있으므로 이는 옮길 필요가 없다. 다음으로 넘어가서 B[1] 과 A[1] 을 비교하면 서로 다른 문자이므로 A[1] 에 위치한 'C' 는 옮겨야 하는 문자가 되는 것이다. 예제로 주어진 ABC CBA 에 대해서 이 과정을 수행해보면 다음과 같다 A[2] != B[2] 이므로 C 는 옮긴다(연산 횟수 : 1) A[1] != B[2] 이므로 B 는 옮긴다(연산 횟수 :..

아이디어 i번째 숫자를 마지막으로 하는 부분 수열은 이전(1 ~ i - 1)에 만든 부분 수열에 i 번째 숫자를 이어붙임으로써 만들 수 있다. dp[i] 를 i 번째 숫자를 마지막으로 하는 부분 수열 중 가장 긴 부분 수열의 길이라고 정의하면 아래와 같은 점화식을 세울 수 있다. dp[i] = 1 ~ i - 1번째 숫자 중 i 번째 숫자보다 큰 경우에 대해 Math.max(dp[j] + 1, dp[i]) 풀이코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { public static void..

아이디어 입력을 토대로 정점 간의 연결 관계를 표현한 그래프를 만들고 촌수를 구해야 하는 대상(시작점)에서 dfs 를 수행한다. dfs 를 수행했을 때 촌수를 구해야 하는 대상(끝점)에 도달하면 현재까지의 depth 를 계산해서 촌수를 출력하면 되고 만약 도달하지 못하면 -1 을 출력하면 된다. 풀이코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; public class Main { static int target1; static int target2; static int[][] graph; static boolean[][]..

아이디어 어떤 지원자의 서류 성적이 N 등이라면 이 지원자가 합격하기 위해서는 서류 기준 1 ~ N - 1 등의 면접 성적 중 가장 높은 성적보다 더 좋은 성적을 받아야 한다. 그렇지 않으면 다른 지원자 중 자신보다 서류 성적도, 면접 성적도 높은 지원자가 존재하게 되기 때문이다. 따라서 서류 성적 기준으로 지원자를 정렬하고 면접 성적을 비교하며 나보다 서류 성적이 높은 지원자 중 가장 좋은 면접 성적과의 비교를 통해 합/불 여부를 결정한다. 풀이코드 import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.List;..