[ 백준 단계별 알고리즘 ] 브루트 포스(Brute Force) - JAVA

 

완전탐색(Exhaustive Search)

: 가능한 모든 경우의 수를 전부 탐색하여 문제를 해결하는 방법

• Brute Force : 반복문이나 조건문을 사용하여 가능한 모든 경우를 하나씩 모두 테스트하는 방법
• 순열(Permutation) : 주어진 n개의 원소 중에서 r개의 원소를 선택해 순서대로 나열하는 모든 경우의 수를 찾는 방식 -> 조합, 순서문
• 재귀 : 재귀 호출을 통해 문제를 여러 작은 하위 문제로 분할하여 해결하는 방법 -> DFS(깊이 우선 탐색)
• 비트 마스크(Bit Mask) : 이진수를 이용하여 특정 상태나 조합을 표현하는 기법
• BFS(너비 우선 탐색), DFS(깊이 우선 탐색) : 그래프의 노드탐색 기법

 

Brute Force의 사용조건

• 달성하고자 하는 솔루션이 명확함
• 풀이의 수가 제한

 

[ 백준 2798 ] 블랙잭

https://www.acmicpc.net/problem/2798

 

n장의 카드를 배열로 선언하여 값을 저장한뒤 서로다른 3장이 조합되어 이룰 수 있는 모든 합의 값(sum)을 얻은 후 목표값과 최소의 차이(minDiff)을 가지는 것을 도출한다.(minSum)

막혔던 점 : 3개 조합합이 되는 sum은 중첩반복문이 다같이 돌아가는 1사이클에서 초기화해야한다.

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    int[] nums = new int[n];
    for(int i=0; i<n; i++) nums[i] = sc.nextInt();

    int minDiff = Integer.MAX_VALUE;
    int minSum = 0;
    
    for(int i=0; i<n; i++){
      for(int j=i+1; j<n; j++){
        for(int k=j+1; k<n; k++){
          int sum = nums[i] + nums[j] + nums[k]; //3개 조합의 합, 한번 반복마다 갱신
          if(sum <= m) { //m보다 작거나 같을때만 갱신
            int diff = m - sum;
            if( diff < minDiff ) {
              minDiff = diff;
              minSum = sum;
            }
          }
        }
      }
    }

    System.out.println(minSum);
    sc.close();
}
}

 

[ 백준2231 ] 분해합

https://www.acmicpc.net/problem/2231

 

주어진 숫자(n)를 분해합으로 만들어낼 수 있는 가장작은 값의 생성자를 찾는 문제이다.

생성자는 여러개일 수 있지만 주어진 숫자보다 항상 작은 값을 가지므로( 범위제한 ) 0에서 n까지 반복문을 돌리면서 가장먼저 생성자 조건을 만족하는 숫자를 구해본다.

반복문의 숫자가 n까지 도달했을때까 생성자 조건을 만족해지 못했다면(break못함) 생성자가 없는 수 이므로 0을 출력한다. 

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();

    for(int i=0; i<=n; i++){
      int j = i;
      int sum = i;
      while(j>0){
        sum += (j%10);
        j /= 10;
      }
      if(sum==n){
        System.out.println(i);
        break;
      }

      if(i==n){
        System.out.println(0);
        break;
      }
    }
    
    
  }
}

 

[ 백준 19532 ] 수학은 비대면강의입니다.

https://www.acmicpc.net/problem/19532

 

연립방정식의 해를 구하는 문제이다.

 

다음과 같은 방식으로 풀었을때 소수점 오차와 관련한 문제가 발생했다. 자바에서 double 타입은 부동소수점 연산을 하기에 아주 미세한 소수점 오차가 발생할 수 있다고 한다. 따라서 정수값을 통해 정수해를 구하는 문제에서는 정수연산이 그대로 유지되어야 했다.

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();
    int d = sc.nextInt();
    int e = sc.nextInt();
    int f = sc.nextInt();

    /*
    by = c - ax
    y = c/b - a/bx

    ey = f - dx
    y = f/e - d/ex

    c/b - a/bx = f/e - d/ex
    (d/e - a/b) x = f/e - c/b
    x = (f/e - c/b) / (d/e - a/b)
    */
    double x = ((double)f / e - (double)c / b) / ((double)d / e - (double)a / b);
    double y = (double)c / b - (double)a / b * x;

    System.out.println(x+" "+y);


  }
}

 

해당 연립방정식은 단하나의 해답쌍을 가지고, 각 x,y값은 제한된 범위를 가지기에,

brute force 방식으로 주어진 범위내의 x, y값을 직접 대입하여 조건을 만족하는 것을 찾는 방법이 가장 적합했다.

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int a = sc.nextInt();
    int b = sc.nextInt();
    int c = sc.nextInt();
    int d = sc.nextInt();
    int e = sc.nextInt();
    int f = sc.nextInt();

    for(int x=-999; x<=999; x++){
      for(int y=-999; y<=999; y++){
        if(a*x + b*y == c && d*x + e*y == f){
          System.out.println(x+" "+y);
          return;
        }
      }
    }


  }
}

 

[ 백준 1018 ] 체스판 다시칠하기

https://www.acmicpc.net/problem/1018

 

8X8 사이즈의 체스판을 만족하기 위해서는 2가지 케이스가 존재하고 그 경우를 각각 2차원 배열로 선언하였다.(case1, case2 )

그리고 원본 2차원 배열(board)에서 8X8 형태가 나타나는 영역들을 모두 탐색하여 두가지의 체스판 케이스와 비교하여 수정되어야할 영역의 수를 카운팅 하였다. ( changeCnt1, changeCnt2 )

이후 한영역에 대해서 2가지 케이스로 수정할 경우 카운팅이 가장 적은 것을 선택하고, 모든영역에 대해서 가장 적은 것을 도출해낸다. ( Math.min함수는 반드시 2가지 요소만 비교가 가능하기에 순서대로 중첩하여 사용한다. )

 

막혔던 점 : 초반에 case를 선언하지 않고 영역에서 이전 영역과 이후영역이 값이 다른 부분들을 수정영역으로 카운팅했다. 이러한 경우 한번 어긋나는 영역을 3번씩 카운팅하는등 적절한 수정카운팅이 이루어지지 않는다. 또한 두가지 케이스로 수정하는 경우 각각의 수정횟수를 비교하지 못한다. 기준점을 두고 그것과 완전탐색하여 수정영역을 카운팅하는 것이 바람직한 풀이법이었다.

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int m = sc.nextInt();
    char[][] board = new char[n][m];

    for (int i = 0; i < n; i++) {
      String row = sc.next();
      for (int j = 0; j < m; j++) {
        board[i][j] = row.charAt(j);
      }
    }

    char[][] case1 = {
      {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
      {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
      {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
      {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
      {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
      {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
      {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
      {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'}
    };  

    char[][] case2 = {
      {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
      {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
      {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
      {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
      {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
      {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'},
      {'B', 'W', 'B', 'W', 'B', 'W', 'B', 'W'},
      {'W', 'B', 'W', 'B', 'W', 'B', 'W', 'B'}
    };

      
    int minChangeCnt = Integer.MAX_VALUE; 
    
    for(int i=0; i<=n-8; i++){
      for(int j=0; j<=m-8; j++){
        int changeCnt1 = 0; //  case1일때 바꿔야될 갯수
        int changeCnt2 = 0; // case2일때 바꿔야될 갯수
        
        for(int k=0; k<8; k++){ 
          for(int l=0; l<8; l++){
            if(board[i+k][j+l] != case1[k][l]) changeCnt1++;
            if(board[i+k][j+l] != case2[k][l]) changeCnt2++;
          }
        }
        //minChangeCnt = Math.min(minChangeCnt, changeCnt1, changeCnt2);
        minChangeCnt = Math.min(minChangeCnt, Math.min(changeCnt1, changeCnt2));

      }
    }

    System.out.println(minChangeCnt);

  }
}

 

[ 백준 1436 ] 영화감독 숌

https://www.acmicpc.net/problem/1436

 

종말의 수 순번을 나타내는 cnt를 1로, 그 값을 num 666으로 초기화하고

이를 1씩 증가시키면서 종말의 수 조건을 만족한다면 순번 cnt값을 증가시켰다.

이때 n번째를 구하는 것이기에 순번 cnt가 n보다 작은 경우에만 이를 반복하고 동일해지는 순간에는 num값을 출력하였다.

 

막혔던 점 : 초반에 while을 true로 무한루프를 설정하고 cnt == n이 되는 순간 break하여 num을 출력하도록 하였다.( num증가 -> cnt증가 -> break ) 하지만 반복문에서 num을 먼저 증가시켜서 n+1번째의 종말의 수를 출력하게 되었다.

num증가 -> break -> cnt 증가 순으로 반복로직을 고치거나 cnt의 초기값을 0부터 시작해야 n번째를 구할 수 있었다.

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int cnt = 1;
    int num = 666;

    while(cnt<n){
      num++;
      if(String.valueOf(num).contains("666")) cnt++;
    }

    System.out.println(num);
  }
}

 

[ 백준 2839 ] 설탕 배달

https://www.acmicpc.net/problem/2839

 

연립방정식과 비슷한 형태로 구할 수 있었다. i를 3kg짜리 갯수의 미지수로, j를 5kg짜리 갯수의 미지수로 두고 조건을 만족하는 것중에서 최소값을 만족하는 것을 구하는 것이다.

i와 j의 직접적인 최소최대범위는 주어지지 않았지만  목표 킬로그램인 n의 범위가 주어져서 그 최대최소 정수값을 구할 수 있었다. 

연립방정식을 만족하는 해가 없어서( n의 값을 만족하는 i와 j의 조합이 없음) 처음 minCnt값이 갱신되지 않았다면 답이 없는 것이므로 0을 출력한다.

 

import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int n = sc.nextInt();
    int minCnt = Integer.MAX_VALUE; //최소총합

    // 3 ≤ N ≤ 5000 -> 3kg 최소0~최대1666개, 5kg 최소0~최대1000

    for(int i=0; i<=1666; i++){  //3kg짜리 개수
      for(int j=0; j<=1000; j++){  //5kg짜리 개수
        if(3*i+5*j == n){
          minCnt = Math.min(i+j, minCnt);
        }
      }
    }

    if (minCnt == Integer.MAX_VALUE) System.out.println(-1); //조건만족X
    else  System.out.println(minCnt);


  }
}