완전 탐색
문제를 해결하기 위해 확인해야 하는 모든 경우를 전부 탐색하는 방법이다.
그 중에서도 백 트래킹을 통해야 하는 상황을 해결할 때 유용하다.
모든 코테문제에서 기본적으로 접근해 봐야 한다.
장점 : 부분점수를 얻기좋다.
단점 : 전부 탐색하기에 시간 복잡도가 일반적으로 높다.
코테에 나오는 완전 탐색 종류
N개 중
A. 중복을 허용해서
B. 중복없이
M개를
- 순서 있게 나열하기
- 고르기
완전 탐색은 함수 정의가 50%
// Recurrene Function (재귀 함수)
// 만약 M개를 전부 고름 --> 조건에 맞는 탐색을 한 가지 성공한 것!
// 아직 M개를 고르지 않음 --> k번째부터 M번째 원소를 조건에 맞게 고르는 모든 방법을 시도한다.
static void rec_func(int k){}
public static void main(String[] args) {
input();
rec_func(1);
System.out.println(sb.toString());
}1 + A 버전
N개 중 중복을 허용해서 M개를 순서있게 나열하기
import java.io.*;
import java.util.StringTokenizer;
public class MAndN {
static StringBuilder sb = new StringBuilder();
static void input() {
FastReader scan = new FastReader();
N = scan.nextInt();
M = scan.nextInt();
selected = new int[M + 1];
}
static int N,M;
static int[] selected;
//Recurrence Function (재귀 함수)
// 만약 M개를 전부 고름 --> 조건에 맞는 탐색을 한 가지 성공한 것!
// 아직 M개를 고르지 않음 --> k번째부터 M번쨰 원소를 조건에 맞게 고르는 모든 방법을 시도한다.
static void rec_func(int k) {
if (k == M + 1) {
for (int i = 1; i <= M; i++) {
sb.append(selected[i]).append(' ');
}
sb.append('\n');
} else {
for (int cand = 1; cand <= N; cand++) {
selected[k] = cand;
// K=1 번 ~ M번을 모두 탐색하는 일이 발생해야 하는 상황
rec_func(k + 1);
selected[k] = 0;
}
}
}
public static void main(String[] args) {
input();
rec_func(1);
System.out.println(sb.toString());
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws FileNotFoundException {
br = new BufferedReader(new FileReader(new File(s)));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
}2 + A 버전
N개중 중복없이 M개를 순서있게 나열하기
import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;
public class Main {
static int N;
static int M;
static int[] selected;
static boolean[] used;
static StringBuilder sb = new StringBuilder();
static void input() {
final FastReader scan = new FastReader();
N = scan.nextInt();
M = scan.nextInt();
selected = new int[M + 1];
used = new boolean[N + 1];
Arrays.fill(used, false);
}
static void ref_func(int k) {
if (k == M + 1) {
for (int i = 1; i <= M; i++) {
sb.append(selected[i]).append(' ');
}
sb.append('\n');
return;
}
for (int cand = 1; cand <= N; cand++) {
if (used[cand]) {
continue;
}
selected[k] = cand;
used[cand] = true;
ref_func(k + 1);
selected[k] = 0;
used[cand] = false;
}
}
public static void main(String[] args) {
input();
ref_func(1);
System.out.println(sb.toString());
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws FileNotFoundException {
br = new BufferedReader(new FileReader(new File(s)));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
}1 + B 버전
N개 중 중복을 허용해서 M개를 고르기
import java.io.*;
import java.util.StringTokenizer;
public class Main {
static int N,M;
static int[] selected;
static StringBuilder sb = new StringBuilder();
static void input() {
final FastReader scan = new FastReader();
N = scan.nextInt();
M = scan.nextInt();
selected = new int[M + 1];
}
static void ref_func(int k) {
if (k == M + 1) {
for (int i = 1; i <= M; i++) {
sb.append(selected[i]).append(' ');
}
sb.append('\n');
return;
}
for (int cand = 1; cand <= N; cand++) {
if (k != 1 && selected[k - 1] > cand) {
continue;
}
selected[k] = cand;
ref_func(k + 1);
selected[k] = 0;
}
}
public static void main(String[] args) {
input();
ref_func(1);
System.out.println(sb.toString());
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws FileNotFoundException {
br = new BufferedReader(new FileReader(new File(s)));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
}2 + B 버전
N개 중 중복없이 M개를 고르기
public class Main {
static int N,M;
static int[] selected;
static StringBuilder sb = new StringBuilder();
static void input() {
final FastReader scan = new FastReader();
N = scan.nextInt();
M = scan.nextInt();
selected = new int[M + 1];
}
static void ref_func(int k) {
if (k == M + 1) {
for (int i = 1; i <= M; i++) {
sb.append(selected[i]).append(' ');
}
sb.append('\n');
return;
}
for (int cand = selected[k-1] + 1; cand <= N; cand++) {
selected[k] = cand;
ref_func(k + 1);
selected[k] = 0;
}
}
public static void main(String[] args) {
input();
ref_func(1);
System.out.println(sb.toString());
}
static class FastReader {
BufferedReader br;
StringTokenizer st;
public FastReader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
public FastReader(String s) throws FileNotFoundException {
br = new BufferedReader(new FileReader(new File(s)));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
long nextLong() {
return Long.parseLong(next());
}
double nextDouble() {
return Double.parseDouble(next());
}
String nextLine() {
String str = "";
try {
str = br.readLine();
} catch (IOException e) {
e.printStackTrace();
}
return str;
}
}
}
현시깁니다