[JAVA] 완전탐색(Exhaustive Search)

완전탐색(exhaustive search)

① 완전탐색이란?

▷ 완전탐색은 간단히 가능한 모든 경우의 수를 다 체크해서 정답을 찾는 방법이다. 즉, 무식하게 가능한 거 다 해보겠다는 방법을 의미한다. '무식하게 푼다(brute-force)'는 컴퓨터의 빠른 계산 능력을 이용해 가능한 경우의 수를 일일이 나열하면서 답을 찾는 방법을 의미. 이렇게 가능한 방법을 전부 만들어 보는 알고리즘을 뜻한다.
▷ 완전 탐색은 컴퓨터의 빠른 계산 속도를 잘 이용하는 방법이다.
▷ (예제) n개의 원소 중 m개를 고르는 모든 조합을 출력하는 코드

 

완전 탐색 방법

1. Brute Force : for문과 if문을 이용하여 처음부터 끝까지 탐색하는 방법
2. 순열 : 순열의 시간 복잡도는 O(N!)
3. 재귀호출
4. 비트마스크
5.  BFS, DFS 사용하기

 

① Brute Force 기법 - 반복 / 조건문을 활용해 모두 테스트하는 방법

② 순열(Permutation) - n개의 원소 중 r개의 원소를 중복 허용 없이 나열하는 방법

③ 재귀 호출

④ 비트마스크(Bitmask)

비트마스크 - 2진수 표현 기법을 활용하는 방법⑤ BFS, DFS를 활용하는 방법

비트마스크란 비트(bit) 연산을 통해서 부분 집합을 표현하는 방법을 의미한다.
비트 연산이란 다음과 같은 것들이 있다.
And 연산(&) : 둘 다 1이면 1

OR 연산(|) : 둘 중 1개만 1이면 1

NOT 연산(~) : 1이면 0, 0이면 1

XOR 연산(^) : 둘의 관계가 다르면 1, 같으면 0

Shift 연산(<<, >>) : A << B라고 한다면 A를 좌측으로 B 비트만큼 미는 것이다.

⑤ BFS, DFS 사용하기
이는 그래프 자료 구조에서 모든 정점을 탐색하기 위한 방법이다.
BFS는 너비 우선 탐색으로 현재 정점과 인접한 정점을 우선으로 탐색하고 DFS는 깊이 우선 탐색으로 현재 인접한 정점을 탐색 후 그 다음 인접한 정점을 탐색하여 끝까지 탐색하는 방식이다.

 

다음은 순열을 구하는 코드

import java.util.*;

public class Main {
    static int[] perm = {1, 2, 3, 4}; // 초기 순열 설정
    static int n = 4;

    public static void main(String[] args) {
        StringBuilder sb = new StringBuilder(); // 출력 속도 최적화를 위해 StringBuilder 사용

        do {
            // 현재 순열 출력
            for (int num : perm) sb.append(num).append(" ");
            sb.append("\n");
        } while (nextPermutation()); // 다음 순열이 존재하는 동안 반복

        System.out.print(sb); // 최종 결과 출력 (한 번에 출력하여 I/O 성능 향상)
    }

    /**
     * 사전 순 다음 순열을 생성하는 함수
     * @return 다음 순열이 존재하면 true, 마지막 순열이면 false 반환
     */
    private static boolean nextPermutation() {
        int i = n - 1;

        // 1. 뒤에서부터 탐색하여 perm[i-1] < perm[i]를 만족하는 가장 큰 i 찾기
        while (i > 0 && perm[i - 1] >= perm[i]) i--;

        // 2. 마지막 순열이면 false 반환
        if (i <= 0) return false;

        // 3. i-1보다 큰 값 중 가장 오른쪽 값(j)을 찾기
        int j = n - 1;
        while (perm[j] <= perm[i - 1]) j--;

        // 4. i-1과 j의 값을 교환
        swap(i - 1, j);

        // 5. i부터 끝까지의 부분을 뒤집어 사전 순 최소로 만들기
        for (int left = i, right = n - 1; left < right; left++, right--) {
            swap(left, right);
        }

        return true;
    }

    /**
     * 배열 내 두 원소를 교환하는 함수
     */
    private static void swap(int i, int j) {
        int temp = perm[i];
        perm[i] = perm[j];
        perm[j] = temp;
    }
}