완전탐색 - 총정리
- 문제를 풀 떄 항상 정답의 최대치를 파악하라!
연산자 끼워넣기 풀이
import java.io.*;
import java.util.*;
public class Main {
static FastReader scan = new FastReader();
static StringBuilder sb = new StringBuilder();
static void input() {
N = scan.nextInt();
nums = new int[N + 1];
operators = new int[5];
for (int i = 1; i <= N; i++) nums[i] = scan.nextInt();
for (int i = 1; i <= 4; i++) operators[i] = scan.nextInt();
max = Integer.MIN_VALUE;
min = Integer.MAX_VALUE;
}
static int N, max, min;
static int[] nums, operators, order;
// 피연산자 2개와 연산자가 주어졌을 때 계산해주는 함수
static int calculator(int operand1, int operator, int operand2){
// value, order[i], num[i+1]
if (operator == 1) // +
return operand1 + operand2;
else if (operator == 2) // -
return operand1 - operand2;
else if (operator == 3) // *
return operand1 * operand2;
else // /
return operand1 / operand2;
}
// order[1...N-1] 에 연산자들이 순서대로 저장될 것이다.
// k-1 번째 연산자까지 계산한 결과가 value 이다.
static void rec_func(int k, int value) {
if (k == N) {
// 완성된 식에 맞게 계산을 해서 정답에 갱신하는 작업
max = Math.max(max, value);
min = Math.min(min, value);
} else {
// k 번째 연산자는 무엇을 선택할 것인가?
for (int cand = 1; cand <= 4; cand++){
if (operators[cand] >= 1){
operators[cand]--;
rec_func(k + 1, calculator(value, cand, nums[k + 1]));
operators[cand]++;
}
}
}
}
public static void main(String[] args) {
input();
// 1 번째 원소부터 M 번째 원소를 조건에 맞게 고르는 모든 방법을 탐색해줘
rec_func(1, nums[1]);
sb.append(max).append('\n').append(min);
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;
}
}
}
N Queen 알고리즘 풀이
- 백트래킹 이용
- N개 중에서 중복을 허용해서 N개를 순서대로 나열하는 모든 경우 탐색
• N Queen 해답 예시
| Queen | ||||
| Queen | ||||
| Queen | ||||
| Queen | ||||
| Queen |
import java.io.*;
import java.util.*;
public class Main {
static FastReader scan = new FastReader();
static StringBuilder sb = new StringBuilder();
static void input() {
N = scan.nextInt();
col = new int[N + 1];
}
static int N, ans;
static int[] col;
static boolean attackable(int r1, int c1, int r2, int c2) {
if (c1 == c2) return true;
if (r1 - c1 == r2 - c2) return true;
if (r1 + c1 == r2 + c2) return true;
return false;
}
static void rec_func(int row) {
if (row == N + 1) {
ans++;
} else {
for (int c = 1; c <= N; c++) {
boolean possible = true;
// valid check (row, c)
for (int i=1;i<=row-1;i++){
// (i, col[i])
if (attackable(row, c, i, col[i])){
possible = false;
break;
}
}
if (possible) {
col[row] = c;
rec_func(row + 1);
col[row] = 0;
}
}
}
}
public static void main(String[] args) {
input();
// 1 번째 원소부터 M 번째 원소를 조건에 맞게 고르는 모든 방법을 탐색해줘
rec_func(1);
System.out.println(ans);
}
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;
}
}
}
부분 수열 : 수열의 일부 항을 선택해서 원래 순서대로 나열진 부분 수열 : 아무것도 안고르는 경우는 뺀 부분수열
부분 수열의 합 풀이
import java.io.*;
import java.util.*;
public class Main {
static FastReader scan = new FastReader();
static StringBuilder sb = new StringBuilder();
static void input() {
N = scan.nextInt();
S = scan.nextInt();
nums = new int[N + 1];
for (int i = 1; i <= N; i++) nums[i] = scan.nextInt();
}
static int N, S, ans;
static int[] nums;
// k번째 원소를 포함시킬 지 정하는 함수
// value:= k-1 번째 원소까지 골라진 원소들의 합
static void rec_func(int k, int value) {
if (k == N + 1) { // 부분 수열을 하나 완성 시킨 상태
// value 가 S 랑 같은 지 확인하기
if (value == S) ans++;
} else {
// k 번째 원소를 포함시킬 지 결정하고 재귀호출해주기
// Include
rec_func(k + 1, value + nums[k]);
// Not Include
rec_func(k + 1, value);
}
}
public static void main(String[] args) {
input();
// 1 번째 원소부터 M 번째 원소를 조건에 맞게 고르는 모든 방법을 탐색해줘
rec_func(1, 0);
// ans 가 정말 "진 부분집합"만 다루는 지 확인하기
if (S == 0){
ans--;
}
System.out.println(ans);
}
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;
}
}
}
재귀 함수의 정의를 통한 완전 탐색 알고리즘 풀이를 구현해보았다 완전 탐색이라는 것 자체가 아직 익숙하진 않지만
반복과 이해하기를 중점으로 다시 해봐야겠다.
본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.
패스트캠퍼스 [직장인 실무교육]
프로그래밍, 영상편집, UX/UI, 마케팅, 데이터 분석, 엑셀강의, The RED, 국비지원, 기업교육, 서비스 제공.
fastcampus.co.kr
'알고리즘 챌린지' 카테고리의 다른 글
| 패스트캠퍼스 챌린지 23일차 (0) | 2022.02.15 |
|---|---|
| 패스트캠퍼스 챌린지 22일차 (0) | 2022.02.14 |
| 패스트캠퍼스 챌린지 20일차 (0) | 2022.02.12 |
| 패스트캠퍼스 챌린지 19일차 (0) | 2022.02.11 |
| 패스트캠퍼스 챌린지 18일차 (0) | 2022.02.10 |