브루트 포스(Brute Force) 알고리즘

다양한 알고리즘 문제들을 풀이하는 방법들이 있는데 그 중 첫 번째는 역시 브루트 포스(Brute Force) 가 아닐까 싶다.

 

해킹 기법 중 가장 기본적인 공격 방식 중에 '무차별 대입 공격(brute-force attack)'이라는 것이 있는데, 이는 특정한 암호를 풀기 위해 가능한 모든 값을 대입하는 방식을 의미한다! 쉽게 생각하자면 아래 자전거 자물쇠를 살펴보면 된다.

이 자전거 자물쇠를 푸는 가장 쉬운 방법은 '0000' 부터 '9999'까지 하나씩 돌려보면 될 것이다.

 

브루트 포스(brute force) 알고리즘 역시 마찬가지다. 다른 말로 '무식하게 풀기'라고도 하는데, 특정한 문제에 발생 가능한 경우의 수를 일일이 나열하면서 답을 찾는 것이다. 최단 거리를 찾기 위해 노드 간의 경로들을 일일이 다 만들어 볼 수도 있을 것이며, 자원의 분배의 경우 모든 분배 방법을 전부 만들어보는 알고리즘이 이에 해당되겠다.

 

모든 경우의 수에 대해 체크하는 것이므로 이를 완전 탐색(exhaustive search) 라고도 부른다. 어떻게 보면 우리가 할 수 없는 일을 컴퓨터라는 고성능 자원을 이용해 처리하는 가장 근본적인 방식이라고 볼 수도 있겠다.

 

앞으로 소개할 알고리즘 방식들은 이 완전 탐색에 기반을 두고 설명이 가능하다. 결국 어떠한 문제라도 모든 경우를 대입하고 처리하면 답은 나오기 마련인데, 우리의 자원(시간, 공간)은 한정적이므로 이 과정에서 불필요한 연산과정을 제거함으로써 보다 효과적인 알고리즘을 만들어 내는 것이 주요한 목표가 될 것이다.

 

완전탐색을 처리하기 위해서는 재귀 호출(recursive function)을 주된 테크닉으로 사용하게 된다. 재귀 함수는 수행해야 할 작업을 유사한 형태의 여러 조각으로 나눈 뒤, 그 중 한 조각을 수행하고 나머지는 스스로를 호출해 실행하는 함수를 의미한다!

 

실무에서는 특수한 비즈니스 로직을 생성하지 않는 이상 '재귀 함수'는 코드 가독성을 떨어뜨리고 디버깅에 어려움을 줄 수 있으므로 잘 쓰지 않지만, 알고리즘에서만큼은 효율적인 도구로 동작한다. 또한 알고리즘 공부를 통해서 재귀 함수를 자주 작성하다 보면, 기능에 따른 메소드 분할을 신경 써서 처리할 수 밖에 없는데 이는 곧 실무에서 하나의 메소드가 하나의 기능만을 수행하도록 코드를 작성함에 도움이 된다고 개인적으로 생각한다.

 

그럼 예제 문제를 통해서 완전탐색을 살펴보자.

---

[백준] 1681번 줄세우기 - Bronze 2

1681번: 줄 세우기

문제

민승이는 N(1 ≤ N ≤ 1,000,000)명의 학생들에게 양의 정수로 된 라벨을 붙이려고 한다. 하지만 모든 학생들은 숫자 L(0 ≤ L ≤ 9)이 자신의 라벨 숫자에 포함되길 원치 않는다. 
문제는 학생들에게 숫자 L을 쓰지 않고 최소한 작은 N개의 양의 수 세트를 라벨링 할 때 학생들이 받는 라벨 중 가장 큰 수가 몇 인지를 구하는 것이다.

문제를 접했을 때, 이를 완전탐색으로 풀이할 수 있는가를 판단하기 위해서 가장 중요한 것은 시간 복잡도를 판단해보는 것이다. 완전 탐색은 탐색해야 되는 값의 개수에 비례해서 연산 횟수가 증가하기 때문이다.

 

현재 문제를 풀기 위해서 1부터 시작하여 L을 포함하지 않는 양의 정수를 찾으면 학생에 라벨을 하나씩 할당하는 방식을

채택한다고 가정하자. 이 방식에서 핵심은 양의 정수에서 L 포함 여부를 판단하는 것 일텐데, 양의 정수 M 에 대해서 L 포함 여부를 판단하는 것은 M의 자리수가 늘어날 수록 기하 급수적으로 늘어나게 될 것이다. 수식을 작성하다 귀찮아서 패스...

 

하지만 현재 문제의 경우 N이 1,000,000 이라는 제한적인 범위를 갖고 있으므로, 완전 탐색으로 풀이가 가능하게 된다.

public class Main {

    static char L;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        L = st.nextToken().charAt(0);

        int num = 0;
        while (N-- > 0) {
            num = makePossibleNumber(++num);
        }

        bw.write(num + "");
        bw.flush();
        bw.close();
        br.close();
    }

    private static int makePossibleNumber(int n) {
        return String.valueOf(n).indexOf(L) != -1
                ? makePossibleNumber(n + 1)
                : n;
    }
}

앞서 언급한 재귀를 응용해서 문제를 풀어보자.

 

num을 순차적으로 탐색하며 L이 포함되어 있는 경우 num을 증가 시켜 다시 조건을 만족하는지 판단하고, L이 포함되지 않은 경우에는 해당 숫자를 반환하여, 학생에게 할당해주는 방식을 채택한다.

---

[정리]

1. 완전탐색은 모든 경우의 수를 탐색하는 것이므로, 탐색하는 횟수를 검증하는 과정이 중요하다. 최대 크기의 입력을 가정하였을 때, 이를 완전탐색으로 해결할 수 있는지 먼저 생각하자.

 

2. 완전탐색으로 가능하다고 판단되었을 경우, 큰 문제를 작은 문제로 나눌 수 있는지 생각해보자.

 단일 메소드로 처리해도 무방하지만, 작은 문제로 분할하는 연습을 미리미리 하지 않으면 향후 DP와 같은 다른 알고리즘에서 골머리가 아플 것이다.

---

[ 함께 풀어보면 좋을 문제 ]

 

1. Bronze 2 - 완전 제곱수

1977번: 완전제곱수

2. Silver 4 - 사이클 단어

1544번: 사이클 단어

3. Silver 3 - N과 M(1)
  백트래킹(backtracking)이라는 테크닉이 필요하지만, 우선 완전탐색으로 풀이하며 백트래킹의 필요성을 느껴본다.

 

15649번: N과 M (1)