[알고리즘&코딩테스트] 완전 탐색(Brute Force)

완전 탐색(Brute Force)

 

· 문제를 해결하기 위해 확인하는 모든 경우를 탐색하는 방법이다

  - 정답은 무조건 구하는 치트키

· 백 트래킹을 사용해야 하는 상황을 해결한다.

· 모든 코딩테스트 문제에게 기본적으로 접근해 봐야 한다.

 

· 장점: 부분점수를 얻기 좋다.

· 단점: 전부 탐색하기 때문에 일반적으로 시간 복잡도가  높다.

 

코딩테스트에 나오는 완전 탐색 문제 종류

· 4가지: (중복없이 or 중복을 허용해서) N개 중 M개를  (고르기 or 순서 있게 나열하기)

· 완전 탐색은 함수 정의가 50%

 

   // Recurrence Function (재귀 함수)
   // 만약 M 개를 전부 고름   => 조건에 맞는 탐색을 한 가지 성공한 것!
   // 아직 M 개를 고르지 않음 => k 번째부터 M번째 원소를 조건에 맞게 고르는 모든 방법을 시도한다.
   static void rec_func(int k) {}

   public static void main(String[] args) {
      input();

      // 1 번째 원소부터 M 번째 원소를 조건에 맞는 모든 방법을 찾아줘
      rec_func(1);
      System.out.println(sb.toString());

   }

 

N개 중 중복을 허용하여, M개를 순서 있게 나열하기

문제 BOJ 15651: https://www.acmicpc.net/problem/15651

시간: O(N^M) => 7^7 = 82만 (1억 미만)

공간: O(M)

 

아래 코드에서 FastReader는 입력을 빨리 받기 위해 정의한 클래스다. 

public class N15651_N과M {
   private static StringBuilder sb = new StringBuilder();
   private static int N;
   private static int M;
   private static int[] selected;

   private static void input( ) {
	 Scanner scan = new Scanner(System.in);
      N = scan.nextInt();
      M = scan.nextInt();
      selected = new int[M + 1];
   }
   private static void rec_func(int k) {
      if (k == M + 1) { // 모두 고름
         // selected[1...M] 배열이 새롭게 탑색된 결과
         for (int i = 1; i <= M; i++) sb.append(selected[i]).append(' ');
         sb.append('\n');
      } else {
         // 1 ~ N 까지를 k 번 원소로 한 번씩 정하고,
         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());
   }
}

 

N개 중 중복 없이, M개를 순서 있게 나열하기

문제 BOJ 15649: https://www.acmicpc.net/problem/15649

 

 

public class N15649 {
   private static StringBuilder sb = new StringBuilder();
   private static int N;
   private static int M;
   private static int[] selected, used;

   private static void input() {
      Scanner scan = new Scanner(System.in);
      N = scan.nextInt();
      M = scan.nextInt();
      selected = new int[M + 1];
      used = new int[N + 1];
   }

   private static void rec_func(int k) {
      if (k == M + 1) { // 모두 고름
         // selected[1...M] 배열이 새롭게 탑색된 결과
         for (int i = 1; i <= M; i++) {
            sb.append(selected[i]).append(' ');
         }
         sb.append('\n');
      } else {
         // 1 ~ N 까지를 k 번 원소로 한 번씩 정하고,
         for (int cand = 1; cand <= N; cand++) {
            // cand가 이미 사용되었는지 확인
            if (used[cand] == 1) {
               continue;
            }

            selected[k] = cand;
            used[cand] = 1; // 사용 처리

            // 매번 k+1 번부터 M번 원소로 재귀 호출
            rec_func(k + 1);

            // 사용 후 반납
            selected[k] = 0;
            used[cand] = 0;
         }
      }
   }
}

 

N개 중 중복을 허용하고, M개를 고르기

문제 BOJ 15652: https://www.acmicpc.net/problem/15652

시간: O(N^M) => 8^8 => 1667만 보단 작다

예) N=4, M=3인 경우 4x4x4 = 4^3보단 작다

공간: O(M)

public class N15652_N과M4 {
   private static StringBuilder sb = new StringBuilder();
   private static int N;
   private static int M;
   private static int[] selected;

   private static void input() {
      Scanner scan = new Scanner(System.in);
      N = scan.nextInt();
      M = scan.nextInt();
      selected = new int[M + 1];
   }

   private static void rec_func(int k) {
      if (k == M + 1) { // 모두 고름
         // selected[1...M] 배열이 새롭게 탑색된 결과
         for (int i = 1; i <= M; i++) {
            sb.append(selected[i]).append(' ');
         }
         sb.append('\n');
      } else {
         int start = selected[k-1];
         if (start == 0) start = 1;
         for (int cand = start; 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());
   }
}

 

N개 중 중복 없이, M개를 고르기

문제 BOJ 15650: https://www.acmicpc.net/problem/15650

- C: Combination

 

응용

예시 문제1

· BOJ 14888: 연산자 끼워 넣기: https://www.acmicpc.net/problem/14888

· 문제 파악 - 정답의 최대치: -21억 ~ 21억의 범위를 갖는 int 형 변수를 사용 가능

· '중복을 허용하지 않으며, 순서 있게 나열하기' 문제

public class N14888_연산자끼워넣기 {
   static int N, max, min;
   static int[] nums, operators, order;

   private static void input() {
      Scanner sc = new Scanner(System.in);
      N = sc.nextInt();
      nums = new int[N + 1];
      operators = new int[5];
      order = new int[N + 1];
      for (int i = 1; i <= N; i++) nums[i] = sc.nextInt();
      for (int i = 1; i <= 4; i++) operators[i] = sc.nextInt();

      max = Integer.MIN_VALUE;
      min = Integer.MAX_VALUE;
   }

   // 완성된 식에 맞게 계산을 해서 정답에 개신하는 작업
   static int calculator() {
      int value = nums[1];
      for (int i = 1; i < N; i++) {
         switch (order[i]) {
            case 1:
               value = value + nums[i+1];
               break;
            case 2:
               value = value - nums[i+1];
               break;
            case 3:
               value = value * nums[i+1];
               break;
            case 4:
               value = value / nums[i+1];
               break;
         }
      }
      return value;
   }

   // order[1...N-1]에 연산자들이 순서대로 저장
   private static void recurFun(int k) {
      if (k == N) { // 모든 연산자들을 전부 나열하는 방법을 찾은 상태
         // 정한 연산자 순서대로 계산해서 정답을 갱신하기
         int value = calculator();
         max = Math.max(max, value);
         min = Math.min(min, value);
      } else { // k 번째 연산자는 무엇을 선택할 것인가?
         // 4 가지의 연산자들 중에 뭘 쓸 것인지 선택하고 재귀 호출
         for (int cand = 1; cand <= 4; cand++) {
            if (operators[cand] >= 1) {
               operators[cand]--;
               order[k] = cand;
               recurFun(k+1);
               operators[cand]++;
               order[k] = 0;
            }
         }
      }
   }

   public static void main(String[] args) {
      input();
      recurFun(1);
      StringBuilder sb = new StringBuilder();
      sb.append(max).append('\n').append(min);
      System.out.println(sb);
   }
}

 

문제점: 탐색이 완료될 때마다 calculator() 함수 내에서 반복(for)이 발생한다.

개선: recurFun() 함수에서 4 가지 연산자들 중에 뭘 쓸 것인지 선택하고, 연산자를 계산 한 후에 재귀를 호출한다.

 

예시 문제2

· BOJ 9663 - N Queen : https://www.acmicpc.net/problem/9663

· 퀸은 위아래, 좌우, 대각선 방향을 공격할 수 있다.

· 'N개 중에서 중복을 허용해서 , N개 순서대로 나열하기' 문제

 

· 시도1: 재귀 함수를 사용하여 모든 위치에 퀸을 놓아본다.

· 문제점: 시간 복잡도 O(N^M) -> 14^14 > 10 ^ 16 == 1억 이상의 연산 시간이 걸려 시간 초과 한다.

· 시도2(문제해결) : 모든 경우를 전부 고려하지 않고 매 시도마다 퀸의 위치가 올바른지 체크하고, 올바르지 않으면, 재귀를 중지한다.

 

public class N9663_NQueen {

   static int N, ans;
   static int[] col; // col[i]: i번 행의 퀸은 col[i]번 열에 놓았다는 기록

   private static boolean attackable(int r1, int c1, int r2, int c2) {
      boolean result = false;
      if (c1 == c2) result = true; // 같은 열에서 공격 가능
      else if (r1 - c1 == r2 - c2) result = true; // 왼쪽 위 대각선으로 공격 가능
      else if (r1 + c1 == r2 + c2) result = true; // 오른쪽 위 대각선으로 공격 가능
      return result;
   }

   private static void recFunc(int row) {
      if (row == N + 1) {    // 각 행마다 퀸을 하나씩 놓음
         ans++;
      } else {
         for (int c = 1; c <= N; c++) {
            boolean possible = true;
            for (int i = 1; i <= row-1; i++){
               if(attackable(row, c, i, col[i])) {
                  possible = false;
                  break;
               }
            }

            if (possible) {
               col[row] = c;
               recFunc(row + 1);
               col[row] = 0;
            }
         }
      }
   }

   private static void input() {
      Scanner sc = new Scanner(System.in);
      N = sc.nextInt();
      col = new int[N + 1];
   }

   public static void main(String[] args) {
      input();
      recFunc(1);
      System.out.println(ans);
   }
}

 

예시 문제3

· BOJ 1182 - 부분 수열의 합 : https://www.acmicpc.net/problem/1182

· 부분 수열 개수의 상한: 2^20 <= 1,048,576 / 부분 수열의 합 상한 20 * 1,000,000 => 모두 int 형 변수 가능 

· '중복을 허용하고, 순서 있게 나열하기' 문제

· 시간 복잡도: O(N^M)

 

· 추가 학습 방법: 백준 - 알고리즘 분류 - 백트래킹 문제 학습 (맞은 사람이 많은 쉬운 문제 부터)

· 백 트래킹의 핵심: 재귀 함수의 정의

 

출처

fastcampus