브루트포스 (완전 탐색) 알고리즘

예시 코드는 토글을 클릭하면 확인할 수 있습니다.

브루트포스 (완전 탐색)이란

브루트포스 (완전 탐색) 말 그대로 가능한 모든 경우를 다 시도해보는 방식입니다. 마치 자물쇠의 모든 번호를 하나씩 돌려보는 것처럼 가장 직관적이고 확실한 방법입니다.

다만 이를 PS에서 사용하기 위해서는 시간복잡도를 고려해야 합니다. 시간복잡도를 계산해봤을 때 주어진 시간에 마치지 못 할 것 같으면 최적화를 하거나 다른 방법을 찾아야 합니다. 이때 보통 1초당 1억번의 연산을 실행한다고 이해하면 될 것 같습니다.

예제 1. 블랙잭(백준 2798번)

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

문제를 정리해보면 N장의 카드 중 3장을 고릅니다. 이 3장의 카드의 합이 M을 넘지 않으면서 최대가 되도록 만드는 문제입니다.

문제의 조건을 잘 보면 N의 범위가 최대 100입니다. 그러면 브루트포스로 3장의 경우를 모두 구해도 100^3 = 1,000,000 으로 1초 안에 연산이 가능합니다.

JAVA 정답 코드

import java.util.*;
import java.io.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        int[] cards = new int[N];
        for (int i = 0; i < N; i++) {
            cards[i] = Integer.parseInt(st.nextToken());
        }
        int ans = -1;
        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 = cards[i] + cards[j] + cards[k];
                    if (sum <= M) {
                        ans = Math.max(ans, sum);
                    }
                }
            }
        }
        bw.write(String.valueOf(ans));

        bw.flush();

        bw.close();
        br.close();
    }
}

 

예제 2. 백설 공주와 일곱 난쟁이(백준 3040번)

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

문제를 정리해보면 9개의 수 중 더해서 100이 되는 7개의 수를 찾는 문제입니다. 이 문제도 숫자의 갯수가 9개밖에 되지 않으니 7중 for문을 이용해서 7개 수의 합을 전부 구해도 시간초과가 발생하진 않습니다.

7중 for문 JAVA 코드

import java.util.*;
import java.io.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int[] nums = new int[9];
        for (int i = 0; i < 9; i++) {
            nums[i] = Integer.parseInt(br.readLine());
        }
        boolean e = false;
        for (int i = 0; i < 9; i++) {
            for (int j = i + 1; j < 9; j++) {
                for (int k = j + 1; k < 9; k++) {
                    for (int l = k + 1; l < 9; l++) {
                        for (int m = l + 1; m < 9; m++) {
                            for (int n = m + 1; n < 9; n++) {
                                for (int p = n + 1; p < 9; p++) {
                                    if (nums[i] + nums[j] + nums[k] + nums[l] + nums[m] + nums[n] + nums[p] == 100) {
                                        bw.write(nums[i] + "\n" + nums[j] + "\n" + nums[k] + "\n" + nums[l] + "\n" + nums[m] + "\n" + nums[n] + "\n" + nums[p] + "\n");
                                        e = true;
                                        break;
                                    }
                                }
                                if (e) break;
                            }
                            if (e) break;
                        }
                        if (e) break;
                    }
                    if (e) break;
                }
                if (e) break;
            }
            if (e) break;
        }

        bw.flush();

        bw.close();
        br.close();
    }
}

 

하지만 위의 코드를 보면 너무 코드가 복잡하기도 하고 숫자의 갯수가 많아지면 시간 초과가 발생합니다.

그래서 최적화가 필요합니다. 9개 중에 합해서 100이 되는 수 7개를 찾는단 말은 다시 생각하면 9개 중 2개를 제외하란 말과 같습니다. 따라서 9개 숫자의 총합에 100을 뺀 값을 tmp라고 가정하면, 9개의 숫자 중 더해서 tmp가 되는 2개의 수를 고르는 것과 같습니다. 

JAVA 정답 코드

import java.util.*;
import java.io.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        int[] nums = new int[9];
        int sum = 0;
        for (int i = 0; i < 9; i++) {
            nums[i] = Integer.parseInt(br.readLine());
            sum += nums[i];
        }
        int tmp = sum - 100;
        int x1 = 0, x2 = 0;
        for (int i = 0; i < 9; i++) {
            for (int j = i + 1; j < 9; j++) {
                if (nums[i] + nums[j] == tmp) {
                    x1 = i;
                    x2 = j;
                }
            }
        }
        for (int i = 0; i < 9; i++) {
            if (i == x1 || i == x2) continue;
            bw.write(nums[i] + "\n");
        }

        bw.flush();

        bw.close();
        br.close();
    }
}