mondegreen

동일한 숫자는 카운트하지 않기 때문에 set을 활용해야겠다고 판단했다. 숫자를 고르는 방법은 특정 인덱스를 기준으로 뒤의 숫자만 고르게 하려고 했었다. 그런데 이렇게 처리하게되면 뽑은 숫자마다 순서를 직접 달리 배치해봐야 하는 번거로움이 발생한다. 따라서 방문 배열을 생성하고 해당 숫자를 뽑았는지를 체크하며 고르고 모든 인덱스를 순회하도록 처리했다. 이렇게 처리하면 모든 숫자를 순회하는 대신 뽑은 숫자 간의 숫자를 바꿔서 배치할 필요가 없다. k개의 카드만 뽑아야 하므로 cnt 변수로 뽑은 숫자를 관리했다. package BaekJoon.backtracking; import java.util.Arrays; import java.util.HashSet; import java.util.Scanner; pub..

백트래킹의 개념 해를 찾는 도중 해가 아니면, 되돌아가서 다시 해를 찾아가는 방법 => 모든 가능한 경우의 수 중 특정한 조건을 만족하는 경우만 살펴보는 방법 => 만족하지 않는 것이 확인되면 부모 노드로 돌아가 다음 자식 노드를 확인한다. => 가지치기라고 말하는데 불필요한 부분을 굳이 연산하지 않아 효율적이다. => 최악의 경우에는 여전히 지수함수 시간을 요할 수 있어 반드시 답을 얻는 것은 아님 깊이우선탐색(DFS) + 가지치기(Pruning) DFS만으로는 답이 될 수 없는 경우도 모두 리프까지 탐색하므로 이 때 특정 조건문을 작성하여 조건에 해당하지 않으면 해당 경로를 가지는 않는 가지치기 방식을 적용해 백트래킹을 구현할 수 있다. 백준 9663 import java.util.Scanner; p..

순서 X 중복 X 서로 다른 n개의 원소 중 r개의 순서없이 골라낸 것 import java.util.Scanner; public class Main { static int n, m; static int[] arr; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); arr = new int[m + 1]; rec(1); sc.close(); } private static void rec(int idx) { // 기저조건 if (idx == m + 1) { for (int a = 1; a < arr.length; a++) { System.out.print(..

순서 O 중복 X 서로 다른 것들 중 몇 개를 뽑아서 나열하는 것 import java.util.Scanner; public class Main { static int n, m; static int[] selected; static boolean[] used; public static void main(String[] args) { Scanner sc = new Scanner(System.in); n = sc.nextInt(); m = sc.nextInt(); selected = new int[m + 1]; used = new boolean[n + 1]; rec(1); sc.close(); } private static void rec(int idx) { // 기저조건 if (idx == m + 1) {..