[백준] 11. Brute Force - Java 코드

https://www.acmicpc.net/step

단계별로 풀어보기

 

BruteForce (무차별 공격)

• 암호학에서 비밀번호를 찾는 방법론.
• 조합 가능한 모든 경우를 하나씩 다 대입해 보는 방식으로 암호를 해독하는 방법.
• 브루트 포스 공격(brute force attack) , 키 전수조사(exhaustive key search), 무차별 대입 공격, 완전 탐색 등으로도 부른다.
• 알고리즘의 대다수의 문제가 브루트 포스와 같이 경우를 완전 탐색하며 해를 구하는 문제이다.
• 브루트 포스의 특 장점은 해를 구하는 탐색과정을 병렬로 수행 가능하다는 점이다.
• 해당 방법론이 적용된 구현 알고리즘은 아래와 같다.
  • 선형 : 배열과 같은 선형 구조를 전체적으로 탐색하는 순차 탐색
  • 비선형 : 비선형 구조를 탐색하는 깊이 우선 탐색(DFS, Depth First Search) 과 너비 우선 탐색(BFS, breadth first search) 이 있다.

 

2798 블랙잭

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
// 14,252 KB	 128ms
public class 블랙잭 {
    // 전역변수 선언
    static int [] arr;
    static int N,M,ans=0;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); // 사용법 필수암기, throws IO익셉션
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        // input
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        arr = new int[N];
        arr = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        // 3개 뽑기 완전탐색
        for(int i=0;i<N;i++)
            bruteForce(arr[i],i+1,1);
        // 결과 출력
        System.out.println(ans);
    }
    private static void bruteForce(int sum, int i,int cnt){ // 선택값 합,선택 번호 ,선택갯수
        if(cnt==3 && sum<=M) { // 3개 모두선택, 값이 안넘었으면 결과저장
            ans = Math.max(ans, sum);
            return;
        }
        if(i==N || cnt==3) return;  // 3개 선택끝, 배열 끝번호인 경우 종료
        for(;i<N;i++)
            bruteForce(sum+arr[i],i+1,cnt+1);
    }
}
/*
* 입력의 경우는 확실히 Scanner 보다는 BufferedReader 가 빠른 걸 볼 수 있다.
* 알고리즘의 경우 데이터가 워낙 적어 사실상 성능차는 안보이는 것 같다.
* */

3개를 선택하는 문제이며,

재귀적으로 선택하도록 구현하였다.

 

2231 분해합

import java.util.Scanner;
// 74520 kb	, 332 ms
public class 분해합 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        sc.close();
        for(int i=1;i<n;i++) {
            if (n == Constract(i)) {
                System.out.println(i);
                return;
            }
        }
        System.out.println(0);
    }
    public static int Constract(int n){
        int a=n;
        String tmp = Integer.toString(n);
        for (char c : tmp.toCharArray()) {
            a+= Character.getNumericValue(c);
        }
        return a;
    }
}

 

7568 덩치

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
//14,116kb	128ms
public class 덩치2 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[][] arr = new int[N][2];
        String[] str;
        for(int i = 0; i < N; i++) {
            str = br.readLine().split(" ");
            arr[i][0] = Integer.parseInt(str[0]);	// [i][0] : 몸무게
            arr[i][1] = Integer.parseInt(str[1]);	// [i][1] : 키
        }
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < N; i++) {
            int rank = 1;
            for(int j = 0; j < N; j++) {
                if (i == j) continue;
                if (arr[i][0] < arr[j][0] && arr[i][1] < arr[j][1]) {
                    rank++;
                }
            }
            sb.append(rank).append(' ');
        }
		System.out.println(sb);
    }
}
/*
* 쉬운걸 왜 어렵게 접근했을까...
* 정말 단순히 input이 50개 밖에 안되니깐 배열에 넣고,
* 자기보다 큰게 있을때마다 ++로 랭크를 하나씩 낮춰주면서 붙여주면되는데..
* 왜 Class를 만들고, Sorting을 해주면서 계산했는가..;;
* */

처음에는 배열을 무식하게 순회하고 싶지 않았다.

클래스를 만들어서 정렬해주며 풀었지만, 결과가 좋지않아 브루트포스의 개념을 다시 잡는 문제가 되었다.

 

1018 체스판 다시 칠하기 ★★★

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
// 14288 kb , 132ms
public class 체스판다시칠하기 {
    static char[] check = {'W', 'B'};
    static char[][] chess;
    public static void main(String[] args) throws IOException {
        // input 받기
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] t = br.readLine().split(" ");
        int n = Integer.parseInt(t[0]), m = Integer.parseInt(t[1]);
        chess = new char[n][m];
        for (int i = 0; i<n ; i++) {
            char[] chars = br.readLine().toCharArray();
            for (int j = 0; j < m; j++) {
                chess[i][j] = chars[j];
            }
            // System.arraycopy(chars, 0, chess[i], 0, m); // 이렇게도 가능
        }
        // 순회하기
        int res = 0, min=64;
        for (int i = 0; i<= n-8 ; i++) {
            for (int j = 0; j <= m-8; j++) {
                res = chessCount(i,j);
                min = Math.min(min,res);
            }
        }
        // 결과 출력
        System.out.println(min);
    }
    //
    public static int chessCount(int a, int b){
        int res = 0;
        for (int i = a; i < a+8; i++) {
            for (int j = b; j < b+8; j++) {
                if (chess[i][j] == check[(i + j) % 2])
                    res++;
            }
        }
        res = Math.min(64 - res, res);
        return res;
    }
}

나는 이 문제가 제일 어려웠다.

처음에 8x8 로 잘라낸다는 내용을 보지못하고 구현했었다가, 

모든 경우를 전부 순회해야함을 깨닫고 count해주는 부분을 함수로 뺐다.

 

1436 영화감독 숌

import java.util.Scanner;
// 87780kb	364ms
public class 영화감독숌 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int cnt = 0,i=0;
        while(cnt<n){ // bruteforce
            i++;
            if(Integer.toString(i).contains("666"))
                cnt++;
        }
        System.out.println(i);
    }
}

이 또한 처음에 잘못 생각하여

6을 만날때마다 20씩 늘어나는데, 한자리가 커질때마다 x10이 되는 점화식을 구하고 있었다.

하지만, 정말 단순하게 반복문을 통해 시간을 고려하지않고 풀 수 았는 문제였다.

 

말 그대로 무차별 공격이다.