Kang Chang Ryong

8 분 소요

이번 시간에는 완전 탐색(브루트 포스)에 대해서 배워보도록 할 것이다.


1. 완전 탐색 알고리즘이란?

한때 유명했던 초등 학교 수학 문제 풀이가 있다.

image

문제가 의도한 대로 푼 풀이는 아니지만 문제가 원하는 답을 얻기 위해서 접근한 과정은 꼭 틀리다 볼 수는 없다.(그러나 답은 틀렸다.)


이처럼 완전 탐색은 모든 경우의 수를 전부 다 체크해서 정답을 찾는 방법이다. 즉, 다시 말해서 무식하게 모든 경우의 수를 하나하나 다 해보겠다는 방법인 것이다.

이러한 방식이 굉장히 무식하다고 하여 "Brute Force"라는 이름이 붙여졌고 모든 알고리즘 중에서 가장 단순하고 직관적인 방법이라고 할 수 있다.


예를 들어, 금고의 4자리 비밀번호를 풀려고 할 때, 이 알고리즘으로 푸는 방법은 0000부터 9999까지 모두 시도해 보는 것이다. 그러면 최대 10000번의 시도를 하게 되고 그 안에는 반드시 해결이 되는 것이다.

그렇지만 만약 4자리가 아니라 8자리라면…? 16자리라면…? (머리가 벌써 아파진다.)


그렇기 때문에 Computer Science(CS)에서 문제 해결 알고리즘을 사용할 때는 다음과 같은 2가지 규칙을 지켜야 한다.

  1. 사용되는 알고리즘이 적절한 방법인가?(제한 조건 내에서 해결될 수 있는가)
  2. 효율적으로 동작하는가?


위 2가지 규칙 중에서 1번은 충분히 만족할 수 있을 것이다. (어떻게든 풀어내면 되는 것이기 때문에)

하지만 2번 규칙은 사용하는데 제한이 따른다.


예를 들어, 다이나믹 프로그래밍으로 해결할 수 있는 문제에서 O(N)의 시간 복잡도가 소모되었다고 하자.

그런데 만약, 이를 완전 탐색으로 풀이를 진행한다면 각 위치 N에 대해 이전의 경우의 수를 모두 따져봐야 하기 때문에 2중 반복문이 생겨 O(n2)의 시간 복잡도를 갖게 된다.


백준이나 프로그래머스 같은 코딩 문제 사이트에서는 입력 값의 범위를 제한한다. 그런데 만약 범위가 100,000이 된다면 (혹은 그 이상) 위 문제를 주어진 시간 이내에 절대 풀어낼 수없는 경우가 생길 수 있는 것이다.

따라서, 브루트 포스는 사용할 때에 해당 문제에 대한 파악이 제일 중요하다.


완전탐색 사용법

완전 탐색을 할 때에는 다음과 같은 것들이 고려되어야 한다.

  1. 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산한다.
  2. 가능한 모든 방법을 다 고려한다.
  3. 실제 답을 구할 수 있는지 적용한다.


위의 2번 방법들에는 다음과 같은 것들이 있다.

① Broute Force 기법 - 반복문 or 조건문을 활용하여 모두 테스트 하는 방법

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

③ 재귀 호출

④ 비트 마스크 - 2진수 표현 기법을 활용하는 방법

⑤ BFS, DFS를 활용하는 방법


① Broute Force 기법

이 방법은 반복문과 조건문을 마구 써서 어떻게 해서 든지 모든 방법을 전부 다 시도해 보는 방법이다. 위의 자물쇠 예시와 같은 방법이다.


② 순열(Permutation)

순열은 임의의 수열에 대하여 다른 순서로 연산하는 방법을 의미한다.

즉, 순서가 중요한 것으로 만약, 수열에서 숫자 {1, 2, 3}이 있다면 이것을 보는 순서에 따라 {1, 2, 3}과 {3, 2, 1}는 서로 순서에 차이가 있기 때문에 서로 다른 수열로 보는 것을 의미한다.


그래서 만약 n개의 서로 다른 데이터가 있고 이를 순열로 나타낸다 하면 전체 순열의 가지 수는 n!개 가 되는 것이다. 고등학교 확률과 통계 시간에 배우는 내용으로 자세히 알고 싶으면 다음 링크를 참고하자.

  • 순열의 설명은 이곳에서 확인하시오.


순열을 구현하는 방법은 다음과 같다.

  1. A[i-1] <= A[i]를 만족하는 i 중 가장 큰 값을 찾는다.(혹은 뒤에서부터 찾는 경우 A[i-1] >= A[i] 중 가장 작은 i를 찾는다.)

    • → 현재 i값을 기준으로 이후의 데이터는 모두 내림차순으로 되는 경우를 찾는 것이다.

    • 현재 기준에서 최종 순열을 찾는다.

    • A배열을 보면 A[i-1] < A[i]가 되는 가장 큰 i는 6이므로 3번째(0부터 시작)이다. 즉, i=3이 된다.

  2. j >= i 중, A[j] > A[i-1]을 만족하는 가장 큰 j의 값을 찾는다.

    • → 현재가 최종 순열 상태이므로 i - 1 번째 숫자를 변경하여 최초 순열을 찾아야 한다.

    • A배열을 기준으로 i-1번째 숫자는 3으로 3보다 큰 경우는 6, 5, 4이나 그 중 j 값이 가장 큰 경우는 4이다.

  3. A[i-1]과 A[j]를 Swap한다.

    • → i-1인 2번째 숫자 3과 j인 5번째 숫자 4를 변경한다.

    • A 배열은 다음과 같이 변경된다.

      • A={7, 2, 4, 6, 5, 3, 1}

  4. i이후의 순열을 모두 뒤집는다.

    • → 최초 순열 상태로 만들어야 하므로 i번째부터는 오름차순으로 만들어야 한다.

    • 배열은 다음과 같이 변경된다.

      • A={7, 2, 4, 1, 3, 5, 6}


위 과정의 시간복잡도를 생각해 보자.

  • 전체 N개의 숫자에 대하여 각각의 순열을 구하는 문제로, 제일 좌측에 숫자 N개가 올 수 있고 각각 (N - 1)!개의 순열을 갖기 때문에 시간 복잡도 O(N x (N -1)!) 이므로 O(N!)을 갖는다.


O(N!)의 시간 복잡도는 O(N)보다 훨씬 더 높은 값이며 N=10인 경우 약 360만 번의 연산이 진행되어야 하고 N=11인 경우 약 4억 번의 연산이 진행되어야 하기 때문에 N이 적당히 큰 범위에서는 이 방법을 절대 사용 불가능 한 것이다.

하지만 작은 범위의 N에서는 나쁘지 않은 효율을 보이기 때문에 문제에서 주어진 N의 범위를 잘 파악해야 한다.


순열 구현

// 순서 없이 n 개중에서 r 개를 뽑는 경우
// 사용 예시: permutation(arr, 0, n, 4);

static void permutation(int[] arr, int depth, int n, int r) {
    if (depth == r) {
        print(arr, r);
        return;
    }
 
    for (int i=depth; i<n; i++) {
        swap(arr, depth, i);
        permutation(arr, depth + 1, n, r);
        swap(arr, depth, i);
    }
}
 
static void swap(int[] arr, int depth, int i) {
    int temp = arr[depth];
    arr[depth] = arr[i];
    arr[i] = temp;
}


③ 재귀(Recursive)

재귀는 그 동안 탐색, 정렬, 트리 등에서 사용되어 설명한 바가 있다. 하지만 이에 대해 자세히 다룬 적은 없었기 때문에 이곳에서 다뤄보도록 하겠다.


image

재귀란 말 그대로 자기 자신을 호출한다는 의미이다.

왜 코딩을 하면서 자기 자신(메소드)을 호출해야 하는 일이 생길까? 다음 예시를 보자.

예를 들어, 총 4개의 숫자 중에서 2개의 숫자를 선택하는 경우를 코드로 구현하고 싶다고 하자.

그러면 1부터 4까지의 숫자 중에서 2개를 중복 없이 선택하는 모든 경우의 수를 출력해야 하기 때문에 반복문으로 이를 표현하면 다음 코드와 같다. 직관적으로 나타내기 위해 파이썬 언어로 나타냈다.

for i in range(1, 5):
    a = i
	for j in range(i+1, 5):
       	b = j 
    	print(i , j)


이처럼 2중 for문을 사용하면 쉽게 구현할 수 있다.

하지만 만약 숫자 N개 중에서 M개를 고르는 경우에 N과 M이 2중 for문을 돌리면 큰일 날 만한 큰 숫자라면 복사 붙여넣기를 마구 한다고 해도 for문을 몇 천개, 몇 만개씩 쓰는 것은 그렇게 좋은 코드는 아닐 것이다.


이 때문에 재귀 함수가 나타나게 된 것이다.

재귀함수를 사용하면 자기 자신을 호출하는 것이기 때문에 자기 자신을 몇 번 호출할 지만 코드에 작성하면 알아서 그 수만큼 호출이 되게끔 할 수 있는 것이다.

그렇게 되면 코드가 몇 천, 몇 만 줄을 쓰던 것이 단 10줄 만에 끝날 수도 있는 것이다.


하지만 재귀를 사용할 때는 주의할 점이 있다.

1) 재귀문을 종료시키기 위한 종료 조건이 반드시 필요하다.

  • 이는 무한루프를 발생시키는 주 원인으로 이를 넣지 않으면 프로그램도 끝나지 않을 것이다.

2) 현재 함수의 상태를 저장하는 parameter(인자)가 필요하다.

  • 이것이 없다면 현재 함수의 상태를 저장할 수가 없어 재귀 탈출(종료) 조건을 만들 수 없게 되거나 잘못된 결과를 출력하게 된다.

3) return 문을 신경 써야 한다.

  • 보통은 void 함수로 작성하지만 재귀를 통해 이후의 연산 결과를 반환한 후에 이전 결과에 추가 연산을 수행해야 하는 경우도 있을 것이다. 이때 문제 해결을 위한 정확한 정의를 수행 해야지만이 완벽하게 문제를 풀 수 있는 것이다.


이는 Dynamic Programming(DP)와도 흡사해 보이는데 DP가 Top-down 방식을 통해 재귀를 사용하여 기저 문제를 통해 종료 조건을 만들고 , 현재 함수의 상태를 전달하는 parameter를 전달하기 때문이다.

완전 탐색과 DP와의 차이는 문제 구조에 있다.

  • DP는 작은 문제가 큰 문제와 동일한 구조를 가져 큰 문제의 답을 구할 때 작은 문제의 결과를 메모이제이션 한뒤 그대로 사용함으로써 수행 속도를 빠르게 한다.
  • 완전 탐색은 크고 작은 문제의 구조가 다를 수도 있으며, 때문에 이전 결과를 반드시 기억할 필요가 없이 그저 해결 가능할만한 모든 방법을 모두 탐색하는 방식이다.

(즉, DP는 일반적인 재귀 중에서 조건을 만족하는 경우에 적용할 수 있다.)

다이나믹 프로그래밍의 설명은 이곳을 참조


④ 비트마스크(Bitmask)

비트마스크란 비트(bit)연산을 통해서 부분 집합을 표현하는 방법을 의미한다.

비트 연산에 대한 내용을 자세히 알고 싶으면 다음 링크를 참고하길 바란다.

  • 비트 연산의 설명은 이곳을 참조


비트 연산을 활용하는 방법은 다음과 같다.

1) 집합 포함 여부 검사

0~9 까지의 숫자 중에서 어떤 숫자가 현재 집합에 포함되어 있는지를 알아보는 방법이다.

{1, 3, 5, 7, 9} = 570 일 때, 0의 포함 여부를 검사하기 위해서 0번째 비트만 1로 만들고 나머지를 9으로 한 것과 570을 2진수로 만든 것을 AND(&) 비트 연산을 하면 된다.

그 이유는 AND 비트 연산은 각각의 비트가 둘 다 1인 경우만 결과가 1이 되기 때문에 0이 포함되어 있으면 1로 표시 되기 떄문에 그 결과로 나온 위치의 비트가 1이라면 해당 숫자가 집합에 포함되어 있는 지를 알 수 있기 때문이다.

아래의 식을 보자.

image

이처럼 0이 포함되어 있는지 확인하고 싶은 비트만 1로 하고 나머지는 0으로 두어서 AND 비트 연산을 진행하면 나머지는 무조건 0이 나올 것이고 해당 자릿수만 원래의 값에 따라 결정 되게끔 하는 것이다.

궁금하면 코드를 자세히 살펴보길 바란다.

public class Main{
    static int[] set = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    static int sub_set = 570;
    public static void main(String[] args){
        // 현재 부분 집합에 0이 포함되었는지 검사
        // 570 & 2^0 이므로 570 & (1 << 0) = 1이라면 있는 것, 0이면 없는 것
        System.out.println((570 & (1 << 0)) == 1 ? "0 있음" : "0 없음" );

        // 현재 부분 집합에 1이 포함되었는지 검사
        // 570 & 2^1 이므로 570 & (1 << 1) = 2이라면 있는 것, 0이면 없는 것
        System.out.println((570 & (1 << 1)) == 2 ? "1 있음" : "1 없음" );

        // 현재 부분 집합에 2가 포함되었는지 검사
        // 570 & 2^2 이므로 570 & (1 << 2) = 4이라면 있는 것, 0이면 없는 것
        System.out.println((570 & (1 << 2)) == 4 ? "2 있음" : "2 없음" );

        // 현재 부분 집합에 3이 포함되었는지 검사
        // 570 & 2^3 이므로 570 & (1 << 3) = 8이라면 있는 것, 0이면 없는 것
        System.out.println((570 & (1 << 3)) == 8 ? "3 있음" : "3 없음" );

        System.out.println(check(4) ? "4 있음" : "4 없음" );
        System.out.println(check(5) ? "5 있음" : "5 없음" );
        System.out.println(check(6) ? "6 있음" : "6 없음" );
    }


    // 함수로 만든 경우
    private static boolean check(int n){
        boolean isExist = (sub_set & (1 << n)) == Math.pow(2, n) ? true : false;
        return isExist;
    }
}

/*
0 없음
1 있음
2 없음
3 있음
4 있음
5 있음
6 없음
*/


2) 숫자 추가하기

위의 1)번과 같이 비트 연산을 통해 숫자를 추가할 수 있었다. 특정 숫자를 추가하기 위해서는 해당하는 위치의 비트를 1로 만들어야 한다.

1로 만들기 위해서는 OR( )연산을 사용하면 되는데, 추가하고자 하는 위치의 비트만 1로 만들고 나머지는 0으로 된 비트와 570을 2진수로 만든 비트를 OR 비트 연산을 거치게 하면 추가하고자 했던 비트의 자리가 1로 변경되는 방식인 것이다.

image


public class Main{
    static int[] set = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
    static int sub_set = 570;
    public static void main(String[] args){
        // 2를 추가
        add(2);
        System.out.println(sub_set);

        // 7을 추가
        add(7);
        System.out.println(sub_set);
        
        System.out.println(check(2) ? "2 있음" : "2 없음" );
        System.out.println(check(7) ? "7 있음" : "7 없음" );
    }

    // 현재 특정 숫자를 추가하는 함수
    private static void add(int n){
        sub_set = sub_set | (1 << n);
    }

    // 현재 특정 숫자가 부분 집합에 있는지 체크하는 함수
    private static boolean check(int n){
        boolean isExist = (sub_set & (1 << n)) == Math.pow(2, n) ? true : false;
        return isExist;
    }
}

/*
결과
574
702
2 있음
7 있음
*/


그 외에도 다음과 같은 방식들이 있다.

3) 특정 숫자 제거하기 - NOT(~) 비트 연산, AND(&) 비트 연산 동시 사용

4) 토글 연산하기 - 0, 1을 왔다갔다 할 수 있게 하는 연산, XOR(^) 비트 연산 사용

5) 전체 집합, 공집합 표현하기 - 전체 집합은 모든 숫자가 1, 공집합은 0


⑤ BFS, DFS 사용하기

BFS와 DFS는 그래프 자료구조에서 모든 정점을 탐색하기 위한 방법이다.

BFS의 설명은 이곳을 참조

DFS의 설명은 이곳을 참조

댓글남기기

참고