![]()
[백준] 10974번 - 이전 순열 (JAVA) [접근 방법] 바로 이전 문제인 문제를 정확히 반대되는 문제이다. 7 3 2 7 1 4 5 6 주어진 순열 : [ 3 , 2 , 7 , 1 , 4 , 5 , 6 ] 1. 주어진 순열에 마지막 원소를 포함하는 을 찾는다. (A[i] = i 이고, A[j] < A[i-1] 인 가장 큰 j 를 찾는다. [ 3 , 2 , 7 , 1 , 4 , 5 , 6 ] j = 6 (A[j] = 6 < A[i-1] = 7) 3. SWAP (A[i-1] , A[j]) [ 3 , 2 , 6 , 1 , 4 , 5 , 7 ..
![]()
[백준] 10974번 - 모든 순열 (JAVA) [접근 방법] 입력된 N에 따라 1 ~ N 의 수로 이루어진 순열을 모두 출력하는 문제는 와 비슷한 문제였다. dfs 함수를 생성한 후, N개의 숫자로 이루어진 순열을 중복없이 출력하였다. [JAVA 코드] // 10974번 - 모든 순열 import java.util.*; import java.io.*; public class Main { static int[] arr; static boolean[] visit; static int N; static StringBuilder sb; public static void dfs(int depth){ if (depth == N){ for(int val : arr){ sb.append(val).append(" ")..
![]()
[백준] 10972번 - 다음 순열 (!) (JAVA) [접근 방법] 처음 생각한 방법은 문제 처럼 DFS를 사용하여 만든 순열을 List에 저장하고, List를 탐색하여, 주어진 순열의 다음 차례에 오는 순열을 찾아내면 된다고 생각했다. 그러나 이러한 방법을 사용하는 경우 "메모리 초과" 가 발생한다. 여러 사람의 풀이를 참고하여 종합한 방법은 다음과 같다. 10 4 6 2 7 9 8 5 3 1 1. 주어진 배열에서 마지막 원소를 마지막으로 하는 가장 긴 감소수열을 찾는다. (arr[i-1] i = 4 2. j >= i 이면서, arr[j] > arr[i-1]을 만족하는 가장 큰 j 찾기 [4, 6, 2..
![]()
[백준] 15663번 - N과 M (9) (!) (JAVA) [접근 방법] 중복되는 수열을 여러번 출력해서는 안되고, 수열을 사전순으로 증가하는 순서로 출력해야 한다. 이전 문제와 다른 점은 "둘째 줄에 주어지는 N개의 수" 가 "중복 가능" 하다는 것 이다. 예제 2의 N개의 수를 입력받은 배열인 num = {1, 7, 9 ,9}로 정렬 시킬 수 있다. 기존 방식대로 출력한다면, 1 7 1 9 1 9 7 1 7 9 7 9 9 1 9 7 9 9 9 1 9 7 9 9 로 출력된다. 9가 2개 입력되면서, 출력되는 수열에서 중복이 생기게 되었다. 따라서 같은 값을 추가하여도 (중복된 데이터를 넣어도) 무시하는 Set 을 사용하여야 한다. LinkedHashSet을 사용하여 문제를 해결하였다. [JAVA 코드..
![]()
[백준] 15649번 - N과 M (1) (!) (JAVA) [접근 방법] 참 간단해 보이는 문제인데, 손도 못대겠어서 상당히 당황하였다. DFS를 그래프 탐색 알고리즘으로만 알고 있어서, 이러한 문제에도 활용할 수 있는지 몰랐다. DFS를 이용한 다른 사람의 풀이를 참고하였다. 먼저, DFS에 필요한 변수들이 있다. 방문 여부를 판단할 boolean "visit 배열", M개의 숫자의 수열을 저장할 int "arr 배열", 문제에서 입력으로 주어지는 N, M 과 그래프의 깊이를 나타내는 depth 변수이다. static int[] arr; // M개의 숫자로 이루어진 수열 저장 static boolean[] visit; // 방문여부를 기록. static StringBuilder sb; // 출력을 위..
![]()
[백준] 14500번 - 테크로미노 (!) (JAVA) [접근 방법] 브루트포스 파트이기에 모든 경우의 수를 탐색해야 한다는 것은 알고있었다. 어떻게 탐색 할 것인가? 가 가장 어려웠다. 첫번째로 고려한 방법은 모든 경우를 일일이 생각하여 구현하는 방법이다. (i , j)를 시작으로 하는 모든 경우의 수를 전부 고려한 후, 그중 최댓값을 구해서 N X M 보드의 모든 칸의 최대값을 비교하여 갱신할 계획이였다. worst case = 500 * 500 * 13 = 3,250,000 으로 시간도 적합했다. 그러나 너무나 까다롭고 귀찮은 구현에 포기하였다. 두번째 고려한 방법은 다른 사람들의 풀이 방법을 보고 풀었다. 위 4가지 도형은 상하좌우 완전 탐색으로 구현하고, 이 모형만 따로 구현하는 방법이다. 탐색..
