[알고리즘 이론] 1. 브루트포스 알고리즘

안녕하세요? 닉네임간편입니다. 이번 시간에는 브루트 포스 알고리즘에 대해 알아보겠습니다.

1. 브루트 포스란?

브루트 포스(Brute Force)는 짐승과 힘을 뜻하는 단어를 결합한 것으로, 말 그대로 짐승처럼 원시적으로 가능한 모든 경우를 탐색하는 것입니다. 이를 무차별 대입이라고도 합니다.

예를 들어 전화번호부에서 원하는 이름을 찾고 싶다면, 전화번호부 전체에서 하나씩 이름을 살펴보며 모든 곳을 다 탐색하는 것이 있겠습니다. 이렇게 가능한 모든 곳을 탐색하거나 가능한 모든 조합을 만드는 알고리즘을 완전 탐색(exhaustive search)이라고 합니다.

이 완전 탐색 기법을 사용하는 방법에는 일반 브루트 포스, 그래프 자료구조에 사용되는 DFS와 BFS, 재귀, 순열, 비트 마스크가 있습니다. 다른 내용은 선행 지식이 필요하기 때문에, 본 글에선 우선 재귀와 순열에 대해서 다루겠습니다.

2. 장점

브루트 포스는 모든 경우를 다 탐색하기 때문에 무조건 원하는 경우를 찾을 수 있다는 장점이 있습니다. 즉, 정확성 측면에서 100%를 보장하기 때문에 시간과 자원에 구애받지 않고 무조건 정답을 찾아야 하는 경우라면 브루트 포스를 사용할 수 있습니다.

3. 단점

그러나 말 그대로 모든 경우를 다 탐색해야 하기 때문에 원하는 경우를 찾을 때까지 시간이 오래 걸릴 가능성이 매우 높고, 효율적이지 못합니다. 예를 들어 비밀번호 4자리를 맞추는 게임을 한다고 가정해보겠습니다. 가능한 숫자가 0~9라면 한 자리에 10개의 수를 총 4번에 걸쳐 넣어야 하므로 가능한 조합은 10*10*10*10 = 10^4가 됩니다. 만일 5자리의 비밀번호를 맞춘다면 제곱수가 하나씩 늘어나며, 이때 가능한 숫자의 개수를 M이라고 하고 맞추어야 하는 비밀번호의 자릿수를 N이라고 한다면, 시간 복잡도는 O(M^N)이 됩니다. 이 경우 비밀번호 자릿수가 증가할 때마다 시간 복잡도가 제곱수만큼 증가하기 때문에, 매우 비효율적으로 볼 수 있습니다.

그럼에도 이 알고리즘은 구현이 쉽고 100% 정답을 찾을 수 있다는 점으로 인해서, 그리고 다른 더 빠른 알고리즘의 기반이 되기도 하기에 자주 사용되곤 합니다.

728x90

4. 기법 1-순열

서로 다른 N개의 원소를 순서대로 나열한 것을 순열(permutation)이라고 합니다.

만약 1,2,3이라는 숫자가 있다면 값이 낮은 순서대로 123, 132, 213, 231, 312, 321 이런 식으로 정렬이 됩니다.

이때 총 경우의 수는 N!입니다. 위 예시로 설명하자면 3개의 수 중 앞자리에 놓을 수 있는 수는 1,2,3이므로 총 3개입니다. 그다음 놓을 수 있는 수는 앞에 사용되었던 수를 제외한 나머지 두 개의 수이고, 마지막에는 나머지 수만 놓을 수 있습니다. 따라서 총 경우의 수는 3x2x1 = 3! 이 됩니다.

따라서 N이 커짐에 따라 시간 복잡도가 매우 커지게 됩니다. 그렇기에 완전 탐색이 아닌 다른 기법을 사용하는 경우도 있습니다.

또한 파이썬에서는 permutations라는 아주 유용한 도구가 있기 때문이 이것을 사용해서 예제를 풀어보겠습니다.

문제는 [백준] 10974번-모든 순열 문제입니다.

[문제 링크]

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

10974번: 모든 순열

N이 주어졌을 때 순열을 만들고 그 순열을 사전 순으로, 여기선 숫자만 있으므로 값이 낮은 것부터 오름차순으로 정렬하면 되겠습니다.

from itertools import permutations

N = int(input())
nums = [i for i in range(1, int(input())+1)]
for k in permutations(nums, len(nums)):
    for i in range(len(k)):
        print(k[i], end=' ')
    print()

 

a) permutations 

itertools 모듈에서 permutations를 가져옵니다. 이렇게 import를 하면 해당 기능을 사용할 때 itertools.permutations로 하지 않고 바로 permutations로 사용할 수 있으므로 좀 더 편리합니다.

b) 숫자 배열 생성

N을 입력받은 후, 1부터 N까지의 숫자가 들어간 배열을 생성합니다.

c) 순열 만들고 출력

for k in permutations(nums, len(nums))는 nums라는 배열 내부에 있는 모든 요소들 중에서 len(nums) 개수만큼 뽑아 순열을 만든다는 것입니다. 즉 여기서는 1부터 N개까지의 숫자가 있는 배열에서 N개를 뽑아 순열을 만듭니다.

그러면 반복문에서 k는 순열이 담기게 됩니다. 이때 N이 3인 경우로 예시를 들자면 k는 그대로 출력하면

# 이전 예시| 바꾼 방법
(1, 2, 3) | 1 2 3 
(1, 3, 2) | 1 3 2 
(2, 1, 3) | 2 1 3 
(2, 3, 1) | 2 3 1 
(3, 1, 2) | 3 1 2 
(3, 2, 1) | 3 2 1

 

위와 같이 출력됩니다. 따라서 이를 방지하기 위해 k 내부 요소들을 순서대로 출력하고, end를 ' '로 설정하여 한 칸씩 빈칸을 두고 출력하도록 합니다. 그러면 문제에서 원하는 대로 출력이 되는 것을 확인할 수 있습니다.

5. 기법 2-재귀

브루트 포스 알고리즘으로 코드를 구현한다면 대게 for문으로 같은 동작을 반복하는 경향이 있습니다. 이때 이걸 재귀 함수로 만들어서 호출해주면 코드를 간결하게 표현할 수 있으므로 유용하게 사용됩니다.

재귀 함수는 수행되어야 할 작업을 여러 개로 분리한 뒤, 하나의 동작을 수행하고 나머지는 다시 자기 자신을 호출해서 수행하는 함수입니다.

예를 들어서 팩토리얼을 만드는 함수를 가정해보겠습니다. 팩토리얼은 N부터 시작해서 N-1, N-2,..., 1까지 모두 곱한 값을 의미합니다. 이때 팩토리얼을 재귀 함수로 구현한다면, 곱하는 부분을 함수에 넣은 뒤 1을 뺀 값으로 다시 이 함수를 호출하면 됩니다. 그렇게 되면 factorial(N)*factorial(N-1)*factorial(N-2)...*factorial(1)처럼 표현이 될 것이고, 이를 통해 값을 구할 수 있습니다.

이때 유의해야 할 점은 반드시 재귀 호출을 빠져나올 조건이 있어야 한다는 것입니다. 만일 계속해서 재귀 함수를 호출하는데 빠져나오지 못한다면 결국 스택 오버플로우가 발생해 프로그램이 제대로 동작하지 않을 수 있습니다. 따라서 더 이상 동작을 할 수 없을 때 답을 반환하는 조건문을 포함시켜야 합니다. 이때 더 이상 동작을 할 수 없는, 즉 다시 자기 자신을 호출해 동작을 할 필요 없이 바로 답이 나올 수 있는 사례들을 기저 사례(base case)라고 합니다.

이 부분들은 다음 문제 예제를 통해 알아보겠습니다.

문제는 [백준] 10872-팩토리얼 문제입니다.

[문제 링크]

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

10872번: 팩토리얼

앞선 예시처럼 팩토리얼을 구해야 합니다. 재귀 함수를 통해 구현했습니다.

def factorial(n):
    if n <= 1:
        return 1
    else:
        return n * factorial(n - 1)
print(factorial(int(input())))

 

factorial() 메서드는 숫자 n을 입력받으면 n과 factorial(n-1)을 곱한 값을 반환합니다.

이때 만일 n이 1보다 작거나 같다면, 1을 반환합니다. 이때 n이 0이나 1이 되는 경우가 바로 기저 사례이며, 이럴 경우 바로 답이 반환됩니다.

그 이외의 경우에는 n이 계속 감소하여 factorial(1)이 호출될 때까지 재귀 호출을 계속하여, 이를 다음과 같이 표현할 수 있습니다.

n * factorial(n - 1) => n * n-1 * factorial(n - 2) ...
=> n * n-1 * n-2 * ... * factorial(1)
=> n!

6. 마무리

이렇게 브루트 포스 알고리즘 및 완전 탐색 기법에 대해 알아보았습니다. 저 또한 이번 게시글을 작성하면서 다시금 공부할 수 있어서 좋은 시간이 되었습니다. 이번 게시글을 기준으로 앞으로도 알고리즘 공부를 더 해나가야겠습니다.