브루트 포스

문제에 주어진 방법의 모든 경우의 수를 적용하는 것이다. 예를 들어 비밀번호가 4자리이고, 숫자로만 이루어져 있다고 한다면 0000 ~ 9999까지 총 10000가지의 경우의 수를 모두 적용하는 것이다. 즉, 모든 방법을 1번 씩 시도한다.

• 문제의 가능한 경우의 수를 하나도 빠짐 없이 계산한다.
• 가능한 모든 방법을 다 만들어본다. 반복문, 순열, 재귀, 비트 마스크 등이 있다.
• 각각의 방법을 적용해 답을 구한다. 시간 복잡도는 O(경우의 수 x 1회 시도의 복잡도)이다.

경우의 수

1. N명의 사람이 한 줄로 서는 경우의 수, N! = N x (N - 1) x (N - 2) ... x 1 = O(N!)
2. N명의 사람 중에서 대표 두 명을 뽑는 경우의 수, nC2 = N(N - 1) / 2! = O(N$^{2}$)
3. N명의 사람 중에서 대표 세 명을 뽑는 경우의 수, nC3 = N(N - 1)(N - 2) / 3! = O(N$^{3}$)
4. N명의 사람 중에서 반장 1명과 부반장 1명을 뽑는 경우의 수, N(N - 1) = O(N$^{2}$)
5. N명의 사람이 있을 때, 각 사람이 영화를 볼지 말지 결정하는 가능한 조합의 수(한 사람이 결정할 수 있는 경우의 수는 본다, 안 본다 총 2가지), 2$^{N}$ = 2 x 2 x .... 2(N번) = O(2$^{N}$)
6. N명의 사람이 있을 때, 각 사람이 세 개의 영화를 골라 보는 가능한 조합의 수(한 사람이 결정할 수 있는 경우의 수는 A, B, C 총 3가지), 3$^{N}$ = 3 x 3 x .... 3(N번) = O(3$^{N}$)

예제

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

9개의 수 중 합이 100을 만드는 7개의 수를 구한다. 정답이 여러개인 경우는 아무거나 상관없다.

package com.example.demo;

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

public class DemoApplication {

    public static void main(String[] args) throws IOException {
        try (
                BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out))
        ) {
            int n = 9;
            int[] heights = new int[n];
            int sum = 0;

            for (int i = 0; i < n; i++) {
                heights[i] = Integer.parseInt(reader.readLine());
                sum += heights[i];
            }

            Arrays.sort(heights);

            for (int i = 0; i < n - 1; i++) {
                for (int j = i + 1; j < n; j++) {
                    if (sum - heights[i] - heights[j] == 100) {
                        for (int k = 0; k < n; k++) {
                            if (i == k || j == k) {
                                continue;
                            }
                            writer.write(heights[k] + "\n");
                        }
                        return;
                    }
                }
            }

        }
    }

}

이 문제는 9개의 수에서 7가지를 구하는 방법과 2가지를 구하는 방법이 있다. 7가지 경우의 수에서 100합을 만드는 것보다 2가지 경우의 수에서 전체합에서 뺄셈하여 100을 만드는 경우의 수가 더 적으므로(9C2 = 38 < 9C7 = 144)이므로 2가지 경우의 수를 구하는 방법을 선택해야한다. 시간 복잡도는 nC2 = O(N$^{2}$)이다.

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

import java.io.*;

public class Main {

    public static void main(String[] args) throws IOException {
        try (
                BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out))
        ) {
            int n = Integer.parseInt(reader.readLine());
            int answer = 0;
            char[][] arr = new char[n][n];

            for (int i = 0; i < n; i++) {
                String line = reader.readLine();
                for (int j = 0; j < n; j++) {
                    arr[i][j] = line.charAt(j);
                }
            }

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (i < n - 1) {
                        swap(arr, i, j, i + 1, j);
                        int temp = check(arr, i, i + 1, j, j);
                        swap(arr, i, j, i + 1, j);
                        if (answer < temp) {
                            answer = temp;
                        }
                    }
                    if (j < n - 1) {
                        swap(arr, i, j + 1, i, j);
                        int temp = check(arr, i, i, j, j + 1);
                        swap(arr, i, j + 1, i, j);
                        if (answer < temp) {
                            answer = temp;
                        }
                    }
                }
            }

            writer.write(answer + "");
        }
    }

    public static void swap(char[][] arr, int aLeft, int aRight, int bLeft, int bRight) {
        char temp = arr[aLeft][aRight];
        arr[aLeft][aRight] = arr[bLeft][bRight];
        arr[bLeft][bRight] = temp;
    }

    public static int check(char[][] arr, int startLow, int endLow, int startCols, int endCols) {
        int n = arr.length;
        int answer = 1;

        for (int i = startLow; i <= endLow; i++) {
            int cnt = 1;
            for (int j = 1; j < n; j++) {
                if (arr[i][j] == arr[i][j - 1]) {
                    cnt++;
                } else {
                    cnt = 1;
                }
                if (answer < cnt) {
                    answer = cnt;
                }
            }
        }

        for (int i = startCols; i <= endCols; i++) {
            int cnt = 1;
            for (int j = 1; j < n; j++) {
                if (arr[j][i] == arr[j - 1][i]) {
                    cnt++;
                } else {
                    cnt = 1;
                }
                if (answer < cnt) {
                    answer = cnt;
                }
            }
        }

        return answer;
    }

}

이 문제는 N x N개의 보드의 칸을 모두 검사해야한다. 각 칸마다 인접한 두 칸의 교환은 최대 상하좌우로 총 4번이고 칸의 위치에 따라 상하좌우가 없을 수 있다. 인접한 두 칸의 검사는 각 칸에서 우측 칸과 아래 칸을 교환하는 경우만 검사하면 모든 칸을 교환하는 전체 경우의 수를 검사할 수 있다. 인접한 두 칸을 교환했을 때, 매 번 모든 행과 열을 검사하는 것이 아닌 영향을 받는 행과 열만을 검사한다. 시간 복잡도는 N$^{2}$(경우의 수) x N(1회 시도의 복잡도) = O(N$^{3}$)이다.

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

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

public class Main {

    public static void main(String[] args) throws IOException {
        try (
                BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out))
        ) {
            int[] check = Arrays.stream(reader.readLine().split(" "))
                    .mapToInt(n -> Integer.parseInt(n) - 1)
                    .toArray();
            int[] esm = new int[3];

            for (int year = 0; ; year++) {
                esm[0] = year % 15;
                esm[1] = year % 28;
                esm[2] = year % 19;
                if (Arrays.compare(esm, check) == 0) {
                    writer.write(year + 1 + "");
                    return;
                }
            }
        }
    }

}

ESM으로 표현 가능한 경우의 수는 15 x 28 x 19 = 7980가지이다. ESM년도를 1씩 증가시키면서 입력과 동일한지 검사한다. 년도를 0부터 14로 표현하면 나머지 연산을 활용해서 연산을 쉽게 할 수 있다.

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

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

public class Main {

    public static void main(String[] args) throws IOException {
        try (
                BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out))
        ) {
            int t = Integer.parseInt(reader.readLine());

            for (int i = 0; i < t; i++) {
                StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
                int m = Integer.parseInt(tokenizer.nextToken());
                int n = Integer.parseInt(tokenizer.nextToken());
                int x = Integer.parseInt(tokenizer.nextToken()) - 1;
                int y = Integer.parseInt(tokenizer.nextToken()) - 1;
                boolean find = false;

                for (int j = x; j < m * n; j += m) {
                    if (j % n == y) {
                        writer.write(j + 1 + "\n");
                        find = true;
                        break;
                    }
                }

                if (!find) {
                    writer.write(-1 + "\n");
                }
            }
        }
    }

}

위의 ESM(년도) 문제와 동일한 방법으로 해결할 수 있지만 이 문제는 시간 제한이 1초인데 N이 최대 40000이기 때문에 시간 복잡도 O(N$^{2}$)으로 해결할 수 없다. 전체 년도를 검사하지 않고 x, y 중 x가 나오는 년도 중에서만 y가 나오는 년도가 있는지 검사한다. 시간 복잡도 O(N)이다.

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

import java.io.*;

public class Main {

    public static boolean[] broken = new boolean[10];

    public static void main(String[] args) throws IOException {
        try (
                BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out))
        ) {
            String line = reader.readLine();
            int n = Integer.parseInt(line);
            int m = Integer.parseInt(reader.readLine());

            if (m != 0) {
                for (String s : reader.readLine().split(" ")) {
                    broken[Integer.parseInt(s)] = true;
                }
            }

            int answer = getDiff(n, 100);

            if (n == 100) {
                writer.write(0 + "");
            } else if (line.length() >= answer) {
                writer.write(answer + "");
            } else {
                for (int i = 0; i < 999900; i++) {
                    int length = possible(i);
                    if (length > 0) {
                        int count = getDiff(i, n);
                        if (answer > length + count) {
                            answer = length + count;
                        }
                    }
                }
                writer.write(answer + "");
            }

        }
    }

    public static int possible(int c) {
        int length = 0;
        if (c == 0) {
            if (broken[0]) {
                return 0;
            } else {
                return 1;
            }
        }
        while (c > 0) {
            if (broken[c % 10]) {
                return 0;
            }
            length++;
            c /= 10;
        }
        return length;
    }

    public static int getDiff(int n, int m) {
        int diff = n - m;
        return diff < 0 ? -diff : diff;
    }

}

채널을 최소한의 버튼 사용으로 이동하는 방법은 숫자 버튼으로 채널을 이동한 후, +/- 버튼으로 이동하는 방법과 +/- 버튼으로만 이동하는 방법이 있다. 현재 채널의 위치인 100과 N의 차이가 N의 길이보다 짧거나 같은 경우가 +/- 버튼만으로 이동하는 것이 최소인 경우이다. 100부터 N의 최대인 500000까지 + 버튼으로 이동한다고 할 때, 버튼의 최대 사용 횟수는 499900이다. 반대로 - 버튼으로 이동하는 경우도 있으므로 버튼의 최대 사용 횟수인 499900보다 덜 사용할 수 있는 경우는 999894 미만(채널 이동 자리수 6 + 499894)의 채널로 이동 후, - 버튼으로 이동하는 경우다. 가능한 경우의 수 범위를 설정하고 사용 가능한 버튼으로 구성할 수 있는 번호인지 검사하여 최소 버튼 사용 횟수를 구할 수 있다.

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

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

public class Main {

    public static void main(String[] args) throws IOException {
        try (
                BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out))
        ) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            int answer = 0;
            int n = Integer.parseInt(tokenizer.nextToken());
            int m = Integer.parseInt(tokenizer.nextToken());
            int[][] arr = new int[n][m];

            for (int i = 0; i < n; i++) {
                tokenizer = new StringTokenizer(reader.readLine());
                for (int j = 0; j < m; j++) {
                    arr[i][j] = Integer.parseInt(tokenizer.nextToken());
                }
            }

            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    // ㅡ자 검사(회전 가능)
                    if (j < m - 3) {
                        int sum = 0;
                        sum += arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i][j + 3];
                        if (answer < sum) {
                            answer = sum;
                        }
                    }
                    // ㅡ자 검사(회전 가능)
                    if (i < n - 3) {
                        int sum = 0;
                        sum += arr[i][j] + arr[i + 1][j] + arr[i + 2][j] + arr[i + 3][j];
                        if (answer < sum) {
                            answer = sum;
                        }
                    }
                    // ㅁ자 검사
                    if (i < n - 1 && j < m - 1) {
                        int sum = 0;
                        sum += arr[i][j] + arr[i][j + 1] + arr[i + 1][j] + arr[i + 1][j + 1];
                        if (answer < sum) {
                            answer = sum;
                        }
                    }

                    // ㄴ, ㄹ, ㅗ(회전 및 대칭 가능)
                    if (i < n - 2 && j < m - 1) {
                        // ㄴ자 검사
                        int sum = 0;
                        sum += arr[i][j] + arr[i + 1][j] + arr[i + 2][j] + arr[i + 2][j + 1];
                        if (answer < sum) {
                            answer = sum;
                        }
                        sum = 0;
                        sum += arr[i][j + 1] + arr[i + 1][j + 1] + arr[i + 2][j] + arr[i + 2][j + 1];
                        if (answer < sum) {
                            answer = sum;
                        }
                        sum = 0;
                        sum += arr[i][j] + arr[i][j + 1] + arr[i + 1][j + 1] + arr[i + 2][j + 1];
                        if (answer < sum) {
                            answer = sum;
                        }
                        sum = 0;
                        sum += arr[i][j] + arr[i][j + 1] + arr[i + 1][j] + arr[i + 2][j];
                        if (answer < sum) {
                            answer = sum;
                        }

                        // ㄹ자 검사
                        sum = 0;
                        sum += arr[i][j] + arr[i + 1][j] + arr[i + 1][j + 1] + arr[i + 2][j + 1];
                        if (answer < sum) {
                            answer = sum;
                        }
                        sum = 0;
                        sum += arr[i][j + 1] + arr[i + 1][j + 1] + arr[i + 1][j] + arr[i + 2][j];
                        if (answer < sum) {
                            answer = sum;
                        }

                        // ㅗ자 검사
                        sum = 0;
                        sum += arr[i][j + 1] + arr[i + 1][j] + arr[i + 1][j + 1] + arr[i + 2][j + 1];
                        if (answer < sum) {
                            answer = sum;
                        }
                        sum = 0;
                        sum += arr[i][j] + arr[i + 1][j] + arr[i + 1][j + 1] + arr[i + 2][j];
                        if (answer < sum) {
                            answer = sum;
                        }
                    }

                    if (i < n - 1 && j < m - 2) {
                        // ㄴ자 검사
                        int sum = 0;
                        sum += arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i + 1][j + 2];
                        if (answer < sum) {
                            answer = sum;
                        }
                        sum = 0;
                        sum += arr[i + 1][j] + arr[i + 1][j + 1] + arr[i + 1][j + 2] + arr[i][j + 2];
                        if (answer < sum) {
                            answer = sum;
                        }
                        sum = 0;
                        sum += arr[i][j] + arr[i + 1][j] + arr[i][j + 1] + arr[i][j + 2];
                        if (answer < sum) {
                            answer = sum;
                        }
                        sum = 0;
                        sum += arr[i][j] + arr[i + 1][j] + arr[i + 1][j + 1] + arr[i + 1][j + 2];
                        if (answer < sum) {
                            answer = sum;
                        }

                        // ㄹ자 검사
                        sum = 0;
                        sum += arr[i][j] + arr[i][j + 1] + arr[i + 1][j + 1] + arr[i + 1][j + 2];
                        if (answer < sum) {
                            answer = sum;
                        }
                        sum = 0;
                        sum += arr[i + 1][j] + arr[i + 1][j + 1] + arr[i][j + 1] + arr[i][j + 2];
                        if (answer < sum) {
                            answer = sum;
                        }

                        // ㅗ자 검사
                        sum = 0;
                        sum += arr[i + 1][j] + arr[i + 1][j + 1] + arr[i][j + 1] + arr[i + 1][j + 2];
                        if (answer < sum) {
                            answer = sum;
                        }
                        sum = 0;
                        sum += arr[i][j] + arr[i][j + 1] + arr[i][j + 2] + arr[i + 1][j + 1];
                        if (answer < sum) {
                            answer = sum;
                        }
                    }
                }
            }

            writer.write(answer + "");
        }
    }

}

ㅡ자 2가지, ㅁ자 1가지, ㄴ자 8가지, ㄹ자 4가지, ㅗ자 4가지 총 모든 도형의 회전 및 대칭이 가능한 경우의 수는 19가지이다. 각 보드에 기준점으로 가능한 경우의수는 NM개이다. 시간 복잡도는 O(NM)이다.

N과 M

N개에서 M개, N x M개에서 K개 유형이 있고 경우에 따라 순서와 선택 2가지 방식으로 문제를 해결할 수 있다.

예제

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    
    public static boolean[] check;

    public static int[] arr;

    public static void main(String[] args) throws IOException {
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            int n = Integer.parseInt(tokenizer.nextToken());
            int m = Integer.parseInt(tokenizer.nextToken());
            check = new boolean[n];
            arr = new int[m];
            go(n, m, 0);
        }
    }

    public static void go(int n, int m, int depth) {
        if (depth == m) {
            for (int j = 0; j < arr.length; j++) {
                System.out.print(arr[j] + (j + 1 != arr.length ? " " : "\n"));
            }
        } else {
            for (int i = 1; i <= n; i++) {
                if (check[i - 1]) {
                    continue;
                }
                check[i - 1] = true;
                arr[depth] = i;
                go(n, m, depth + 1);
                check[i - 1] = false;
            }
        }
    }

}

중복 없이 수를 골라 수열을 구성하는 경우의 수는 N, M이 같은 경우가 최대이므로 N x (N - 1) x (N - 2) ... x 1 형태가 될 수 있다. 시간 복잡도는 O(N!)이다.

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

순서 방식

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static int[] arr;

    public static void main(String[] args) throws IOException {
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            int n = Integer.parseInt(tokenizer.nextToken());
            int m = Integer.parseInt(tokenizer.nextToken());
            arr = new int[m];
            go(n, m, 0);
        }
    }

    public static void go(int n, int m, int depth) {
        if (depth == m) {
            for (int j = 0; j < arr.length; j++) {
                System.out.print(arr[j] + (j + 1 != arr.length ? " " : "\n"));
            }
        } else {
            int start = depth > 0 ? arr[depth - 1] + 1 : 1;
            for (int i = start; i <= n; i++) {
                arr[depth] = i;
                go(n, m, depth + 1);
            }
        }
    }

}

위 문제와 동일하게 중복 없이 수를 골라 수열을 구성하지만 오름차순이기 때문에 현재 항이 이전 항의 숫자보다 큰 수부터 검사한다. 이전 항 보다 큰 숫자만 순회하기 때문에 중복 검사는 불필요하다.

선택 방식

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    public static int[] arr;

    public static void main(String[] args) throws IOException {
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            int n = Integer.parseInt(tokenizer.nextToken());
            int m = Integer.parseInt(tokenizer.nextToken());
            arr = new int[m];
            go(n, m, 1, 0);
        }
    }

    public static void go(int n, int m, int index, int selected) {
        if (selected == m) {
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + (i + 1 != arr.length ? " " : "\n"));
            }
        } else {
            if (index > n) {
                return;
            }
            arr[selected] = index;
            go(n, m, index + 1, selected + 1);
            arr[selected] = 0;
            go(n, m, index + 1, selected);
        }

    }

}

수열을 모든 경우로 구성하는 것이 아닌 반드시 오름차순으로 구성되어야 하기 때문에 수를 선택하거나 선택하지 않는 경우로 문제를 해결할 수 있다. 선택하지 않는 경우가 있기 때문에 수가 m개 만큼 선택되지 않는 경우도 있다. 시간 복잡도는 O(2$^{N}$)이다.

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

순서 방식

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

public class Main {

    public static int[] arr;

    public static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            int n = Integer.parseInt(tokenizer.nextToken());
            int m = Integer.parseInt(tokenizer.nextToken());
            arr = new int[m];
            go(n, m, 0);
            writer.flush();
            writer.close();
        }
    }

    public static void go(int n, int m, int depth) throws IOException {
        if (depth == m) {
            for (int i = 0; i < arr.length; i++) {
                writer.write(arr[i] + "");
                if (i + 1 != arr.length) {
                    writer.write(" ");
                } else {
                    writer.newLine();
                }
            }
        } else {
            int start = depth > 0 ? arr[depth - 1] : 1;
            for (int i = start; i <= n; i++) {
                arr[depth] = i;
                go(n, m, depth + 1);
            }
        }

    }

}

중복이 가능한 수열이지만 수열의 현재 항이 이전 항보다 크거나 같아야 비내림차순의 조건을 만족할 수 있다.

선택 방식

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

public class Main {

    public static int[] cnt;

    public static BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));

    public static void main(String[] args) throws IOException {
        try (BufferedReader reader = new BufferedReader(new InputStreamReader(System.in))) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            int n = Integer.parseInt(tokenizer.nextToken());
            int m = Integer.parseInt(tokenizer.nextToken());
            cnt = new int[n + 1];
            go(n, m, 1, 0);
            writer.flush();
            writer.close();
        }
    }

    public static void go(int n, int m, int index, int selected) throws IOException {
        if (selected == m) {
            for (int i = 0; i < cnt.length; i++) {
                for (int j = 0; j < cnt[i]; j++) {
                    writer.write(i + "");
                    if (j + 1 != cnt[i]) {
                        writer.write(" ");
                    } else {
                        writer.newLine();
                    }
                }
            }
        } else {
            if (index > n) {
                return;
            }
            for (int i = m - selected; i >= 1; i--) {
                cnt[index] = i;
                go(n, m, index + 1, selected + i);
            }
            cnt[index] = 0;
            go(n, m, index + 1, selected);
        }

    }

}

수열을 모든 경우로 구성하는 것이 아닌 반드시 비내림차순으로 구성되어야 하기 때문에 수를 선택하거나 선택하지 않는 경우로 문제를 해결할 수 있다. 수의 중복이 가능하기 때문에 현재 항의 위치에 따라 나머지 항에서 중복으로 같은 수를 항으로 가질 수 있는 갯수가 다르고 같거나 오름차순 형태로 수열이 구성되기 때문에 같은 항의 갯수가 많은 수열이 사전 순으로 먼저 나오기 때문에 중복 항이 많은(m - selected) 수열부터 중복이 없는(1) 수열까지 순회한다. 선택하지 않는 경우가 있기 때문에 수가 m개 만큼 선택되지 않는 경우도 있다. 시간 복잡도는 O(2$^{N}$)이다.

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

import java.io.*;
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class Main {

    public static int answer;

    public static int[] buttons = new int[0];

    public static void main(String[] args) throws IOException {
        try (
                BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out))
        ) {
            String line = reader.readLine();
            int n = Integer.parseInt(line);
            int m = Integer.parseInt(reader.readLine());

            answer = getDiff(n, 100);

            if (n == 100) {
                writer.write(0 + "");
            } else if (line.length() >= answer) {
                writer.write(answer + "");
            } else {
                if (m != 0) {
                    List<Integer> brokenButtons = Arrays
                            .stream(reader.readLine().split(" "))
                            .mapToInt(Integer::parseInt)
                            .boxed()
                            .collect(Collectors.toList());
                    buttons = IntStream
                            .range(0, 10)
                            .filter(number -> !brokenButtons.contains(number))
                            .toArray();
                    for (int i = 1; i <= 6; i++) {
                        go(0, i, i, n);
                    }
                } else {
                    answer = line.length();
                }

                writer.write(answer + "");
            }

        }
    }

    public static void go(int base, int position, int length, int n) {
        if (position < 1) {
            return;
        }
        int increase = 1;
        for (int i = 0; i < position - 1; i++) {
            increase *= 10;
        }
        for (int button : buttons) {
            int number = base + button * increase;
            go(number, position - 1, length, n);
            if (position == 1) {
                int diff = getDiff(n, number);
                if (answer > length + diff) {
                    answer = length + diff;
                }
            }
        }
    }

    public static int getDiff(int n, int m) {
        int diff = n - m;
        return diff < 0 ? -diff : diff;
    }

}

위의 리모컨 문제를 순서 방식이 아닌 선택 방식으로 해결하는 방식이다.사용 가능한 버튼으로 구성할 수 있는 수만을 검사하여 최소 버튼 사용 횟수를 구한다.

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

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

public class Main {

    public static int max = Integer.MIN_VALUE;

    public static boolean[][] check;

    public static int[][] arr;

    public static int[][] direction = {
            {0, 0, 1, -1},
            {1, -1, 0, 0}
    };

    public static void main(String[] args) throws IOException {
        try (
                BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out))
        ) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            int n = Integer.parseInt(tokenizer.nextToken());
            int m = Integer.parseInt(tokenizer.nextToken());
            int k = Integer.parseInt(tokenizer.nextToken());

            arr = new int[n][m];
            check = new boolean[n][m];

            for (int i = 0; i < n; i++) {
                tokenizer = new StringTokenizer(reader.readLine());
                for (int j = 0; j < m; j++) {
                    arr[i][j] = Integer.parseInt(tokenizer.nextToken());
                }
            }

            go(0, 0, 0, k, 0);
            writer.write(max + "");
        }
    }

    public static void go(int pi, int pj, int sum, int k, int depth) {
        if (depth == k) {
            if (max < sum) {
                max = sum;
            }
        } else {
            for (int i = pi; i < arr.length; i++) {
                for (int j = (i == pi ? pj : 0); j < arr[i].length; j++) {
                    if (check[i][j]) {
                        continue;
                    }
                    boolean ok = true;
                    for (int l = 0; l < direction[0].length; l++) {
                        int nx = i + direction[0][l];
                        int ny = j + direction[1][l];
                        if (nx >= 0 && nx < arr.length && ny >= 0 && ny < arr[i].length && check[nx][ny]) {
                            ok = false;
                            break;
                        }
                    }
                    if (ok) {
                        check[i][j] = true;
                        go(i, j, sum + arr[i][j], k, depth + 1);
                        check[i][j] = false;
                    }
                }
            }
        }
    }

}

격자의 모든 칸을 순회하면서 이미 선택한 칸인지 또는 선택한 칸의 상하좌우 칸이 이미 선택된 칸인지 검사하여 칸을 선택하고 선택한 칸들의 합을 구한다. 중복되는 검사를 피하기 위해 이전 행의 검사와 이전 열의 검사를 제외한다.

백트래킹

재귀 함수를 이용한 브루트 포스 구현에서 더 이상의 함수 호출이 문제의 해로 이어지지 않는 경우 더 이상의 호출은 의미가 없기 때문에 함수 호출하지 않고 중단한다.

예제

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

import java.io.*;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class Main {

    public static int[][] s;

    public static void main(String[] args) throws IOException {
        try (
                BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out))
        ) {
            int n = Integer.parseInt(reader.readLine());
            s = new int[n][n];
            for (int i = 0; i < n; i++) {
                StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
                for (int j = 0; j < n; j++) {
                    s[i][j] = Integer.parseInt(tokenizer.nextToken());
                }
            }
            int answer = go(n, 0, new ArrayList<>(), new ArrayList<>());
            writer.write(answer + "");
        }
    }

    public static int go(int n, int index, List<Integer> first, List<Integer> second) {
        if (index == n) {
            if (first.size() != n / 2) {
                return -1;
            }
            if (second.size() != n / 2) {
                return -1;
            }
            int t1 = 0;
            int t2 = 0;
            for (int i = 0; i < n / 2; i++) {
                for (int j = 0; j < n / 2; j++) {
                    if (i == j) {
                        continue;
                    }
                    t1 += s[first.get(i)][first.get(j)];
                    t2 += s[second.get(i)][second.get(j)];
                }
            }
            return Math.abs(t1 - t2);
        }
        if (first.size() > n / 2) {
            return -1;
        }
        if (second.size() > n / 2) {
            return - 1;
        }
        int ans = Integer.MAX_VALUE;
        first.add(index);
        int t1 = go(n, index + 1, first, second);
        if (t1 != -1 && ans > t1) {
            ans = t1;
        }
        first.remove(first.size() - 1);
        second.add(index);
        int t2 = go(n, index + 1, first, second);
        if (t2 != -1 && ans > t2) {
            ans = t2;
        }
        second.remove(second.size() - 1);
        return ans;
    }

}

브루트 포스 선택 방식으로 구현해서 문제를 해결하고 한쪽 팀의 인원이 N / 2가 넘는 경우 함수 호출을 중단하는 조건을 추가해 구현한다.

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

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

public class Main {

    public static String[] p;

    public static boolean[] check = new boolean[10];

    public static String min = Long.MAX_VALUE + "";

    public static String max = Long.MIN_VALUE + "";

    public static void main(String[] args) throws IOException {
        try (
                BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out))
        ) {
            int k = Integer.parseInt(reader.readLine());
            p = new String[k];
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());

            for (int i = 0; i < k; i++) {
                p[i] = tokenizer.nextToken();
            }
            go(k, 0, "");
            writer.write(max + "\n");
            writer.write(min + "");
        }
    }

    public static void go(int k, int selected, String answer) {
        if (selected == k + 1) {
            long ans = Long.parseLong(answer);
            if (Long.parseLong(min) > ans) {
                min = answer;
            }
            if (Long.parseLong(max) < ans) {
                max = answer;
            }
            return;
        }
        for (int i = 0; i <= 9; i++) {
            if (check[i]) {
                continue;
            }
            if (selected > 0) {
                if (p[selected - 1].equals("<") && answer.charAt(selected - 1) > i + 48) {
                    continue;
                }
                if (p[selected - 1].equals(">") && answer.charAt(selected - 1) < i + 48) {
                    break;
                }
            }
            check[i] = true;
            go(k, selected + 1, answer + i);
            check[i] = false;
        }
    }

}

브루트 포스 순서 방식으로 구현해서 문제를 해결하고 수가 중복되거나 주어진 부등호 조건에 부합하지 않는 경우 함수 호출을 중단하는 조건을 추가해 구현한다.

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

import java.io.*;

public class Main {

    public static int[] a;

    public static char[][] p;

    public static void main(String[] args) throws IOException {
        try (
                BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out))
        ) {
            int n = Integer.parseInt(reader.readLine());
            a = new int[n];
            p = new char[n][n];
            String s = reader.readLine();
            for (int i = 0; i < n; i++) {
                for (int j = i; j < n; j++) {
                    p[i][j] = s.charAt(i * n + j - (i + 1) * i / 2);
                }
            }
            go(n, 0);
        }
    }


    public static boolean go(int n, int selected) {
        if (selected == n) {
            for (int i = 0; i < a.length; i++) {
                System.out.print(a[i] + " ");
            }
            return true;
        }
        int start;
        int end;
        if (p[selected][selected] == '+') {
            start = 1;
            end = 10;
        } else if (p[selected][selected] == '-') {
            start = -10;
            end = -1;
        } else {
            start = end = 0;
        }

        outer: for (int i = start; i <= end; i++) {
            a[selected] = i;
            int sum = 0;
            for (int j = selected; j >= 0; j--) {
                sum += a[j];
                if (p[j][selected] == '+') {
                    if (sum < 1) {
                        continue outer;
                    }
                } else if (p[j][selected] == '-') {
                    if (sum > -1) {
                        continue outer;
                    }
                } else {
                    if (sum != 0) {
                        continue outer;
                    }
                }
            }
            if (go(n, selected + 1)) {
                return true;
            }
        }

        return false;
    }

}

브루트 포스 순서 방식으로 구현해서 문제를 해결하고 같은 순열의 수의 합이 +, -, 0 중 어떤 것이 나오는지를 이용하여 자기 자신과의 합이 양수이려면 양수(1 ~ 10)이어야 하고 음수이려면 음수(-1 ~ -10), 0이려면 0 밖에 없으므로 범위를 좁힐 수 있다. 수가 선택될 때마다 전체를 다시 검사할 필요는 없고 이전 순열부터 현재 선택한 순열의 합까지만 검사하여 조건에 부합하지 않는 경우함수 호출을 중단하는 조건을 추가해 구현한다.

순열

재귀 방식이 아닌 수열을 구성하여 모든 경우를 구한다. 모든 순열을 순회하거나 구하는 경우보다는 특정 순열의 다음 또는 이전 순열을 구하는 경우 사용한다.

• 순열 {7 2 3 6 5 4 1}에서 마지막 항에서 어디까지 내림차순인지 검사한다. 순열이 모두 내림차순인 경우 이미 마지막 순열이다.
• {7 2 3 (6 5 4 1)}에서 이 순열은 {7 2 3}이 앞 자리인 순열의 가장 마지막 순열이다. i를 6라고 할 때 마지막 항에서 i - 1인 4보다 크면서 가장 작은 수인 4를 j라고 한다.
• {7 2 4 (6 5 3 1)} i - 1과 j를 교환한다.
• {7 2 4 (1 3 5 6)} i부터 마지막 항까지 역순으로 전환한다. 이 순열은 {7 2 4}가 앞 자리인 순열의 가장 첫 번째 순열이다.
• 가장 첫 번째 순열에서 부터 이 과정을 반복하면 마지막 순열까지 순회할 수 있다. 마지막 순열에서 첫 번째 순열로 순회하려면 내림차순을 오름차순으로 반대로 검사하면 된다.

예제

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

import java.io.*;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    public static int[] a;

    public static int max = Integer.MIN_VALUE;

    public static void main(String[] args) throws IOException {
        try (
                BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out))
        ) {
            int n = Integer.parseInt(reader.readLine());
            a = new int[n];
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            for (int i = 0; i < n; i++) {
                a[i] = Integer.parseInt(tokenizer.nextToken());
            }
            Arrays.sort(a);
            do {
                int sum = 0;
                for (int i = 0; i < a.length - 1; i++) {
                    sum += Math.abs(a[i] - a[i + 1]);
                }
                if (max < sum) {
                    max = sum;
                }
            } while (go());
            writer.write(max + "");
        }
    }

    public static boolean go() {
        int i = a.length - 1;
        while (i > 0 && a[i - 1] >= a[i]) {
            i--;
        }
        if (i <= 0) {
            return false;
        }
        int j = a.length - 1;
        while (a[i - 1] >= a[j]) {
            j--;
        }
        swap(a, i - 1, j);
        j = a.length - 1;
        while (i < j) {
            swap(a, i++, j--);
        }
        return true;
    }

    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

}

입력받은 수열의 첫 수열을 구하기 위해 정렬을 수행하고 구성할 수 있는 모든 수열을 첫 순열부터 마지막 순열까지 하나씩 모두 구성하면서 최댓값을 구한다. 시간 복잡도는 O(N log${^N}$ + N!N)이다.

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

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

public class Main {

    public static int[] a;

    public static int[][] w;

    public static int min = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        try (
                BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out))
        ) {
            int n = Integer.parseInt(reader.readLine());
            a = new int[n];
            w = new int[n][n];
            for (int i = 0; i < n; i++) {
                StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
                for (int j = 0; j < n; j++) {
                    w[i][j] = Integer.parseInt(tokenizer.nextToken());
                }
                a[i] = i;
            }

            do {
                int sum = 0;
                boolean ok = true;
                for (int i = 0; i < a.length; i++) {
                    int distance = w[a[i % a.length]][a[(i + 1) % a.length]];
                    if (distance == 0) {
                        ok = false;
                        break;
                    }
                    sum += distance;
                }
                if (ok) {
                    if (min > sum) {
                        min = sum;
                    }
                }
            } while (go());

            writer.write(min + "");
        }
    }

    public static boolean go() {
        int i = a.length - 1;
        while (i > 1 && a[i - 1] >= a[i]) {
            i--;
        }
        if (i <= 1) {
            return false;
        }
        int j = a.length - 1;
        while (a[i - 1] >= a[j]) {
            j--;
        }
        swap(a, i - 1, j);
        j = a.length - 1;
        while (i < j) {
            swap(a, i++, j--);
        }
        return true;
    }

    public static void swap(int[] a, int i, int j) {
        int temp = a[i];
        a[i] = a[j];
        a[j] = temp;
    }

}

시작 지점에서 출발하여 종료 지점을 거쳐 다시 시작 지점으로 돌아오는 조건으로 인해 (0->1->2->3), (1->2->3->0), (2->3->0->1), (3->0->1->2)의 거리 비용은 같다. 임의의 지점을 고정하고 나머지 지점만을 순열로 구성하고 거리가 0인 이동할 수 없는 경우를 제외하여 구한다. 시간 복잡도는 O(N!)이다.

비트마스크

비트(0 or 1) 연산(and, or, not, xor, shift)을 사용해서 부분 집합을 표현할 수 있다. 수의 유무를 비트로 표현하여 공간을 적게 사용할 수 있고 검사, 추가, 삭제의 시간 복잡도가 O(1)인 장점이 있다.

• {1, 3, 4, 5, 9} = 2$^{1}$ x 2$^{3}$ ... x 2$^{9}$ = 570
• 0이 포함되어 있는지 검사 570 & 2$^{0}$ = 570 & (1 << 0) = 0
• 1이 포함되어 있는지 검사 570 & 2$^{1}$ = 570 & (1 << 1) = 2
• 3이 포함되어 있는지 검사 570 >> 3 & 1 = 1
• 6이 포함되어 있는지 검사 570 >> 6 & 1 = 0
• 2를 추가하기 570 | (1 << 2) = 574
• 4를 추가하기 570 | (1 << 4) = 570(변경 없음)
• 3을 제거하기 570 & ~(1 << 3) = 562
• 2를 제거하기 570 & ~(1 << 2) = 570(변경 없음)

예제

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

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

public class Main {

    public static void main(String[] args) throws IOException {
        try (
                BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out))
        ) {
            int s = 0;
            int m = Integer.parseInt(reader.readLine());
            for (int i = 0; i < m; i++) {
                StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
                String operation = tokenizer.nextToken();
                if (operation.equals("add")) {
                    int n = Integer.parseInt(tokenizer.nextToken());
                    s |= 1 << (n - 1);
                } else if (operation.equals("check")) {
                    int n = Integer.parseInt(tokenizer.nextToken());
                    writer.write(((s >> (n - 1)) & 1) + "\n");
                } else if (operation.equals("remove")) {
                    int n = Integer.parseInt(tokenizer.nextToken());
                    s &= ~(1 << (n - 1));
                } else if (operation.equals("toggle")) {
                    int n = Integer.parseInt(tokenizer.nextToken());
                    s ^= 1 << (n - 1);
                } else if (operation.equals("all")){
                    s = (1 << 20) - 1;
                } else {
                    s = 0;
                }
            }
        }
    }

}

비트마스크로 부분 집합을 나타내기 위해 정수형 자료형과 비트 연산자를 사용한다. 비트 연산자를 통해 검사, 추가, 삭제 등 연산을 수행한다.

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

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

public class Main {

    public static void main(String[] args) throws IOException {
        try (
                BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out))
        ) {
            StringTokenizer tokenizer = new StringTokenizer(reader.readLine());
            int n = Integer.parseInt(tokenizer.nextToken());
            int s = Integer.parseInt(tokenizer.nextToken());
            int ans = 0;
            int[] a = new int[n];

            tokenizer = new StringTokenizer(reader.readLine());
            for (int i = 0; i < n; i++) {
                a[i] = Integer.parseInt(tokenizer.nextToken());
            }

            for (int i = 1; i < (1 << n); i++) {
                int sum = 0;
                for (int j = 0; j < n; j++) {
                    if (((i >> j) & 1) == 1) {
                        sum += a[j];
                    }
                }
                if (sum == s) {
                    ans++;
                }
            }

            writer.write(ans + "");
        }
    }

}

부분 순열이 반드시 1개 이상 선택되어야하므로 한 개의 수만 있는 부분 집합의 표현인 1부터 모든 수가 포함된 부분 집합인 (1 << N) - 1까지의 비트 표현으로 나타낼 수 있다. 비트마스크가 포함되어 있는지 검사하면서 포함되어 있는 모든 수를 합해서 입력받은 합과 동일한지 검사한다. 시간 복잡도는 O(N 2$^{N}$)이다.