완전 탐색 (Brute Force, Exhaustive Search)
: 모든 경우의 수를 탐색하는 방법
완전 탐색 알고리즘
- 단순 반복 (Brute force)
- 깊이우선탐색 (DFS)
- 너비우선탐색 (BFS)
- 비트마스크 (Bitmask)
- 순열
- 재귀함수
- 백트래킹
이제 브루트포스 예제들을 풀어봅시다~!
예제
백준 2798번 - 블랙잭
예제입출력이 맞는데 틀리다해서 겨우 찾아낸 반례 입력이4 10
1 2 3 10이었고 알고보니 3중 for문 중 가장 안쪽 for문이 j+2로 입력 시
n = 4 인 경우 중복된 숫자로 계산하기 때문이었다... 바보^^
풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Blackjack {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] s= br.readLine().split(" ");
int n = Integer.parseInt(s[0]);
int m = Integer.parseInt(s[1]);
String[] nums= br.readLine().split(" ");
int[] num = new int[n];
for(int i =0;i<n; i++){
num[i] = Integer.parseInt(nums[i]);
}
int ans = 0;
//카드 3장을 더할 때
//카드 1은 j~n-2까지 순회, 2는 j+1~n-1, 3은 k(j+1)+1~n-3까지 순회함
for(int j=0; j<n-2;j++){
for(int k=j+1;k<n-1;k++){
for(int l=k+1; l<n;l++){
int sum = num[j]+num[k]+num[l];
if(sum == m) ans = m;
else if(ans<sum && sum<m){
ans = sum;
}
}
}
}
System.out.println(ans);
}
}
백준 2231번 - 분해합
찾은 반례
86
0if문을 for문 안에 넣어둬서.. 이런 하찮은 실수때문에 ㄴHㄱr 싫어진ㄷr..
86 입력시 79라고 79 + 7 에서 멈춰서 return 해버림!!나는 string으로 자리수나눠서 더했는데
while(x != 0){
sum += x % 10;
x /= 10;
}
처럼 % / 연산으로 더하는게 더 좋을 것 같다풀이
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Decomposition {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int decom = Integer.parseInt(br.readLine());
System.out.print(decomposition(decom));
}
public static int decomposition(int d){
for(int i=1;i<d;i++) {
String s = String.valueOf(i);
int x = i;
for(int j=0;j<s.length();j++) {
x += Integer.parseInt(String.valueOf(s.charAt(j)));
if(x == d){
return i;
}
}
}
return 0;
}
}백준 1018번 - 체스판 다시 칠하기
처음에 경우의 수를 (n-7)*(m-7)만 두고
chess[j][i] 값으로 왼쪽 최상단 색으로 지정하여 tog를 바꿨더니
뒤에서 부터 계산 시 min값이 더 크게 나오는 오류가 있었다.
B로 시작하는 체스판 (n-7)*(m-7) 과 W로 시작하는 체스판 (n-7)*(m-7)
두 가지 경우의 min 값을 모두 계산해야 문제를 풀 수 있다!
오답풀이
import java.io.*;
import java.util.Arrays;
public class PaintChess {
static boolean[][] chess;
static int[] cases;
static int c;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] size = br.readLine().split(" ");
int n = Integer.parseInt(size[0]);
int m = Integer.parseInt(size[1]);
chess = new boolean[n][m];
String[][] line = new String[n][m];
for(int i=0;i<n;i++){
line[i] = br.readLine().split("");
}
for(int j=0;j<n;j++) {
for (int i = 0; i < m; i++) {
if(line[j][i].equals("W")){
chess[j][i] = true;
}else{
chess[j][i] = false;
}
}
}
cases = new int[(n - 7) * (m - 7)];
Arrays.fill(cases,0);
int min = 64;
c=0;
//경우의 수 만큼
for(int j=0;j<n-7;j++) {
for (int i = 0; i < m-7; i++) {
cal(j,i,c);
c++;
}
}
for (int i:cases) {
if(min > Math.min(min,i)) min = Math.min(min,i);
}
System.out.println(+min);
}
public static void cal(int x, int y, int c) {
boolean tog = false;
for (int j = x; j < x + 8; j++) {
for (int i = y; i < y + 8; i++) {
if (j == x && i==y) tog = chess[j][i];
if (chess[j][i] != tog) {
cases[c]++;
if(c==31) System.out.println(c+": "+j+" "+i +" " + chess[j][i]);
}
tog = !tog;
}
tog = !tog;
}
}
}
정답풀이
import java.io.*;
import java.util.Arrays;
public class PaintChess {
static boolean[][] chess;
static int[] black_case;
static int[] white_case;
static int c;
static int min = 64; // min의 최댓값, 전부 다 바꾸는 8*8개로 초기화
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] size = br.readLine().split(" ");
int n = Integer.parseInt(size[0]);
int m = Integer.parseInt(size[1]);
chess = new boolean[n][m];
String[][] line = new String[n][m];
for(int i=0;i<n;i++){
line[i] = br.readLine().split("");
}
for(int j = 0; j < n ; j++) { //화이트색상이 true인 2차원배열 저장
for (int i = 0; i < m ; i++) {
if(line[j][i].equals("W")){
chess[j][i] = true;
}else{
chess[j][i] = false;
}
}
}
/*
8 x 8 을 만들 수 있는 경우의 수:
(8+(n-8)) * (8+(m-8)) 사이즈의 판이라고 볼 때,
판을 88로 쪼갤 수 있는 경우의 수는 (n-7)*(m-7) 인데
B OR W로 시작할 수 있으니 2*(n-7)*(m-7)가 된다.
나는 각각의 배열을 만들어 사용하였다.
*/
black_case = new int[(n - 7) * (m - 7)];
white_case = new int[(n - 7) * (m - 7)];
Arrays.fill(black_case,0);
Arrays.fill(white_case,0);
c=0;
//경우의 수 만큼
for(int j=0;j<n-7;j++) {
for (int i = 0; i < m-7; i++) {
count(j,i,c,black_case,false); //B로 시작하는 체스판 기준으로 바꿔하는 개수 계산
count(j,i,c,white_case,true); //W로 시작하는 체스판 기준으로 바꿔하는 개수 계산
c++; // 경우의수마다 카운트
}
}
getMin(black_case);
getMin(white_case);
//output
System.out.println(min);
}
public static void getMin(int[] arr){
for (int i:arr) {
if(min > Math.min(min,i)) min = Math.min(min,i);
}
}
public static void count(int x, int y, int c, int[] arr, boolean isWhite) {
boolean tog =false;
// 8*8 하나씩 비교해서 계산
for (int j = x; j < x + 8; j++) {
for (int i = y; i < y + 8; i++) {
if (j == x && i==y) tog = isWhite; // 받아온 값으로 왼쪽 최상단 색 정하기
if (chess[j][i] != tog) { //기대하는 bool값과 다르면 카운트세기
arr[c]++;
}
tog = !tog; //다음번엔 반대가 와야함
}
tog = !tog; // 줄바뀌면 같은게 와야되므로 한 번 더 바꿔주기
}
}
}
탐색 전 막간 정리 TIME~~
쉬프트 연산자 정리
a << b = a * 2b
a >> b = a / 2b
((a+b) / 2) == (a+b)>>1집합 포함 여부 검사
AND
집합 & (1 << n) == 2n
이면 집합에 n이 포함
0 이면 미포함
OR
집합 | (1 << n)
집합에 n 추가
순열예제 가장 큰 두자리 수 구하기
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class Search01{ //가장 큰 두자리수구하기
// (선택된 숫자의 개수, 사용된 숫자, 중간계산결과, 배열, 배열의 크기)
static int solve(int cnt, int used, int val, int[] nums, int num){
if(cnt == 2) return val; //선택된 숫자가 2개면 재귀호출 종료하고 지금까지 계산결과 return
int ret =0;
for(int i=0; i<num;i++){
if((used & 1 << i) != 0) continue; // 사용한 적이 있다면, skip
ret = Math.max(ret,solve(cnt+1, used | 1 <<i, val*10+nums[i], nums, num));
}
return ret;
}
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int num = Integer.parseInt(br.readLine());
int[] nums = new int[num];
String str[] = br.readLine().split(" ");
for(int i=0;i<num;i++){
nums[i] = Integer.parseInt(str[i]);
System.out.println(str[i]);
}
System.out.println(solve(0,0,0, nums, num));
}
}
𝐃𝐨𝐧'𝐭 𝐛𝐞 𝐚 𝐩𝐫𝐨𝐜𝐫𝐚𝐬𝐭𝐢𝐧𝐚𝐭𝐨𝐫💫