[코딩테스트 대비]완전탐색 (BP - 브루트포스)

완전탐색 (Brute-Force)

BP라고 불리는 완전탐색은 단어 그래로 모든 경우의 수를 다 해보는 것이다.
알고리즘을 풀때 강력한 방식이지만, 시간은 최대로 들어간다.

예를들어 비밀번호가 4자리이고 숫자로만 이루어져 있다면, 0 ~ 9999까지 다 해보면된다.

경우의 수는 10,000가지이다. 만약 한 숫자당 1초가 걸린다고 하면 10,000초 = 2.7시간정도가 걸린다.

따라서 완전탐색을 풀기위해서는 대표적으로 4가지를 생각해볼 수 있다.

1. for문 사용
2. 순열, 조합 사용
3. 재귀함수 사용
4. 비트마스크 사용

• 2309번 일곱 난쟁이

조합을 이용해서 풀면된다.

• 1476번 날짜 계산

나머지를 이용

• 14500번 테트로미노

노가다 문제...

• 1966번 프린터 큐

큐 개념도 연습할 수 있다.

• 2231번 분해합

 

순열(Permutation)

서로 다른 n개의 원소에서 r개를 중복을 허용하지 않고 선택하여 순서대로 늘어 놓은 것을 nPr로 표기한다.

참고로 C++에서는 STL nextPermutation을 이용하면 되기 때문에 Java보다 더 쉽게 해결할 수 있다.

 

다음 순열 구하기

1. A[i-1] < A[i]를 만족하는 가장 큰 i를 찾는다.
2. j >= i 이면서 A[j] > A[i-1]를 만족하는 가장 큰 j를 찾는다.
3. A[i-1]과 A[j]를 swap한다.
4. A[i]부터 순열을 뒤집는다.

ex) 7 2 3 6 5 4 1

1. 오른쪽부터 왼쪽이 작은 수를 찾는다. 3 < 6, 6선택 i = 3
2. 다시 오른쪽부터 확인해서 3보다 첫번째로 큰 숫자를 찾는다. -> 4
3. 3과 4를 자리를 바꾼다 -> 7 2 4 6 5 3 1
4. 바꾼 숫자의 오른쪽 전부를 뒤집는다. -> 7 2 4 1 3 5 6

public void nextPermutation(int[] arr) {
    for (int i = arr.length - 1; i > 0; i--) {
        // 끝에서 부터 A[i-1] < A[i]를 만족하는 가장 큰 i 탐색
        if (arr[i - 1] < arr[i]) {
            // i를 찾았으면 j >= i이면서 A[j] > A[i - 1]를 만족하는 가장 큰 j를 찾는다.
            for (int j = arr.length - 1; j >= i; j--) {
                if (arr[j] > arr[i - 1]) {
                    /* A[i]와 A[j]를 swap */
                    /* A[i]부터 순열을 뒤집는다. */
                }
            }
        }
    }
}

• 10972번 다음 순열

 

이전 순열 구하기

다음 순열에서 부등호만 바꿔주면 되는 문제다.

1. A[i-1] > A[i]를 만족하는 가장 큰 i를 찾는다.
2. j >= i이면서 A[j] < A[i-1]를 만족하는 가장 큰 j를 찾는다.
3. A[i-1]과 A[j]를 swap한다.
4. A[i]부터 순열을 뒤집는다.

ex) 7 2 3 6 5 4 1

1. 오른쪽부터 왼쪽의 수가 큰 수를 찾는다. 4 > 1, i = 6
2. 다시 오른쪽부터 확인해서 4보다 첫 번째로 작은 수를 찾는다. -> 1
3. 4와 1의 자리를 바꾼다. -> 7 2 3 6 5 1 4
4. 바꾼 숫자의 오른쪽 전부를 뒤집는다.

public void previousPermutation(int[] arr) {
    for (int i = arr.length - 1; i > 0; i--) {
        // 끝에서 부터 A[i-1] > A[i]를 만족하는 가장 큰 i를 탐색
        if (arr[i - 1] > arr[i]) {
            // i를 찾았으면 j >= i이면서 A[j] < A[i-1]를 만족하는 가장 큰 j를 찾는다.
            for (int j = arr.length - 1; j >= i; j--) {
                if (arr[j] < arr[i - 1]) {
                    /* A[i]와 A[j]를 swap */
                    /* A[j]부터 순열을 뒤집는다. */
                }
            }
        }
    }
}

• 10973번 이전 순열

 

모든 순열 구하기

모든 순열 문제는 다음 순열 문제를 활용해서 풀면 간단하게 해결할 수 있다.

1. 1, 2, ..., n 기본 순열을 구한다.
2. 다음 순열을 구한다.
3. 반복

• 10974번 모든 순열
• 10819번 차이를 최대로
• 2098번 외판원 순회2

유명한 NP문제이다. 풀이법이 상당히 까다로운데 순열문제를 활용하면 된다. 
그리고 이 문제는 DFS도 연습할 수 있으므로 2가지 방법으로 풀어보는 것이 좋다.